取整函数

数学计算机科学中,取整函数是一类将实数映射到相近的整数函数[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页(译文):“若数 的准确值⋯⋯可以无关素数的方式表达,则该些公式之任一(或一切类似公式)的地位将截然不同。似乎没有此种可能,但却不能完全排除。”