查看“︁取整函数”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
[[File:Floor function.svg|thumb|right|下取整函数]]
[[File:Ceiling function.svg|thumb|right|上取整函数]]
在[[数学]]和[[计算机科学]]中，'''取整函数'''是一类将[[实数]]映射到相近的[[整数]]的[[函数]]。<ref>[[葛立恆|Ronald Graham]], [[高德纳|Donald Knuth]] and {{tsl|en|Oren Patashnik||Oren Patashnik}}. "''Concrete Mathematics''". Addison-Wesley, 1999. Chapter 3, "Integer Functions".</ref>

常用的取整函数有两个，分别是'''下取整函数'''（{{lang-en|floor function}}）和'''上取整函数'''（{{lang|en|ceiling function}}）。

'''下取整函数'''即為'''取底符號'''，在数学中一般记作<math>[ x ]</math>或者<math>\lfloor x \rfloor</math>或者<math>E(x)</math>，在计算机科学中一般记作floor(''x'')，表示不超过''x''的整数中最大的一个。
: <math> [ x ]=\max\, \{n\in\mathbb{Z}\mid n\le x\}.</math>

举例来说，<math>[ 3.633 ] = 3</math>，<math>[ 56 ] = 56</math>，<math>[ -2 ] = -2</math>，<math>[ -2.263 ] = -3</math>。对于非负的实数，其下取整函数的值一般叫做它的'''整数部分'''或'''取整部分'''。而<math>x -[ x]</math>叫做''x''的[[小数]]部分。每个[[分数]]都可以表示成其整数部分与一个[[真分数]]的和，而实数的整数部分和小数部分是与此概念相应的拓延。

下取整函数的符号用[[方括号]]表示（<math>[x]</math>），称作'''[[高斯符号]]'''，首次出現是在[[卡爾·弗里德里希·高斯]]的數學著作《[[算术研究]]》。


'''上取整函数'''即為'''取頂符號'''在数学中一般记作<math>\lceil x \rceil</math>，在计算机科学中一般记作ceil(''x'')，表示不小于''x''的整数中最小的一个。
: <math> \lceil x \rceil=\min\{n\in\mathbb{Z}\mid x\le n\}.</math>

举例来说，<math>\lceil 3.633 \rceil = 4</math>，<math>\lceil 56 \rceil = 56</math>，<math>\lceil -2 \rceil = -2</math>，<math>\lceil -2.263 \rceil = -2</math>。

计算机中的上取整函数和下取整函数的命名来自于[[英文]]的''ceiling''（天花板）和''floor''（地板），1962年由[[肯尼斯·艾佛森]]于《A Programming Language》引入。<ref>{{cite book
  | last1 = Iverson | first1 = Kenneth E.
  | title = A Programming Language
  |publisher = Wiley
  | year = 1962}}</ref>

==性质==

对于高斯符號，有如下性质。
*按定义：
*:<math> [ x] \le x < [ x ] + 1</math> 当且仅当''x''为整数时取等号。
* 设x和n为正整数，则：
*:<math> \left[ \frac{n}{x} \right] \geq \frac{n}{x} - \frac{x-1}{x} </math>
* 当''n''为正整数时，有：
*:<math> \left\lbrack \frac{x}{n} \right\rbrack = \frac{x-x\bmod n}{n},</math> 其中<math>x \bmod n</math>表示<math>x</math>除以<math>n</math>的餘數。
* 对任意的整数''k''和任意实数''x''，
*:<math> [ {k+x} ] = k + [ x].</math>
*一般的[[數值修約規則]]可以表述为将''x''映射到floor(''x'' + 0.5)；
* 高斯符號不是[[连续|连续函数]]，但是[[半連續性|上半连续的]]。作为一个分段的[[常数函数]]，在其导数有定义的地方，高斯符號导数为零。
* 设''x''为一个实数，''n''为整数，则由定义，''n'' ≤ ''x''[[当且仅当]]''n'' ≤ floor(''x'')。
* 當''x''是正數時，有：
*:<math>\left\lbrack 2 x \right\rbrack - 2 \left\lbrack x \right\rbrack \leqslant 1</math>
* 用高斯符號可以写出若干个[[素数公式]]，但没有什么实际价值，見{{section link|#質數公式}}。
* 对于非整数的''x''，高斯符號有如下的[[傅里叶级数]]展开：
*:<math>[ x] = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^\infty \frac{\sin(2 \pi k x)}{k}.</math>
* 根据[[Beatty定理]]，每个正[[无理数]]都可以通过高斯符號制造出一个整数集的[[集合劃分|分划]]。
* 最后，对于每个正整数''k''，其在 [[进位制|p 进制]]下的表示有 <math>[ \log_{p}(k) ] + 1</math> 个[[数位]]。

=== 函數間之關係 ===
由上下取整函數的定義，可見
:<math>\lfloor x \rfloor \le \lceil x \rceil,</math>
等號當且僅當<math>x</math>為整數，即
:<math>\lceil x \rceil - \lfloor x \rfloor = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\
1,&\text{ 若 }\ x\not\in \mathbb{Z}.
\end{cases}</math>

實際上，上取整與下取整函數作用於整數<math>n</math>，效果等同[[恆等函數]]：
:<math>\lfloor n \rfloor = \lceil n \rceil = n.</math>

自變量加負號，相當於將上取整與下取整互換，外面再加負號，即：
:<math> \begin{align}
\lfloor x \rfloor +\lceil -x \rceil &= 0, \\
-\lfloor x \rfloor &= \lceil  -x \rceil, \\
-\lceil  x \rceil  &= \lfloor -x \rfloor.
\end{align}
</math>

且：
:<math>\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\
-1,&\text{ 若 }\ x\not\in \mathbb{Z},
\end{cases}</math>

:<math>\lceil x \rceil + \lceil -x \rceil = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\
1,&\text{ 若 }\ x\not\in \mathbb{Z}.
\end{cases}</math>

至於小數部分<math>\{x \} = x - \lfloor x \rfloor</math>，自變量取相反數會使小數部分變成關於1的「補數」：

:<math>\{ x \} +  \{ -x \} = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\
1,&\text{ 若 }\ x\not\in \mathbb{Z}.
\end{cases}</math>

上取整、下取整、小數部分皆為[[冪等|冪等函數]]，即函數疊代兩次的結果等於自身：

:<math>
\begin{align}
\Big\lfloor \lfloor x \rfloor \Big\rfloor &= \lfloor x \rfloor, \\
\Big\lceil \lceil x \rceil \Big\rceil &= \lceil x \rceil, \\
\Big\{ \{ x \} \Big\} &= \{ x \}.
\end{align}
</math>

而多個上取整與下取整依次疊代的效果，相當於最內層一個：
:<math>
\begin{align}
\Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\
\Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor,
\end{align}
</math>
因為外層取整函數實際衹作用在整數上，不帶來變化。

=== 商 ===
若<math>m</math>和<math>n</math>為正整數，且<math>n \neq 0</math>，則
:<math>0 \le \left \{\frac{m}{n} \right\} \le 1-\frac{1}{|n|}.</math>

若<math>n</math>為正整數，則{{sfn|Graham|Knuth|Patashnik|1994|page = 73}}
:<math>\left\lfloor\frac{x+m}{n}\right\rfloor = \left\lfloor\frac{\lfloor x\rfloor +m}{n}\right\rfloor,
</math>

:<math>\left\lceil\frac{x+m}{n}\right\rceil = \left\lceil\frac{\lceil x\rceil +m}{n}\right\rceil.
</math>

若<math>m</math>為正數，則{{sfn|Graham|Knuth|Patashnik|1994|page = 85}}

:<math>n=\left\lceil\frac{n}{m}\right\rceil + \left\lceil\frac{n-1}{m}\right\rceil +\dots+\left\lceil\frac{n-m+1}{m}\right\rceil,
</math>

:<math>n=\left\lfloor\frac{n}{m}\right\rfloor + \left\lfloor\frac{n+1}{m}\right\rfloor +\dots+\left\lfloor\frac{n+m-1}{m}\right\rfloor.
</math>

代<math>m = 2</math>，上式推出：

:<math>n= \left\lfloor \frac{n}{2}\right \rfloor + \left\lceil\frac{n}{2}\right \rceil.</math>

更一般地，對正整數<math>m</math>，有{{link-en|埃爾米特恆等式|Hermite's identity}}：{{sfn|Graham|Knuth|Patashnik|1994|loc = p. 85 and Ex. 3.15}}

:<math>\lceil mx \rceil =\left\lceil x\right\rceil  + \left\lceil x-\frac{1}{m}\right\rceil +\dots+\left\lceil x-\frac{m-1}{m}\right\rceil,
</math>

:<math>\lfloor mx \rfloor=\left\lfloor x\right\rfloor + \left\lfloor x+\frac{1}{m}\right\rfloor +\dots+\left\lfloor x+\frac{m-1}{m}\right\rfloor.
</math>

對於正整數<math>m</math>，以下兩式可將上下取整函數互相轉化：{{sfn|Graham|Knuth|Patashnik|1994|loc =Ex. 3.12}}

:<math>\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1, </math>

:<math>\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil = \left\lceil \frac{n + 1}{m} \right\rceil - 1. </math>

對任意正整數<math>m</math>和<math>n</math>，有：{{sfn|Graham|Knuth|Patashnik|1994|page =94}}

:<math>\sum_{k = 1}^{n - 1} \left\lfloor \frac{k m}{n} \right\rfloor = \frac{(m - 1)(n - 1)+\gcd(m,n)-1}2,</math>

作為特例，當<math>m</math>和<math>n</math>[[互質]]時，上式簡化為

:<math>\sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor = \frac{1}{2}(m - 1)(n - 1).</math>

此等式可以幾何方式證明。又由於右式關於<math>m</math>、<math>n</math>對稱，可得

:<math>\left\lfloor \frac{m}{n} \right \rfloor + \left\lfloor \frac{2m}{n} \right \rfloor + \dots + \left\lfloor \frac{(n-1)m}{n} \right \rfloor =
\left\lfloor \frac{n}{m} \right \rfloor + \left\lfloor \frac{2n}{m} \right \rfloor + \dots + \left\lfloor \frac{(m-1)n}{m} \right \rfloor.
</math>

更一般地，對正整數<math>m, n</math>，有

:<math>\begin{align}
&\left\lfloor \frac{x}{n} \right \rfloor +
\left\lfloor \frac{m+x}{n} \right \rfloor +
\left\lfloor \frac{2m+x}{n} \right \rfloor +
\dots +
\left\lfloor \frac{(n-1)m+x}{n} \right \rfloor\\=
&\left\lfloor \frac{x}{m} \right \rfloor +
\left\lfloor \frac{n+x}{m} \right \rfloor +
\left\lfloor \frac{2n+x}{m} \right \rfloor +
\cdots +
\left\lfloor \frac{(m-1)n+x}{m} \right \rfloor.
\end{align}
</math>

上式算是一種「互反律」（{{lang|en|reciprocity law}}）{{sfn|Graham|Knuth|Patashnik|1994|page = 94}}，與{{section link|#二次互反律}}有關。

== 應用 ==

=== 二次互反律 ===
高斯給出[[二次互反律]]的第三個證明，經[[費迪南·艾森斯坦|艾森斯坦]]修改後，有以下兩個主要步驟。{{sfn|Lemmermeyer|2000|loc = § 1.4, Ex. 1.32–1.33}}{{sfn|Hardy|Wright|1980|loc = §§ 6.11–6.13}}

設<math>p</math>、<math>q</math>為互異奇質數，又設
:<math>m = \frac{p - 1}{2},</math>  <math>n = \frac{q - 1}{2}.</math>

首先，利用[[高斯引理]]，證明[[勒让德符号]]可表示為和式：

:<math>\left(\frac{q}{p}\right) = (-1)^{\left\lfloor\frac{q}{p}\right\rfloor +\left\lfloor\frac{2q}{p}\right\rfloor +\dots +\left\lfloor\frac{mq}{p}\right\rfloor },</math>

同樣
:<math>\left(\frac{p}{q}\right) = (-1)^{\left\lfloor\frac{p}{q}\right\rfloor +\left\lfloor\frac{2p}{q}\right\rfloor +\dots +\left\lfloor\frac{np}{q}\right\rfloor }.</math>

其後，採用幾何論證，證明
:<math>\left\lfloor\frac{q}{p}\right\rfloor +\left\lfloor\frac{2q}{p}\right\rfloor +\dots +\left\lfloor\frac{mq}{p}\right\rfloor

+\left\lfloor\frac{p}{q}\right\rfloor +\left\lfloor\frac{2p}{q}\right\rfloor +\dots +\left\lfloor\frac{np}{q}\right\rfloor

= mn.
</math>

總結上述兩步，得

:<math>\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{mn}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.</math>

此即二次互反律。一些小整數模奇質數<math>p</math>的二次特徵標，可以高斯符號表示，如：{{sfn|Lemmermeyer|2000|p=25}}
:<math>\left(\frac{2}{p}\right)  = (-1)^{\left\lfloor\frac{p+1}{4}\right\rfloor},</math>

:<math>\left(\frac{3}{p}\right)  = (-1)^{\left\lfloor\frac{p+1}{6}\right\rfloor}.</math>

=== 質數公式 ===
下取整函數出現於若干刻畫質數的公式之中。舉例，因為<math>\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor</math>在<math>m</math>整除<math>n</math>時等於<math>1</math>，否則為<math>0</math>，所以正整數<math>n</math>為質數[[当且仅当]]<ref>{{harvnb|Crandall|Pomerance|2001|loc = Ex. 1.3, p. 46}}，求和式的上限<math>\infty</math>可以換成<math>n</math>。尚有一個等價的表述：<math>n > 1</math>為質數當且僅當<math>\sum_{m=1}^{\lfloor \sqrt n \rfloor}\left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 1.</math></ref>

:<math>\sum_{m=1}^{\infty}\left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 2.</math>

除表示質數的條件外，還可以寫出公式使其取值為質數。例如，記第<math>n</math>個質數為<math>p_n</math>，任選一個整數<math>r > 1</math>，然後定義實數<math>\alpha</math>為

:<math>\alpha = \sum_{m=1}^\infty p_m r^{-m^2}.</math>

則衹用取整、冪、四則運算可以寫出質數公式：{{sfn|Hardy|Wright|1980|loc = § 22.3}}

:<math>p_n = \left\lfloor r^{n^2}\alpha \right\rfloor - r^{2n-1}\left\lfloor r^{(n-1)^2}\alpha\right\rfloor.</math>

類似還有[[米尔斯常数]]<math>\theta = 1.3064\ldots</math>，使

:<math>\left\lfloor \theta^3 \right\rfloor, \left\lfloor \theta^9 \right\rfloor, \left\lfloor \theta^{27} \right\rfloor, \dots</math>

皆為質數。<ref name="Ribenboim, p. 186">{{harvnb|Ribenboim|1996|page = 186}}</ref>

若不[[疊代]]三次方函數，改為疊代以<math>2</math>為㡳的[[指數函數]]，亦有<math>\omega = 1.9287800\ldots</math>使

:<math>\left\lfloor 2^\omega\right\rfloor, \left\lfloor 2^{2^\omega} \right\rfloor, \left\lfloor 2^{2^{2^\omega}} \right\rfloor, \dots</math>

皆為質數。<ref name="Ribenboim, p. 186"/>

以[[質數計算函數]]<math>\pi(x)</math>表示小於或等於<math>x</math>的質數個數。由[[威尔逊定理]]，可知{{sfn|Ribenboim|1996|page =181}}

:<math>\pi(n) = \sum_{j=2}^n\left\lfloor\frac{(j-1)!+1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor\right\rfloor.</math>

又或者，當<math>n \ge 2</math>時：{{sfn|Crandall|Pomerance|2001|loc = Ex. 1.4, p. 46}}

:<math>\pi(n) = \sum_{j=2}^n \left\lfloor \frac{1}{\sum_{k=2}^j\left\lfloor\left\lfloor\frac{j}{k}\right\rfloor\frac{k}{j}\right\rfloor}\right\rfloor.</math>

本小節的公式未有任何實際用途。<ref>{{harvnb|Ribenboim|1996|page =180}}（譯文）：「雖然該些公式毫不實用⋯⋯但邏輯學家希望清晰明白不同公理體系，如何推導出算術各方面，則或許與此有關⋯⋯」</ref><ref>{{harvnb|Hardy|Wright|1980|pages = 344—345}}（譯文）：「若數<math>\alpha</math>的準確值⋯⋯可以無關質數的方式表達，則該些公式之任一（或一切類似公式）的地位將截然不同。似乎沒有此種可能，但卻不能完全排除。」</ref>

==其它等式==

* 对于所有实数''x''，有：
:<math> \left\lfloor \frac{x}{2} \right\rfloor = \frac{1}{4} ((-1)^{\lfloor x \rfloor}-1 + 2 \lfloor x \rfloor ) </math>
:<math> \left\lfloor \frac{x}{3} \right\rfloor = \frac{1}{3} (\frac{2}{\sqrt{3}} \sin(\frac{2\pi}{3}\lfloor x \rfloor + \frac{\pi}{3}) - 1 + \lfloor x \rfloor )</math>
[[Category:基本特殊函数]]
[[Category:数学符号]]

==参考来源==
{{reflist|30em}}
*{{cite book
  | last1 = Crandall
  | first1 = Richard
  | last2 = Pomerance
  | first2 = Carl
  | title = Prime Numbers: A Computational Perspective
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 2001
  | isbn = 0-387-94777-9
  | url = https://books.google.com/books?id=8KZ4RQufxhYC
  | ref = harv
  | access-date = 2022-02-06
  | archive-date = 2022-04-09
  | archive-url = https://web.archive.org/web/20220409035435/https://books.google.com/books?id=8KZ4RQufxhYC
  | dead-url = no
  }}
*{{cite book
  | last1 = Graham  | first1 = Ronald L.
  | last2 = Knuth  | first2 = Donald E.
  | last3 = Patashnik  | first3 = Oren
  | title = Concrete Mathematics
  | publisher = Addison-Wesley
  | location = Reading Ma.
  | year = 1994
  | isbn = 0-201-55802-5
  | ref  = harv
}}
*{{cite book
  | last1 = Hardy
  | first1 = G. H.
  | last2 = Wright
  | first2 = E. M.
  | title = An Introduction to the Theory of Numbers (Fifth edition)
  | publisher = [[Oxford University Press]]
  | location = Oxford
  | year = 1980
  | isbn = 978-0-19-853171-5
  | url = https://archive.org/details/introductiontoth00hard
  | ref = harv
  }}
*{{cite book
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | url = https://archive.org/details/reciprocitylawsf0000lemm  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2000
  | isbn = 3-540-66957-4
  | ref  = harv
  |}}
*{{cite book
  | last1 = Ribenboim  | first1 = Paulo
  | title = The New Book of Prime Number Records
  | url = https://archive.org/details/newbookofprimenu0000ribe  | publisher = Springer
  | location = New York
  | year = 1996
  | isbn = 0-387-94457-5
  | ref  = harv
}}

== 另见 ==
[[截尾函数]]

[[category:数论]]
[[Category:函数]]