2163 字
11 分钟
基于偏移截断法的n舍n+1入简单数学分析

本文主要分析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)。

我们考虑 ∀k∈N∗\forall k\in \mathbb{N}^* , A.50−10−k<A.50A.50-10^{-k}<A.50 取整为 AA , B.50+10−k>B.50B.50+10^{-k}>B.50 取整为 B+1B+1 . 在这种条件下,我们的Δ应满足 1−(0.5+10−k)≤Δ<1−(0.5−10−k)1-\left( 0.5+10^{-k} \right) \leq\Delta <1-\left( 0.5-10^{-k} \right) .

至此我们可以选择三种方法:

法1.1: 极限的保不等式性质(等价于夹逼定理)#

由极限的保不等式性质,对左右两侧不等式分别求极限,可得 lim⁡k→∞[1−(0.5+10−k)]≤Δ\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5+10^{-k} \right) \right] \leq \Delta , Δ≤lim⁡k→∞[1−(0.5−10−k)]\Delta \leq \lim_{k\rightarrow \infty} \left[ 1-\left( 0.5-10^{-k} \right) \right].

考察两个式子的极限,发现 lim⁡k→∞[1−(0.5+10−k)]=lim⁡k→∞[1−(0.5−10−k)]=0.5\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5+10^{-k} \right) \right] =\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5-10^{-k} \right) \right] =0.5

则有 Δ=0.5\Delta=0.5 .

法1.2: 单调性#

我们可研究不等式两边的单调性,发现 1−(0.5+10−k)1-\left( 0.5+10^{-k} \right) 单调递增, 1−(0.5−10−k)1-\left( 0.5-10^{-k} \right) 单调递减。

考察两个式子的极限,发现 lim⁡k→∞[1−(0.5+10−k)]=lim⁡k→∞[1−(0.5−10−k)]=0.5\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5+10^{-k} \right) \right] =\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5-10^{-k} \right) \right] =0.5

由于 1−(0.5+10−k)≤Δ<1−(0.5−10−k)1-\left( 0.5+10^{-k} \right) \leq\Delta <1-\left( 0.5-10^{-k} \right) 对 ∀k∈N∗\forall k\in \mathbb{N}^* 成立,则取 k→∞k \rightarrow \infty, 有 0.5=lim⁡k→∞[1−(0.5+10−k)]≤Δ≤lim⁡k→∞[1−(0.5−10−k)]=0.50.5=\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5+10^{-k} \right) \right] \leq \Delta \leq \lim_{k\rightarrow \infty} \left[ 1-\left( 0.5-10^{-k} \right) \right] =0.5, 则 Δ=0.5\Delta=0.5 .

法1.3: 不等式+闭区间套定理#

为了构造闭区间以满足区间套定理的要求,我们将开区间放缩为闭区间(这是充分的),由此可得 1−(0.5+10−k)≤Δ≤1−(0.5−10−k)1-\left( 0.5+10^{-k} \right) \leq\Delta \leq 1-\left( 0.5-10^{-k} \right)

进而我们可以发现 Δ∈[1−(0.5+10−k),1−(0.5−10−k)]\Delta \in \left[ 1-\left( 0.5+10^{-k} \right) ,1-\left( 0.5-10^{-k} \right) \right] .

记 an=1−(0.5+10−k),bn=1−(0.5−10−k)a_n=1-\left( 0.5+10^{-k} \right) , b_n=1-\left( 0.5-10^{-k} \right) , 则 {[ak,bk]}\left\{ \left[ a_k,b_k \right] \right\} 满足下列条件:

  1. ∀k,[ak+1,bk+1]⊂[ak,bk]\forall k, \left[ a_{k+1},b_{k+1} \right] \subset \left[ a_k,b_k \right]
  2. lim⁡k→∞(bk−ak)=lim⁡k→∞(2×10−k)=0\lim_{k\rightarrow \infty} \left( b_k-a_k \right) =\lim_{k\rightarrow \infty} \left( 2\times 10^{-k} \right) =0

可见 {[ak,bk]}k=1∞\left\{ \left[ a_k,b_k \right] \right\} _{k=1}^{\infty} 是一个闭区间套.

由区间套定理, 存在唯一的实数 ξ\xi , 使得 ξ∈[ak,bk]\xi \in \left[ a_k,b_k\right]

考察两个式子的极限,发现 lim⁡k→∞[1−(0.5+10−k)]=lim⁡k→∞[1−(0.5−10−k)]=0.5\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5+10^{-k} \right) \right] =\lim_{k\rightarrow \infty} \left[ 1-\left( 0.5-10^{-k} \right) \right] =0.5

则有唯一实数 ξ=0.5\xi=0.5 , 即 Δ=0.5\Delta=0.5 .

(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) 考虑正数情况#

我们考虑 ∀n∈N∗,ε>0\forall n\in \mathbb{N}^*, \varepsilon>0 , A.50−ε<A.50A.50-\varepsilon<A.50 取整为 AA , B.50+ε>B.50B.50+\varepsilon>B.50 取整为 B+1B+1 . 在这种条件下,我们的Δ应满足 1−(0.5+ε)≤Δ<1−(0.5−ε)1-\left( 0.5+\varepsilon \right) \leq\Delta <1-\left( 0.5-\varepsilon \right) , 即 0.5−ε≤Δ≤0.5+ε0.5-\varepsilon \leq \Delta \leq 0.5+\varepsilon .

至此我们选择下列两种方法:

法2.1: 极限的保不等式性质(等价于夹逼定理)#

由于 ∀ε>0,均有0.5−ε≤Δ<0.5+ε\forall \varepsilon >0, \text{均有}0.5-\varepsilon \leq \Delta <0.5+\varepsilon , 则对不等式两端同取 ε→0\varepsilon\rightarrow 0 的极限,则有 lim⁡ε→0+(0.5−ε)≤Δ≤lim⁡ε→0+(0.5+ε)\lim_{\varepsilon \rightarrow 0^+} \left( 0.5-\varepsilon \right) \leq \Delta \leq \lim_{\varepsilon \rightarrow 0^+} \left( 0.5+\varepsilon \right) . 进而有 Δ=0.5\Delta=0.5

法2.2: 不等式引理+反证法#

先考虑不等式的左侧: 0.5−ε≤Δ0.5-\varepsilon \leq \Delta .

根据引理 若∀ε>0,均有a<b+ε,则a≤b\text{若}\forall \varepsilon >0, \text{均有}a<b+\varepsilon , \text{则}a\le b, 有 0.5≤Δ0.5 \leq \Delta

考虑不等式的右侧: Δ≤0.5+ε\Delta \leq 0.5+\varepsilon. 考虑下列命题: ∀ε>0,若Δ+ε<0.5,则Δ≤0.5\forall \varepsilon >0, \text{若}\Delta +\varepsilon <0.5, \text{则}\Delta \leq 0.5

采用反证法: 假设 Δ>0.5\Delta >0.5 , 则 Δ+ε>0.5+ε\Delta +\varepsilon >0.5+\varepsilon , 与题设 Δ+ε<0.5\Delta +\varepsilon <0.5 矛盾!故有 Δ≤0.5\Delta \leq 0.5 成立! 再由 0.5≤Δ0.5 \leq \Delta , 可得 Δ=0.5\Delta=0.5 .

(2) 考虑负数情况#

考虑 ∀ε>0\forall \varepsilon>0 , 对于负数-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) 考虑正数情况#

我们考虑 ∀n∈N∗,ε>0\forall n\in \mathbb{N}^*, \varepsilon>0 , A+0.1(n+1)−ε<A+0.1(n+1)A+0.1(n+1)-\varepsilon<A+0.1(n+1) 取整为 AA , B+0.1(n+1)+ε>B+0.1(n+1)B+0.1(n+1)+\varepsilon>B+0.1(n+1) 取整为 B+1B+1 . 在这种条件下,我们的Δ应满足 1−(0.1(n+1)+ε)≤Δ<1−(0.1(n+1)−ε)1-\left( 0.1(n+1)+\varepsilon \right) \leq\Delta <1-\left( 0.1(n+1)-\varepsilon \right) , 即 0.9−0.1n−ε≤Δ≤0.9−0.1n+ε0.9-0.1n-\varepsilon \leq \Delta \leq 0.9-0.1n+\varepsilon .

由于 ∀ε>0,均有0.9−0.1n−ε≤Δ≤0.9−0.1n+ε\forall \varepsilon >0, \text{均有}0.9-0.1n-\varepsilon \leq \Delta \leq 0.9-0.1n+\varepsilon , 则对不等式两端同取 ε→0\varepsilon\rightarrow 0 的极限,则有 lim⁡ε→0+(0.9−0.1n−ε)≤Δ≤lim⁡ε→0+(0.9−0.1n+ε)\lim_{\varepsilon \rightarrow 0^+} \left( 0.9-0.1n-\varepsilon \right) \leq \Delta \leq \lim_{\varepsilon \rightarrow 0^+} \left( 0.9-0.1n+\varepsilon \right) . 进而有 Δ=0.9−0.1n\Delta=0.9-0.1n

(2) 考虑负数情况#

考虑 ∀ε>0\forall \varepsilon>0 , 对于负数-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入的要求。

二、复杂解答#

定义#

在详细的讨论开始前,我们先进行如下定义:

  1. 定义截断算子: Tr(x)=sgn(x)⋅⌊∣x∣⌋Tr\left( x \right) =sgn \left( x \right) \cdot \lfloor \left| x \right| \rfloor . 该算子的物理意义为:抹除实数x的小数部分,仅保留整数。

  2. 定义取整准则: 考虑实数 X∈RX\in \mathbb{R} , 其整数部分为 II , 小数部分为 f∈[0,1)f\in \left[ 0,1 \right) . 即满足 ∣X∣=I+f\left| X \right|=I+f . 定义”n舍n+1入”的进位阈值为 T∈[0,1)T\in \left[ 0,1 \right) . 则我们期望的取整函数 R(X,T)R\left( X,T \right) 应满足下列条件:

    R(X,T)={I⋅sgn(X),f<T(I+1)⋅sgn(X),f≥TR\left( X,T \right) = \left\{ \begin{array}{c} I \cdot \text{sgn} \left( X \right) , f<T\\ \left( I+1 \right) \cdot \text{sgn} \left( X \right) , f\ge T\\ \end{array} \right.

  3. 定义偏移量: 考虑偏移量 Δ\Delta , 使得 Tr(X+Δ)=R(X,T)Tr\left( X + \Delta \right) =R\left ( X,T \right)

解答#

为找到偏移量 Δ\Delta , 进行下列操作:

(1) 考虑正数域#

由于在正数域下,可得: ⌊I+f+Δ⌋={I,f<TI+1,f≥T\lfloor I + f + \Delta \rfloor = \left\{ \begin{array}{c} I, f < T \\ I + 1, f \ge T \end{array} \right.

又由底函数性质 ⌊I+α⌋=I+⌊α⌋\lfloor I + \alpha \rfloor = I + \lfloor \alpha \rfloor, 可得: ⌊f+Δ⌋={0,f+Δ<11,f+Δ≥1\lfloor f + \Delta \rfloor = \left\{ \begin{array}{c} 0, f + \Delta < 1 \\ 1, f + \Delta \ge 1 \end{array} \right.

欲使阈值点 f=Tf = T 恰好成为进位临界点,则应有: {T+Δ≥1  ⟹  Δ≥1−Tlim⁡ϵ→0(T−ϵ)+Δ<1  ⟹  Δ≤1−T\begin{cases} T + \Delta \ge 1 \implies \Delta \ge 1 - T \\ \lim_{\epsilon \to 0} (T - \epsilon) + \Delta < 1 \implies \Delta \leq 1 - T \end{cases}

即得 1−T≤Δ≤1−T1-T\le \Delta \leq 1-T , 则有唯一解为: Δ=1−T\Delta = 1 - T

(2) 考虑负数域#

考虑负数 −N=−I−f<0-N=-I-f<0 , 其中 N,I,f>0N, I, f>0 .

由于在复数域下,可得: ⌊−I−f+Δ⌋={−I,f<T−I−1,f≥T\lfloor -I-f+\Delta \rfloor =\left\{ \begin{array}{c} -I,f<T\\ -I-1,f\ge T\\ \end{array} \right.

即有 ⌊I+f−Δ⌋={I,f<TI+1,f≥T\lfloor I+f-\Delta \rfloor =\left\{ \begin{array}{c} I,f<T\\ I+1,f\ge T\\ \end{array} \right.

令 Δ0=−Δ\Delta_0 = - \Delta, 则有 ⌊I+f+Δ0⌋={I,f<TI+1,f≥T\lfloor I+f+\Delta_0 \rfloor =\left\{ \begin{array}{c} I,f<T\\ I+1,f\ge T\\ \end{array} \right.

则由情况(1),可得 Δ0=1−T\Delta_0 = 1 - T , 进而有: Δ=−(1−T)\Delta =-\left( 1-T \right)

结论#

我们可以得到在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))))

由于计算机存在精度损失,我们需要考虑以下情况: 2.5+(0.9−0.1×4)\xsim精度损失2.5+0.49999999999=2.99999999999→static_cast22.5+\left( 0.9-0.1\times 4 \right) \xsim{\text{精度损失}}2.5+0.49999999999=2.99999999999\xrightarrow{static\_cast}2

为修正精度丢失所带来的影响,我们可以引入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))).

更进一步地,如果能确定数据均为正数或负数,可直接略去三目运算符。

优势和劣势#

  1. 该方法在通常情况下会比round()函数更快,但由于该语句中三目运算符产生的分支,如果输入的数据中大量出现正负交替的现象,则会由于CPU分支预测器的失效导致严重的性能抖动。
  2. 可能存在溢出风险,这需要开发者进行额外的注意(尽管round()函数也会出现溢出就是了)。
基于偏移截断法的n舍n+1入简单数学分析
https://samera2022.github.io/posts/Experiences/基于偏移截断法的n舍n1入简单数学分析/
作者
Samera2022
发布于
2026-01-22
许可协议
CC BY-NC-SA 4.0