Movatterモバイル変換

[0]ホーム
URL:

跳转到内容
维基百科自由的百科全书
搜索

取整函数

本页使用了标题或全文手工转换
维基百科，自由的百科全书
（重定向自取整）
下取整函数
上取整函数

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

常用的取整函数有两个，分别是下取整函数（英語：floor function）和上取整函数（ceiling function）。

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

[x]=max{n∈Z∣n≤x}.{\displaystyle [x]=\max \,\{n\in \mathbb {Z} \mid n\leq x\}.}

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

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

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

⌈x⌉=min{n∈Z∣x≤n}.{\displaystyle \lceil x\rceil =\min\{n\in \mathbb {Z} \mid x\leq n\}.}

举例来说，⌈3.633⌉=4{\displaystyle \lceil 3.633\rceil =4}，⌈56⌉=56{\displaystyle \lceil 56\rceil =56}，⌈−2⌉=−2{\displaystyle \lceil -2\rceil =-2}，⌈−2.263⌉=−2{\displaystyle \lceil -2.263\rceil =-2}。

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

性质

[编辑]

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

函數間之關係

[编辑]

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

⌊x⌋≤⌈x⌉,{\displaystyle \lfloor x\rfloor \leq \lceil x\rceil ,}

等號當且僅當x{\displaystyle x}為整數，即

⌈x⌉−⌊x⌋={0, 若  x∈Z,1, 若  x∉Z.{\displaystyle \lceil x\rceil -\lfloor x\rfloor ={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\1,&{\text{ 若 }}\ x\not \in \mathbb {Z} .\end{cases}}}

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

⌊n⌋=⌈n⌉=n.{\displaystyle \lfloor n\rfloor =\lceil n\rceil =n.}

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

⌊x⌋+⌈−x⌉=0,−⌊x⌋=⌈−x⌉,−⌈x⌉=⌊−x⌋.{\displaystyle {\begin{aligned}\lfloor x\rfloor +\lceil -x\rceil &=0,\\-\lfloor x\rfloor &=\lceil -x\rceil ,\\-\lceil x\rceil &=\lfloor -x\rfloor .\end{aligned}}}

且：

⌊x⌋+⌊−x⌋={0, 若  x∈Z,−1, 若  x∉Z,{\displaystyle \lfloor x\rfloor +\lfloor -x\rfloor ={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\-1,&{\text{ 若 }}\ x\not \in \mathbb {Z} ,\end{cases}}}
⌈x⌉+⌈−x⌉={0, 若  x∈Z,1, 若  x∉Z.{\displaystyle \lceil x\rceil +\lceil -x\rceil ={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\1,&{\text{ 若 }}\ x\not \in \mathbb {Z} .\end{cases}}}

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

{x}+{−x}={0, 若  x∈Z,1, 若  x∉Z.{\displaystyle \{x\}+\{-x\}={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\1,&{\text{ 若 }}\ x\not \in \mathbb {Z} .\end{cases}}}

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

⌊⌊x⌋⌋=⌊x⌋,⌈⌈x⌉⌉=⌈x⌉,{{x}}={x}.{\displaystyle {\begin{aligned}{\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{aligned}}}

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

⌊⌈x⌉⌋=⌈x⌉,⌈⌊x⌋⌉=⌊x⌋,{\displaystyle {\begin{aligned}{\Big \lfloor }\lceil x\rceil {\Big \rfloor }&=\lceil x\rceil ,\\{\Big \lceil }\lfloor x\rfloor {\Big \rceil }&=\lfloor x\rfloor ,\end{aligned}}}

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

商

[编辑]

若m{\displaystyle m}和n{\displaystyle n}為正整數，且n≠0{\displaystyle n\neq 0}，則

0≤{mn}≤1−1|n|.{\displaystyle 0\leq \left\{{\frac {m}{n}}\right\}\leq 1-{\frac {1}{|n|}}.}

若n{\displaystyle n}為正整數，則[3]

⌊x+mn⌋=⌊⌊x⌋+mn⌋,{\displaystyle \left\lfloor {\frac {x+m}{n}}\right\rfloor =\left\lfloor {\frac {\lfloor x\rfloor +m}{n}}\right\rfloor ,}
⌈x+mn⌉=⌈⌈x⌉+mn⌉.{\displaystyle \left\lceil {\frac {x+m}{n}}\right\rceil =\left\lceil {\frac {\lceil x\rceil +m}{n}}\right\rceil .}

若m{\displaystyle m}為正數，則[4]

n=⌈nm⌉+⌈n−1m⌉+⋯+⌈n−m+1m⌉,{\displaystyle 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 ,}
n=⌊nm⌋+⌊n+1m⌋+⋯+⌊n+m−1m⌋.{\displaystyle 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 .}

代m=2{\displaystyle m=2}，上式推出：

n=⌊n2⌋+⌈n2⌉.{\displaystyle n=\left\lfloor {\frac {n}{2}}\right\rfloor +\left\lceil {\frac {n}{2}}\right\rceil .}

更一般地，對正整數m{\displaystyle m}，有埃爾米特恆等式（英语：Hermite's identity）：[5]

⌈mx⌉=⌈x⌉+⌈x−1m⌉+⋯+⌈x−m−1m⌉,{\displaystyle \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 ,}
⌊mx⌋=⌊x⌋+⌊x+1m⌋+⋯+⌊x+m−1m⌋.{\displaystyle \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 .}

對於正整數m{\displaystyle m}，以下兩式可將上下取整函數互相轉化：[6]

⌈nm⌉=⌊n+m−1m⌋=⌊n−1m⌋+1,{\displaystyle \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,}
⌊nm⌋=⌈n−m+1m⌉=⌈n+1m⌉−1.{\displaystyle \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.}

對任意正整數m{\displaystyle m}和n{\displaystyle n}，有：[7]

∑k=1n−1⌊kmn⌋=(m−1)(n−1)+gcd(m,n)−12,{\displaystyle \sum _{k=1}^{n-1}\left\lfloor {\frac {km}{n}}\right\rfloor ={\frac {(m-1)(n-1)+\gcd(m,n)-1}{2}},}

作為特例，當m{\displaystyle m}和n{\displaystyle n}互質時，上式簡化為

∑k=1n−1⌊kmn⌋=12(m−1)(n−1).{\displaystyle \sum _{k=1}^{n-1}\left\lfloor {\frac {km}{n}}\right\rfloor ={\frac {1}{2}}(m-1)(n-1).}

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

⌊mn⌋+⌊2mn⌋+⋯+⌊(n−1)mn⌋=⌊nm⌋+⌊2nm⌋+⋯+⌊(m−1)nm⌋.{\displaystyle \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 .}

更一般地，對正整數m,n{\displaystyle m,n}，有

⌊xn⌋+⌊m+xn⌋+⌊2m+xn⌋+⋯+⌊(n−1)m+xn⌋=⌊xm⌋+⌊n+xm⌋+⌊2n+xm⌋+⋯+⌊(m−1)n+xm⌋.{\displaystyle {\begin{aligned}&\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{aligned}}}

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

應用

[编辑]

二次互反律

[编辑]

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

設p{\displaystyle p}、q{\displaystyle q}為互異奇質數，又設

m=p−12,{\displaystyle m={\frac {p-1}{2}},}n=q−12.{\displaystyle n={\frac {q-1}{2}}.}

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

(qp)=(−1)⌊qp⌋+⌊2qp⌋+⋯+⌊mqp⌋,{\displaystyle \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 },}

同樣

(pq)=(−1)⌊pq⌋+⌊2pq⌋+⋯+⌊npq⌋.{\displaystyle \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 }.}

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

⌊qp⌋+⌊2qp⌋+⋯+⌊mqp⌋+⌊pq⌋+⌊2pq⌋+⋯+⌊npq⌋=mn.{\displaystyle \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.}

總結上述兩步，得

(pq)(qp)=(−1)mn=(−1)p−12q−12.{\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{mn}=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.}

此即二次互反律。一些小整數模奇質數p{\displaystyle p}的二次特徵標，可以高斯符號表示，如：[10]

(2p)=(−1)⌊p+14⌋,{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\left\lfloor {\frac {p+1}{4}}\right\rfloor },}
(3p)=(−1)⌊p+16⌋.{\displaystyle \left({\frac {3}{p}}\right)=(-1)^{\left\lfloor {\frac {p+1}{6}}\right\rfloor }.}

質數公式

[编辑]

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

∑m=1∞(⌊nm⌋−⌊n−1m⌋)=2.{\displaystyle \sum _{m=1}^{\infty }\left(\left\lfloor {\frac {n}{m}}\right\rfloor -\left\lfloor {\frac {n-1}{m}}\right\rfloor \right)=2.}

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

α=∑m=1∞pmr−m2.{\displaystyle \alpha =\sum _{m=1}^{\infty }p_{m}r^{-m^{2}}.}

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

pn=⌊rn2α⌋−r2n−1⌊r(n−1)2α⌋.{\displaystyle p_{n}=\left\lfloor r^{n^{2}}\alpha \right\rfloor -r^{2n-1}\left\lfloor r^{(n-1)^{2}}\alpha \right\rfloor .}

類似還有米尔斯常数θ=1.3064…{\displaystyle \theta =1.3064\ldots }，使

⌊θ3⌋,⌊θ9⌋,⌊θ27⌋,…{\displaystyle \left\lfloor \theta ^{3}\right\rfloor ,\left\lfloor \theta ^{9}\right\rfloor ,\left\lfloor \theta ^{27}\right\rfloor ,\dots }

皆為質數。[13]

若不疊代三次方函數，改為疊代以2{\displaystyle 2}為㡳的指數函數，亦有ω=1.9287800…{\displaystyle \omega =1.9287800\ldots }使

⌊2ω⌋,⌊22ω⌋,⌊222ω⌋,…{\displaystyle \left\lfloor 2^{\omega }\right\rfloor ,\left\lfloor 2^{2^{\omega }}\right\rfloor ,\left\lfloor 2^{2^{2^{\omega }}}\right\rfloor ,\dots }

皆為質數。[13]

以質數計算函數π(x){\displaystyle \pi (x)}表示小於或等於x{\displaystyle x}的質數個數。由威尔逊定理，可知[14]

π(n)=∑j=2n⌊(j−1)!+1j−⌊(j−1)!j⌋⌋.{\displaystyle \pi (n)=\sum _{j=2}^{n}\left\lfloor {\frac {(j-1)!+1}{j}}-\left\lfloor {\frac {(j-1)!}{j}}\right\rfloor \right\rfloor .}

又或者，當n≥2{\displaystyle n\geq 2}時：[15]

π(n)=∑j=2n⌊1∑k=2j⌊⌊jk⌋kj⌋⌋.{\displaystyle \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 .}

本小節的公式未有任何實際用途。[16][17]

其它等式

[编辑]
  • 对于所有实数x，有：
⌊x2⌋=14((−1)⌊x⌋−1+2⌊x⌋){\displaystyle \left\lfloor {\frac {x}{2}}\right\rfloor ={\frac {1}{4}}((-1)^{\lfloor x\rfloor }-1+2\lfloor x\rfloor )}
⌊x3⌋=13(23sin⁡(2π3⌊x⌋+π3)−1+⌊x⌋){\displaystyle \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 )}

参考来源

[编辑]
  1. ^Ronald Graham,Donald Knuth andOren Patashnik（英语：Oren Patashnik）. "Concrete Mathematics". Addison-Wesley, 1999. Chapter 3, "Integer Functions".
  2. ^Iverson, Kenneth E. A Programming Language. Wiley. 1962. 
  3. ^Graham, Knuth & Patashnik 1994，第73頁.
  4. ^Graham, Knuth & Patashnik 1994，第85頁.
  5. ^Graham, Knuth & Patashnik 1994，p. 85 and Ex. 3.15.
  6. ^Graham, Knuth & Patashnik 1994，Ex. 3.12.
  7. ^7.07.1Graham, Knuth & Patashnik 1994，第94頁.
  8. ^Lemmermeyer 2000，§ 1.4, Ex. 1.32–1.33.
  9. ^Hardy & Wright 1980，§§ 6.11–6.13.
  10. ^Lemmermeyer 2000，第25頁.
  11. ^Crandall & Pomerance 2001，Ex. 1.3, p. 46，求和式的上限∞{\displaystyle \infty }可以換成n{\displaystyle n}。尚有一個等價的表述：n>1{\displaystyle n>1}為質數當且僅當∑m=1⌊n⌋(⌊nm⌋−⌊n−1m⌋)=1.{\displaystyle \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.}
  12. ^Hardy & Wright 1980，§ 22.3.
  13. ^13.013.1Ribenboim 1996，第186頁
  14. ^Ribenboim 1996，第181頁.
  15. ^Crandall & Pomerance 2001，Ex. 1.4, p. 46.
  16. ^Ribenboim 1996，第180頁（譯文）：「雖然該些公式毫不實用⋯⋯但邏輯學家希望清晰明白不同公理體系，如何推導出算術各方面，則或許與此有關⋯⋯」
  17. ^Hardy & Wright 1980，第344—345頁（譯文）：「若數α{\displaystyle \alpha }的準確值⋯⋯可以無關質數的方式表達，則該些公式之任一（或一切類似公式）的地位將截然不同。似乎沒有此種可能，但卻不能完全排除。」

另见

[编辑]

截尾函數

检索自“https://zh.wikipedia.org/w/index.php?title=取整函数&oldid=90496870”
分类：​
隐藏分类：​
[8]ページ先頭
©2009-2026 Movatter.jp