取整函数

下取整函数

上取整函数

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

常用的取整函数有两个，分别是下取整函数（Template:Lang-en）和上取整函数（Template:Lang）。

下取整函数即為取底符號，在数学中一般记作$[x]$或者$\lfloor x\rfloor$或者$E(x)$，在计算机科学中一般记作floor(x)，表示不超过x的整数中最大的一个。

$[x]=\max \{n\in \mathbb{Z}\mid n\le x\}.$

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

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

上取整函数即為取頂符號在数学中一般记作$\lceil x\rceil$，在计算机科学中一般记作ceil(x)，表示不小于x的整数中最小的一个。

$\lceil x\rceil =\min \{n\in \mathbb{Z}\mid x\le n\}.$

举例来说，$\lceil 3.633\rceil =4$，$\lceil 56\rceil =56$，$\lceil -2\rceil =-2$，$\lceil -2.263\rceil =-2$。

计算机中的上取整函数和下取整函数的命名来自于英文的ceiling（天花板）和floor（地板），1962年由肯尼斯·艾佛森于《A Programming Language》引入。

性质

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

• 按定义：

  $[x]\le x<[x]+1$ 当且仅当x为整数时取等号。

• 设x和n为正整数，则：

  $\left[\frac{n}{x}\right]\ge \frac{n}{x}-\frac{x-1}{x}$

• 当n为正整数时，有：

  $\left[\frac{x}{n}\right]=\frac{x-xmodn}{n},$ 其中$xmodn$表示$x$除以$n$的餘數。

• 对任意的整数k和任意实数x，

  $[k+x]=k+[x].$

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

  $\left[2x\right]-2\left[x\right]⩽1$

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

  $[x]=x-\frac{1}{2}+\frac{1}{\pi }\sum _{k=1}^{\mathrm{\infty }}\frac{\sin (2\pi kx)}{k}.$

• 根据Beatty定理，每个正无理数都可以通过高斯符號制造出一个整数集的分划。
• 最后，对于每个正整数k，其在 p 进制下的表示有 $[{\log }_p(k)]+1$ 个数位。

函數間之關係

由上下取整函數的定義，可見

$\lfloor x\rfloor \le \lceil x\rceil ,$

等號當且僅當$x$為整數，即

$\lceil x\rceil -\lfloor x\rfloor =\{\begin{array}{cc}0,& \text{ 若 }x\in \mathbb{Z},\\ 1,& \text{ 若 }x\in ̸\mathbb{Z}.\end{array}$

實際上，上取整與下取整函數作用於整數$n$，效果等同恆等函數：

$\lfloor n\rfloor =\lceil n\rceil =n.$

自變量加負號，相當於將上取整與下取整互換，外面再加負號，即：

$\begin{array}{cc}\lfloor x\rfloor +\lceil -x\rceil & =0,\\ -\lfloor x\rfloor & =\lceil -x\rceil ,\\ -\lceil x\rceil & =\lfloor -x\rfloor .\end{array}$

且：

$\lfloor x\rfloor +\lfloor -x\rfloor =\{\begin{array}{cc}0,& \text{ 若 }x\in \mathbb{Z},\\ -1,& \text{ 若 }x\in ̸\mathbb{Z},\end{array}$

$\lceil x\rceil +\lceil -x\rceil =\{\begin{array}{cc}0,& \text{ 若 }x\in \mathbb{Z},\\ 1,& \text{ 若 }x\in ̸\mathbb{Z}.\end{array}$

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

$\{x\}+\{-x\}=\{\begin{array}{cc}0,& \text{ 若 }x\in \mathbb{Z},\\ 1,& \text{ 若 }x\in ̸\mathbb{Z}.\end{array}$

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

$\begin{array}{cc}\lfloor \lfloor x\rfloor \rfloor & =\lfloor x\rfloor ,\\ \lceil \lceil x\rceil \rceil & =\lceil x\rceil ,\\ \{\{x\}\}& =\{x\}.\end{array}$

而多個上取整與下取整依次疊代的效果，相當於最內層一個：

$\begin{array}{cc}\lfloor \lceil x\rceil \rfloor & =\lceil x\rceil ,\\ \lceil \lfloor x\rfloor \rceil & =\lfloor x\rfloor ,\end{array}$

因為外層取整函數實際衹作用在整數上，不帶來變化。

商

若$m$和$n$為正整數，且$n\ne 0$，則

$0\le \left\{\frac{m}{n}\right\}\le 1-\frac{1}{|n|}.$

若$n$為正整數，則Template:Sfn

$\lfloor \frac{x+m}{n}\rfloor =\lfloor \frac{\lfloor x\rfloor +m}{n}\rfloor ,$

$\lceil \frac{x+m}{n}\rceil =\lceil \frac{\lceil x\rceil +m}{n}\rceil .$

若$m$為正數，則Template:Sfn

$n=\lceil \frac{n}{m}\rceil +\lceil \frac{n-1}{m}\rceil +\dots +\lceil \frac{n-m+1}{m}\rceil ,$

$n=\lfloor \frac{n}{m}\rfloor +\lfloor \frac{n+1}{m}\rfloor +\dots +\lfloor \frac{n+m-1}{m}\rfloor .$

代$m=2$，上式推出：

$n=\lfloor \frac{n}{2}\rfloor +\lceil \frac{n}{2}\rceil .$

更一般地，對正整數$m$，有Template:Link-en：Template:Sfn

$\lceil mx\rceil =\lceil x\rceil +\lceil x-\frac{1}{m}\rceil +\dots +\lceil x-\frac{m-1}{m}\rceil ,$

$\lfloor mx\rfloor =\lfloor x\rfloor +\lfloor x+\frac{1}{m}\rfloor +\dots +\lfloor x+\frac{m-1}{m}\rfloor .$

對於正整數$m$，以下兩式可將上下取整函數互相轉化：Template:Sfn

$\lceil \frac{n}{m}\rceil =\lfloor \frac{n+m-1}{m}\rfloor =\lfloor \frac{n-1}{m}\rfloor +1,$

$\lfloor \frac{n}{m}\rfloor =\lceil \frac{n-m+1}{m}\rceil =\lceil \frac{n+1}{m}\rceil -1.$

對任意正整數$m$和$n$，有：Template:Sfn

$\sum _{k=1}^{n-1}\lfloor \frac{km}{n}\rfloor =\frac{(m-1)(n-1)+\gcd (m,n)-1}{2},$

作為特例，當$m$和$n$互質時，上式簡化為

$\sum _{k=1}^{n-1}\lfloor \frac{km}{n}\rfloor =\frac{1}{2}(m-1)(n-1).$

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

$\lfloor \frac{m}{n}\rfloor +\lfloor \frac{2m}{n}\rfloor +\dots +\lfloor \frac{(n-1)m}{n}\rfloor =\lfloor \frac{n}{m}\rfloor +\lfloor \frac{2n}{m}\rfloor +\dots +\lfloor \frac{(m-1)n}{m}\rfloor .$

更一般地，對正整數$m,n$，有

$\begin{array}{cc}& \lfloor \frac{x}{n}\rfloor +\lfloor \frac{m+x}{n}\rfloor +\lfloor \frac{2m+x}{n}\rfloor +\dots +\lfloor \frac{(n-1)m+x}{n}\rfloor \\ =& \lfloor \frac{x}{m}\rfloor +\lfloor \frac{n+x}{m}\rfloor +\lfloor \frac{2n+x}{m}\rfloor +\cdots +\lfloor \frac{(m-1)n+x}{m}\rfloor .\end{array}$

上式算是一種「互反律」（Template:Lang）Template:Sfn，與Template:Section link有關。

應用

二次互反律

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

設$p$、$q$為互異奇質數，又設

$m=\frac{p-1}{2},$ $n=\frac{q-1}{2}.$

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

$\left(\frac{q}{p}\right)=(-1{)}^{\lfloor \frac{q}{p}\rfloor +\lfloor \frac{2q}{p}\rfloor +\dots +\lfloor \frac{mq}{p}\rfloor },$

同樣

$\left(\frac{p}{q}\right)=(-1{)}^{\lfloor \frac{p}{q}\rfloor +\lfloor \frac{2p}{q}\rfloor +\dots +\lfloor \frac{np}{q}\rfloor }.$

其後，採用幾何論證，證明

$\lfloor \frac{q}{p}\rfloor +\lfloor \frac{2q}{p}\rfloor +\dots +\lfloor \frac{mq}{p}\rfloor +\lfloor \frac{p}{q}\rfloor +\lfloor \frac{2p}{q}\rfloor +\dots +\lfloor \frac{np}{q}\rfloor =mn.$

總結上述兩步，得

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{mn}=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}.$

此即二次互反律。一些小整數模奇質數$p$的二次特徵標，可以高斯符號表示，如：Template:Sfn

$\left(\frac{2}{p}\right)=(-1{)}^{\lfloor \frac{p+1}{4}\rfloor },$

$\left(\frac{3}{p}\right)=(-1{)}^{\lfloor \frac{p+1}{6}\rfloor }.$

質數公式

下取整函數出現於若干刻畫質數的公式之中。舉例，因為$\lfloor \frac{n}{m}\rfloor -\lfloor \frac{n-1}{m}\rfloor$在$m$整除$n$時等於$1$，否則為$0$，所以正整數$n$為質數当且仅当

$\sum _{m=1}^{\mathrm{\infty }}(\lfloor \frac{n}{m}\rfloor -\lfloor \frac{n-1}{m}\rfloor )=2.$

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

$\alpha =\sum _{m=1}^{\mathrm{\infty }}{p}_m{r}^{-m^2}.$

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

$p_n=\lfloor r^{n^2}\alpha \rfloor -r^{2n-1}\lfloor r^{(n-1{)}^2}\alpha \rfloor .$

類似還有米尔斯常数$\theta =1.3064\dots$，使

$\lfloor {\theta }^3\rfloor ,\lfloor {\theta }^9\rfloor ,\lfloor {\theta }^{27}\rfloor ,\dots$

皆為質數。

若不疊代三次方函數，改為疊代以$2$為㡳的指數函數，亦有$\omega =1.9287800\dots$使

$\lfloor 2^{\omega }\rfloor ,\lfloor 2^{2^{\omega }}\rfloor ,\lfloor 2^{2^{2^{\omega }}}\rfloor ,\dots$

皆為質數。

以質數計算函數$\pi (x)$表示小於或等於$x$的質數個數。由威尔逊定理，可知Template:Sfn

$\pi (n)=\sum _{j=2}^n\lfloor \frac{(j-1)!+1}{j}-\lfloor \frac{(j-1)!}{j}\rfloor \rfloor .$

又或者，當$n\ge 2$時：Template:Sfn

$\pi (n)=\sum _{j=2}^n\lfloor \frac{1}{\sum _{k=2}^j\lfloor \lfloor \frac{j}{k}\rfloor \frac{k}{j}\rfloor }\rfloor .$

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

其它等式

• 对于所有实数x，有：

$\lfloor \frac{x}{2}\rfloor =\frac{1}{4}((-1{)}^{\lfloor x\rfloor }-1+2\lfloor x\rfloor )$

$\lfloor \frac{x}{3}\rfloor =\frac{1}{3}(\frac{2}{\sqrt{3}}\sin (\frac{2\pi }{3}\lfloor x\rfloor +\frac{\pi }{3})-1+\lfloor x\rfloor )$

参考来源

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book

另见

截尾函数