跳至內容

取整函數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
下取整函數
上取整函數

數學計算機科學中,取整函數是一類將實數映射到相近的整數函數[1]

常用的取整函數有兩個,分別是下取整函數(英語:floor function)和上取整函數ceiling function)。

下取整函數即為取底符號,在數學中一般記作或者或者,在計算機科學中一般記作floor(x),表示不超過x的整數中最大的一個。

舉例來說,。對於非負的實數,其下取整函數的值一般叫做它的整數部分取整部分。而叫做x小數部分。每個分數都可以表示成其整數部分與一個真分數的和,而實數的整數部分和小數部分是與此概念相應的拓延。

下取整函數的符號用方括號表示(),稱作高斯符號,首次出現是在卡爾·弗里德里希·高斯的數學著作《算術研究》。


上取整函數即為取頂符號在數學中一般記作,在計算機科學中一般記作ceil(x),表示不小於x的整數中最小的一個。

舉例來說,

計算機中的上取整函數和下取整函數的命名來自於英文ceiling(天花板)和floor(地板),1962年由肯尼斯·艾佛森於《A Programming Language》引入。[2]

性質

[編輯]

對於高斯符號,有如下性質。

  • 按定義:
    當且僅當x為整數時取等號。
  • 設x和n為正整數,則:
  • n為正整數時,有:
    其中表示除以的餘數。
  • 對任意的整數k和任意實數x
  • 一般的數值修約規則可以表述為將x映射到floor(x + 0.5);
  • 高斯符號不是連續函數,但是上半連續的。作為一個分段的常數函數,在其導數有定義的地方,高斯符號導數為零。
  • x為一個實數,n為整數,則由定義,nx當且僅當n ≤ floor(x)。
  • x是正數時,有:
  • 用高斯符號可以寫出若干個素數公式,但沒有什麼實際價值,見§ 質數公式
  • 對於非整數的x,高斯符號有如下的傅里葉級數展開:
  • 根據Beatty定理,每個正無理數都可以通過高斯符號製造出一個整數集的分劃
  • 最後,對於每個正整數k,其在 p 進制下的表示有 數位

函數間之關係

[編輯]

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

等號當且僅當為整數,即

實際上,上取整與下取整函數作用於整數,效果等同恆等函數

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

且:

至於小數部分,自變量取相反數會使小數部分變成關於1的「補數」:

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

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

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

[編輯]

為正整數,且,則

為正整數,則[3]

為正數,則[4]

,上式推出:

更一般地,對正整數,有埃爾米特恆等式英語Hermite's identity[5]

對於正整數,以下兩式可將上下取整函數互相轉化:[6]

對任意正整數,有:[7]

作為特例,當互質時,上式簡化為

此等式可以幾何方式證明。又由於右式關於對稱,可得

更一般地,對正整數,有

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

應用

[編輯]

二次互反律

[編輯]

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

為互異奇質數,又設

首先,利用高斯引理,證明勒讓德符號可表示為和式:

同樣

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

總結上述兩步,得

此即二次互反律。一些小整數模奇質數的二次特徵標,可以高斯符號表示,如:[10]

質數公式

[編輯]

下取整函數出現於若干刻畫質數的公式之中。舉例,因為整除時等於,否則為,所以正整數為質數當且僅當[11]

除表示質數的條件外,還可以寫出公式使其取值為質數。例如,記第個質數為,任選一個整數,然後定義實數

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

類似還有米爾斯常數,使

皆為質數。[13]

若不疊代三次方函數,改為疊代以為㡳的指數函數,亦有使

皆為質數。[13]

質數計算函數表示小於或等於的質數個數。由威爾遜定理,可知[14]

又或者,當時:[15]

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

其它等式

[編輯]
  • 對於所有實數x,有:
  • x為一個實數,n為整數,則
  • 對於兩個相反數的高斯符號,有:
如果x為整數,則
否則

參考來源

[編輯]
  1. ^ Ronald Graham, Donald Knuth and Oren 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.0 7.1 Graham, 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,求和式的上限可以換成。尚有一個等價的表述:為質數當且僅當
  12. ^ Hardy & Wright 1980,§ 22.3.
  13. ^ 13.0 13.1 Ribenboim 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頁(譯文):「若數的準確值⋯⋯可以無關質數的方式表達,則該些公式之任一(或一切類似公式)的地位將截然不同。似乎沒有此種可能,但卻不能完全排除。」

另見

[編輯]

截尾函數