檢視取整函數的原始碼

佇咧數學佮電腦科學中，'''取整函數'''是一類將實數對映到相倚的整數的函數。

捷用的取整函數有兩个，分別是'''下取整函數'''（英語：floor function）和'''上取整函數'''（ceiling function）。

'''下取整函數'''即為'''取底符號'''，佇數學中一般的記作 $ [x] $ 抑是講 $ \ lfloor x \ rfloor $ 抑是講 $ E ( x ) $，佇電腦科學中一般記作 floor ( _ x _ )，表示無超過 _ x _ 的整數內底上大的一个。


: $ [x]=\ max \ , \ { n \ in \ mathbb { Z } \ mid n \ leq x \ } . $

比如講伊，$ [三孵六三三]=三 $，$ [五十六]=五十六 $，$ [鋪二]=鋪二 $，$ [抹二鋪二六三]=ma三 $。對非負的實數，其下取整函數的值一般號做伊的'''整數部份'''抑是'''取整部份'''。而且 $ x-[x] $ 叫做 _ x _ 的小數部份。每一个分數攏會當表示成其整數的部份佮一个真分數的佮，實數的整數部份佮小數部份是佮此概念相應的楦延。

下取整函數的符號用方括號表示（$ [x] $）， 這號做'''高斯符號'''，首擺出現是佇卡爾 ・ 被里德里希望 ・ 高斯的數學著作《算術研究》。


'''上取整函數'''即為'''取頂符號'''佇數學中一般的記作 $ \ lceil x \ rceil $，佇電腦科學中一般記作 ceil ( _ x _ )，表示無細膩 _ x _ 的整數內底上細的一个。


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

比如講伊，$ \ lceil 三孵六三三 \ rceil=四 $，$ \ lceil 五十六 \ rceil=五十六 $，$ \ lceil 鋪二 \ rceil=鋪二 $，$ \ lceil 抹二鋪二六三 \ rceil=鋪二 $。

電腦內面的上取整函數和下取整函數的號名來自英文的 _ ceiling _（天篷）和 _ floor _（塗跤）， 一九六二年由肯尼斯 ・ 艾佛森於《A Programming Language》引入來。

==性質==

對高斯符號，有如下性質。

* 照定義：


: $ [x] \ leq x < [x] + 一 $ 若是唯一 _ x _ 為整數時號等號。
* 設 x 和 n 為正實數，著：


: $ \ left [{ \ frac { n } { x } } \ right] \ geq { \ frac { n } { x } }-{ \ frac { x 影一 } { x } } $
* 當 _ n _ 為當整數的時陣，有：


: $ \ left \ lbrack { \ frac { x } { n } } \ right \ rbrack={ \ frac { x-x { \ bmod { n } } } { n } } , $ 其中 $ x { \ bmod { n } } $ 表示 $ x $ 除以 $ n $ 的餘數。
* 對任意的整數 _ k _ 佮任意實數 _ x _，


: $ [{ k + x }]=k + [x] . $
* 一般的數值修約規則會當表示對將 _ x _ 嘿映到 floor ( _ x _ + 空七五 )；
* 高斯符號毋是連紲函數，但是頂半連紲的。成做一个分段的常數函數，佇其導數有定義的所在，高斯符號導數為零。
* 設 _ x _ 為一个實數，_ n _ 為整數，則由定義，_ n _ ≤ _ x _ 若是唯一 _ n _ ≤ floor ( _ x _ )。
* 當 _ x _ 是正數的時陣，有：


: $ \ left \ lbrack 二 x \ right \ rbrack 鋪二 \ left \ lbrack x \ right \ rbrack \ leqslant 一 $
* 用高斯符號會當寫出若干個質數公式，但是無啥物實際的價值，見 §  質數公式。
* 對非整數的 _ x _，高斯符號有如下的傅立葉級數展開：


: $ [x]=x-{ \ frac { 一 } { 二 } } + { \ frac { 一 } { \ pi } } \ sum _ { k=一 } ^ { \ infty } { \ frac { \ sin ( 二 \ pi kx ) } { k } } . $
* 根據 Beatty 定理，每一个正無理數攏會當通過高斯符號製造出一个整數集的分劃。
* 最後咧，著每一个正整數 _ k _，其在 p 進位下的表示有 $ [\ log _ { p } ( k )] + 一 $ 個數位。

===函數間之關係===

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


: $ \ lfloor x \ rfloor \ leq \ lceil x \ rceil , $

等號若而且唯若 $ x $ 為整數，即


: $ \ lceil x \ rceil-\ lfloor x \ rfloor={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } . \ end { cases } } $

實際上，頂取整佮下取整函數作用佇整數 $ n $，效果等同恆等函數：


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

自變數加負號，等於是共頂取整佮下取整相換，外口閣加負號，即：


: $ { \ begin { aligned } \ lfloor x \ rfloor + \ lceil-x \ rceil &=零 , \ \-\ lfloor x \ rfloor &=\ lceil-x \ rceil , \ \-\ lceil x \ rceil &=\ lfloor-x \ rfloor . \ end { aligned } } $

而且：


: $ \ lfloor x \ rfloor + \ lfloor-x \ rfloor={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 影一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } , \ end { cases } } $


: $ \ lceil x \ rceil + \ lceil-x \ rceil={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } . \ end { cases } } $

若小數部份 $ \ { x \ }=x-\ lfloor x \ rfloor $，自變數取顛倒反數會使小數部份變做是關於一的「補數」：


: $ \ { x \ } + \ {-x \ }={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } . \ end { cases } } $

上取整、硩規下、小數部份攏為冪等等函數，即函數疊代兩改的結果等於家己：


: $ { \ 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 } } $

若濟上取整和下取整依照相疊代的效果，不止仔成上內層一个：


: $ { \ 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 $ 和 $ n $ 為正整數，而且 $ n \ neq 零 $，著


: $ 零 \ leq \ left \ { { \ frac { m } { n } } \ right \ } \ leq 一-{ \ frac { 一 } { | n | } } . $

若是 $ n $ 為正整數，著


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


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

若是 $ m $ 為正數，著


: $ n=\ left \ lceil { \ frac { n } { m } } \ right \ rceil + \ left \ lceil { \ frac { n 影一 } { m } } \ right \ rceil + \ dots + \ left \ lceil { \ frac { n-m + 一 } { m } } \ right \ rceil , $


: $ n=\ left \ lfloor { \ frac { n } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { n + 一 } { m } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { n + m 影一 } { m } } \ right \ rfloor . $

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


: $ n=\ left \ lfloor { \ frac { n } { 二 } } \ right \ rfloor + \ left \ lceil { \ frac { n } { 二 } } \ right \ rceil . $

閣較一般，著正整數 $ m $，有埃爾米特恆等式：


: $ \ lceil mx \ rceil=\ left \ lceil x \ right \ rceil + \ left \ lceil x-{ \ frac { 一 } { m } } \ right \ rceil + \ dots + \ left \ lceil x-{ \ frac { m 影一 } { m } } \ right \ rceil , $


: $ \ lfloor mx \ rfloor=\ left \ lfloor x \ right \ rfloor + \ left \ lfloor x + { \ frac { 一 } { m } } \ right \ rfloor + \ dots + \ left \ lfloor x + { \ frac { m 影一 } { m } } \ right \ rfloor . $

著正整數 $ m $，以下兩式會當將頂下取整函數互相轉化：


: $ \ left \ lceil { \ frac { n } { m } } \ right \ rceil=\ left \ lfloor { \ frac { n + m 影一 } { m } } \ right \ rfloor=\ left \ lfloor { \ frac { n 影一 } { m } } \ right \ rfloor + 一 , $


: $ \ left \ lfloor { \ frac { n } { m } } \ right \ rfloor=\ left \ lceil { \ frac { n-m + 一 } { m } } \ right \ rceil=\ left \ lceil { \ frac { n + 一 } { m } } \ right \ rceil 影一 . $

著任意正整數 $ m $ 和 $ n $，有：


: $ \ sum _ { k=一 } ^ { n 影一 } \ left \ lfloor { \ frac { km } { n } } \ right \ rfloor={ \ frac { ( m 影一 ) ( n 影一 ) + \ gcd ( m , n ) 影一 } { 二 } } , $

做特別，當 $ m $ 和 $ n $ 互質的時陣，上式簡化為


: $ \ sum _ { k=一 } ^ { n 影一 } \ left \ lfloor { \ frac { km } { n } } \ right \ rfloor={ \ frac { 一 } { 二 } } ( m 影一 ) ( n 影一 ) . $

這个等式會當做幾方式證明。閣因為正式有關於 $ m $、$ n $ 對稱，可得


: $ \ left \ lfloor { \ frac { m } { n } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 m } { n } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { ( n 影一 ) m } { n } } \ right \ rfloor=\ left \ lfloor { \ frac { n } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 n } { m } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { ( m 影一 ) n } { m } } \ right \ rfloor . $

閣較一般，著正整數 $ m , n $，有


: $ { \ begin { aligned } & \ left \ lfloor { \ frac { x } { n } } \ right \ rfloor + \ left \ lfloor { \ frac { m + x } { n } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 m + x } { n } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { ( n 影一 ) m + x } { n } } \ right \ rfloor \ \=& \ left \ lfloor { \ frac { x } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { n + x } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 n + x } { m } } \ right \ rfloor + \ cdots + \ left \ lfloor { \ frac { ( m 影一 ) n + x } { m } } \ right \ rfloor . \ end { aligned } } $

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

==應用==

===二次互反律===

高斯予出兩改互反律的第三个證明，經過艾森斯坦修改了後，有以下兩个主要步數。

設 $ p $、$ q $ 替互異奇質數，閣設


: $ m={ \ frac { p 影一 } { 二 } } , $ $ n={ \ frac { q 影一 } { 二 } } . $

首先，利用高斯引理，證明勒壤得符號會當表示做和式：


: $ \ left ( { \ frac { q } { p } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { q } { p } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 q } { p } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { mq } { p } } \ right \ rfloor } , $

仝款


: $ \ left ( { \ frac { p } { q } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { p } { q } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 p } { q } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { np } { q } } \ right \ rfloor } . $

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


: $ \ left \ lfloor { \ frac { q } { p } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 q } { p } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { mq } { p } } \ right \ rfloor + \ left \ lfloor { \ frac { p } { q } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 p } { q } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { np } { q } } \ right \ rfloor=mn . $

總結上術兩步，得


: $ \ left ( { \ frac { p } { q } } \ right ) \ left ( { \ frac { q } { p } } \ right )=( 影一 ) ^ { mn }=( 影一 ) ^ { { \ frac { p 影一 } { 二 } } { \ frac { q 影一 } { 二 } } } . $

這馬二改互反律。一寡仔細整數模奇質數 $ p $ 的兩改特徵標，會當高斯符號表示，如：


: $ \ left ( { \ frac { 二 } { p } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { p + 一 } { 四 } } \ right \ rfloor } , $


: $ \ left ( { \ frac { 三 } { p } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { p + 一 } { 六 } } \ right \ rfloor } . $

===質數公式===

下整函數出現佇若干焦刻畫質數的公式內底。舉例，因為乎 $ \ left \ lfloor { \ frac { n } { m } } \ right \ rfloor-\ left \ lfloor { \ frac { n 影一 } { m } } \ right \ rfloor $ 佇咧 $ m $ 整除 $ n $ 時等於 $ 一 $，抑無來做 $ 零 $，所以正整數 $ n $ 為質數若是唯若


: $ \ sum _ { m=一 } ^ { \ infty } \ left ( \ left \ lfloor { \ frac { n } { m } } \ right \ rfloor-\ left \ lfloor { \ frac { n 影一 } { m } } \ right \ rfloor \ right )=二 . $

除表示質數條件以外，閣會當寫出公式使其取值做質數。比如講，記第 $ n $ 個質數為 $ p _ { n } $，任選一个整數 $ r > 一 $，然後定義實數 $ \ alpha $ 為


: $ \ alpha=\ sum _ { m=一 } ^ { \ infty } p _ { m } r ^ {-m ^ { 二 } } . $

是使用取整、冪、四則運算會當寫出質數公式：


: $ p _ { n }=\ left \ lfloor r ^ { n ^ { 二 } } \ alpha \ right \ rfloor-r ^ { 二 n 影一 } \ left \ lfloor r ^ { ( n 影一 ) ^ { 二 } } \ alpha \ right \ rfloor . $

類似閣有米爾斯常數 $ \ theta=一孵三空六四 \ ldots $，使


: $ \ left \ lfloor \ theta ^ { 三 } \ right \ rfloor , \ left \ lfloor \ theta ^ { 九 } \ right \ rfloor , \ left \ lfloor \ theta ^ { 二十七 } \ right \ rfloor , \ dots $

攏為質數。

若無三擺的函數，改做疊代以 $ 二 $ 為著的指數函數，亦有 $ \ omega=一孵九二八七八空空 \ ldots $ 使


: $ \ left \ lfloor 二 ^ { \ omega } \ right \ rfloor , \ left \ lfloor 二 ^ { 二 ^ { \ omega } } \ right \ rfloor , \ left \ lfloor 二 ^ { 二 ^ { 二 ^ { \ omega } } } \ right \ rfloor , \ dots $

攏為質數。

以質數計算函數 $ \ pi ( x ) $ 表示細於抑是等於 $ x $ 的質數個數。由威爾遴定理，可知


: $ \ pi ( n )=\ sum _ { j=二 } ^ { n } \ left \ lfloor { \ frac { ( j 影一 ) ! + 一 } { j } }-\ left \ lfloor { \ frac { ( j 影一 ) ! } { j } } \ right \ rfloor \ right \ rfloor . $

閣抑是講，當 $ n \ geq 二 $ 時：


: $ \ pi ( n )=\ sum _ { j=二 } ^ { n } \ left \ lfloor { \ frac { 一 } { \ sum _ { k=二 } ^ { j } \ left \ lfloor \ left \ lfloor { \ frac { j } { k } } \ right \ rfloor { \ frac { k } { j } } \ right \ rfloor } } \ right \ rfloor . $

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

==其他的等式==

* 對所有的實數 _ x _，有：


: $ \ left \ lbrack { \ frac { x } { 二 } } \ right \ rbrack={ \ frac { 一 } { 四 } } ( ( 影一 ) ^ { [x] } 影一 + 二 [x] ) $


: $ \ left \ lbrack { \ frac { x } { 三 } } \ right \ rbrack={ \ frac { 鋪二 } { \ sqrt { 三 } } } \ sin ( { \ frac { 二 \ pi } { 三 } } [x] + { \ frac { \ pi } { 三 } } ) + 一 $
* 設 _ x _ 為一个實數，_ n _ 為整數，著


: $ \ sum _ { k=零 } ^ { n 影一 } E ( x + { \ frac { k } { n } } )=E ( nx ) $


: $ E ( { \ frac { 一 } { n } } E ( nx ) )=E ( x ) $

* 對兩个倒反的高斯符號，有：


: 若是 x 為整數，著 $ E ( x ) + E (-x )=零 $


: 抑無 $ E ( x ) + E (-x )=影一 $

==參考來源==

* Crandall , Richard ; Pomerance , Carl . Prime Numbers : A Computational Perspective . New York : Springer . 兩千空一 [二千空二十二孵二孵六] . ISBN 空九三百八十七石九九五四千七百七十七石九 .（原始內容存檔佇兩千空二十二抹四鋪九）.
* Graham , Ronald L . ; Knuth , Donald E . ; Patashnik , Oren . Concrete Mathematics . Reading Ma . : Addison-Wesley . 一千九百九十四 . ISBN  空九二百空一四五五千八百空二五 .
* Hardy , G . H . ; Wright , E . M . An Introduction to the Theory of Numbers ( Fifth edition ) . Oxford : Oxford University Press . 一千九百八十 . ISBN  九百七十八八八十知知三千一百七十一孵五 .
* Lemmermeyer , Franz . Reciprocity Laws : from Euler to Eisenstein . Berlin : Springer . 兩千 . ISBN  三石五百四十五六鋪六千九百五十七石四 .
* Ribenboim , Paulo . The New Book of Prime Number Records . New York : Springer . 九百九十六 . ISBN  空九三百八十七石九九五四千四百五十七石五 .

[[分類: 待校正]]