取整函数

File:Floor function.svg

下取整函数

File:Ceiling function.svg

上取整函数

在数学和计算机科学中，取整函数是一类将实数映射到相近的整数的函数。

常用的取整函数有两个，分别是下取整函数（英語：floor function）和上取整函数（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》引入。

性质

对于高斯符號，有如下性质。

• 按定义：

  <math> [ x] \le x < [ x ] + 1</math>; 当且仅当 <math>x</math> 为整数时取等号。

• 设 <math>x</math> 和 <math>n</math> 为正整数，则：

  <math> \left[ \frac{n}{x} \right] \geq \frac{n}{x} - \frac{x-1}{x} </math>

• 当 <math>n</math> 为正整数时，有：

  <math> \left[ \frac{x}{n} \right] = \frac{x-x\bmod n}{n},</math> 其中 <math>x \bmod n</math> 表示 <math>x</math> 除以 <math>n</math> 的餘數。

• 对任意的整数 <math>k</math> 和任意实数 <math>x</math>，

  <math> [ {k+x} ] = k + [ x].</math>

• 一般的數值修約規則可以表述为将 <math>x</math> 映射到 <math>\left[ x + 0.5 \right]</math>；
• 高斯符號不是连续函数，但是上半连续的。作为一个分段的常数函数，在其导数有定义的地方，高斯符號导数为零。
• 设 <math>x</math> 为一个实数，<math>n</math> 为整数，则由定义，<math>n \leq x</math> 当且仅当 <math>n \leq \left[ x\right] </math>。
• 當 <math>x</math> 是正數時，有：

  <math>\left[ 2 x \right] - 2 \left[ x \right] \leqslant 1</math>

• 用高斯符號可以写出若干个素数公式，但没有什么实际价值，見§ 質數公式。
• 对于非整数的 <math>x</math>，高斯符號有如下的傅里叶级数展开：

  <math>[ x] = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^\infty \frac{\sin(2 \pi k x)}{k}.</math>

• 根据Beatty定理，每个正无理数都可以通过高斯符號制造出一个整数集的分划。
• 最后，对于每个正整数 <math>k</math>，其在 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>為正整數，則

<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>為正數，則

<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>，有埃爾米特恆等式：

<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>，以下兩式可將上下取整函數互相轉化：

<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>，有：

<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>

上式算是一種「互反律」（reciprocity law），與§ 二次互反律有關。

應用

二次互反律

高斯給出二次互反律的第三個證明，經艾森斯坦修改後，有以下兩個主要步驟。

設<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>的二次特徵標，可以高斯符號表示，如：

<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>為質數当且仅当

<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>

則衹用取整、冪、四則運算可以寫出質數公式：

<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>

皆為質數。

若不疊代三次方函數，改為疊代以<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>

皆為質數。

以質數計算函數<math>\pi(x)</math>表示小於或等於<math>x</math>的質數個數。由威尔逊定理，可知

<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>時：

<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>

本小節的公式未有任何實際用途。

其它等式

• 对于所有实数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>

参考来源

• Crandall, Richard; Pomerance, Carl. Prime Numbers: A Computational Perspective. New York: Springer. 2001 [2022-02-06]. ISBN 978-0-387-94777-8. （原始内容存档于2022-04-09）. 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics. Reading Ma.: Addison-Wesley. 1994. ISBN 0-201-55802-5. 
• Hardy, G. H.; Wright, E. M. An Introduction to the Theory of Numbers (Fifth edition). Oxford: Oxford University Press. 1980. ISBN 978-0-19-853171-5. 
• Lemmermeyer, Franz. Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. 2000. ISBN 978-3-540-66957-9. 
• Ribenboim, Paulo. The New Book of Prime Number Records. New York: Springer. 1996. ISBN 978-0-387-94457-9. 

另见

截尾函數