本文主要分析C++环境下的偏移截断法。当然,核心的逻辑对于其他语言也适用,本文仅以C++举例。C++的强制转型取整为去尾转型,即抛弃所有小数位数。基于此,我们可以讨论基于偏移的截断。
本文尽力做到通俗且严谨,如有疏漏还望大佬轻喷,不吝赐教!
一、简单解答
法1. 四舍五入的情况(采用实数的规范小数表示证明)
特殊地,我们先考虑四舍五入的情况。
(1) 考虑正数情况
对于正数A.49和B.51我们期望得到A和(B+1)。为得到我们的期望,我们需要至多能给A加0.51,至少要给B加0.49。即,我们至多能给A加(1-0.49),至少要给B加(1-0.51)。我们需要加入的偏移量Δ应满足(1-0.51)<Δ<(1-0.49)。
我们考虑 , 取整为 , 取整为 . 在这种条件下,我们的Δ应满足 .
至此我们可以选择三种方法:
法1.1: 极限的保不等式性质(等价于夹逼定理)
由极限的保不等式性质,对左右两侧不等式分别求极限,可得 , .
考察两个式子的极限,发现
则有 .
法1.2: 单调性
我们可研究不等式两边的单调性,发现 单调递增, 单调递减。
考察两个式子的极限,发现
由于 对 成立,则取 , 有 , 则 .
法1.3: 不等式+闭区间套定理
为了构造闭区间以满足区间套定理的要求,我们将开区间放缩为闭区间(这是充分的),由此可得
进而我们可以发现 .
记 , 则 满足下列条件:
可见 是一个闭区间套.
由区间套定理, 存在唯一的实数 , 使得
考察两个式子的极限,发现
则有唯一实数 , 即 .
(2) 考虑负数情况
对于负数-A.49和-B.51我们期望得到-A和-(B+1)。直接取C=-(-A.49)=A.49, D=-(-B.51)=B.51。则注意到在情况(1)中,我们可得C和D在Δ=0.5时有结果分别为A与B+1。则直接全体取反,可得Δ=-0.5时,满足四舍五入的要求。
法2. 四舍五入的情况(采用ε语言证明)
上文我们直观地感受了一下大概的情况,现在我们进行严谨的考虑。
(1) 考虑正数情况
我们考虑 , 取整为 , 取整为 . 在这种条件下,我们的Δ应满足 , 即 .
至此我们选择下列两种方法:
法2.1: 极限的保不等式性质(等价于夹逼定理)
由于 , 则对不等式两端同取 的极限,则有 . 进而有
法2.2: 不等式引理+反证法
先考虑不等式的左侧: .
根据引理 , 有
考虑不等式的右侧: . 考虑下列命题:
采用反证法: 假设 , 则 , 与题设 矛盾!故有 成立! 再由 , 可得 .
(2) 考虑负数情况
考虑 , 对于负数-A-0.5+ε和-B-0.5-ε我们期望得到-A和-(B+1)。直接取C=-(-A-0.5+ε)=A+0.5-ε, D=-(-B-0.5-ε)=B+0.5+ε。则注意到在情况(1)中,我们可得C和D在Δ=0.5时有结果分别为A与B+1。则直接全体取反,可得Δ=-0.5时,满足四舍五入的要求。
n舍n+1入的情况
上文中我们对四舍五入的情况给出了5种证明方法,此处我们仅使用ε语言证明+极限的保不等式性质(等价于夹逼定理)证明,其他方法同理。
(1) 考虑正数情况
我们考虑 , 取整为 , 取整为 . 在这种条件下,我们的Δ应满足 , 即 .
由于 , 则对不等式两端同取 的极限,则有 . 进而有
(2) 考虑负数情况
考虑 , 对于负数-A-0.1(n+1)+ε和-B-0.1(n+1)-ε我们期望得到-A和-(B+1)。直接取C=-(-A-0.1(n+1)+ε)=A+0.1(n+1)-ε, D=-(-B-0.1(n+1)-ε)=B+0.1(n+1)+ε。则注意到在情况(1)中,我们可得C和D在Δ=0.9-0.1n时有结果分别为A与B+1。则直接全体取反,可得Δ=-(0.9-0.1n)时,满足n舍n+1入的要求。
二、复杂解答
定义
在详细的讨论开始前,我们先进行如下定义:
-
定义截断算子: . 该算子的物理意义为:抹除实数x的小数部分,仅保留整数。
-
定义取整准则: 考虑实数 , 其整数部分为 , 小数部分为 . 即满足 . 定义”n舍n+1入”的进位阈值为 . 则我们期望的取整函数 应满足下列条件:
-
定义偏移量: 考虑偏移量 , 使得
解答
为找到偏移量 , 进行下列操作:
(1) 考虑正数域
由于在正数域下,可得:
又由底函数性质 , 可得:
欲使阈值点 恰好成为进位临界点,则应有:
即得 , 则有唯一解为:
(2) 考虑负数域
考虑负数 , 其中 .
由于在复数域下,可得:
即有
令 , 则有
则由情况(1),可得 , 进而有:
结论
我们可以得到在n舍n+1入的情况下,偏移量为Δ=1-0.1(n+1)=0.9-0.1n. 由此我们可以快速设计n舍n+1入算法: static_cast<int>(a+(a==0?0:(0.9-0.1*n)*(a>0?1:(-1)))).
考虑到-0.0的存在,我们需要将a==0时的情况改为0.0f: static_cast<int>(a+(a==0?0.0f:(0.9-0.1*n)*(a>0?1:(-1))))
由于计算机存在精度损失,我们需要考虑以下情况:
为修正精度丢失所带来的影响,我们可以引入1e-9项,这使得丢失的精度仍然可以跨过static_cast<int>的阈值。
进而可以变为如下形式: static_cast<int>( a + ( a == 0 ? 0.0f : ( 0.9 - 0.1 * n + 1e-9 ) * ( a > 0 ? 1 : -1))).
特别地,针对四舍五入的情况,可以得到static_cast<int>( a + ( a == 0 ? 0.0f : ( 0.5 + 1e-9 ) * ( a > 0 ? 1 : -1))).
更进一步地,如果能确定数据均为正数或负数,可直接略去三目运算符。
优势和劣势
- 该方法在通常情况下会比
round()函数更快,但由于该语句中三目运算符产生的分支,如果输入的数据中大量出现正负交替的现象,则会由于CPU分支预测器的失效导致严重的性能抖动。 - 可能存在溢出风险,这需要开发者进行额外的注意(尽管
round()函数也会出现溢出就是了)。