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

本文主要分析C++环境下的偏移截断法。当然,核心的逻辑对于其他语言也适用,本文仅以C++举例。C++的强制转型取整为去尾转型,即抛弃所有小数位数。基于此,我们可以讨论基于偏移的截断。

本文尽力做到通俗且严谨,如有疏漏还望大佬轻喷,不吝赐教!

一、简单解答#

法1. 四舍五入的情况(采用实数的规范小数表示证明)#

特殊地,我们先考虑四舍五入的情况。

(1) 考虑正数情况#

对于正数A.49B.51我们期望得到A(B+1)。为得到我们的期望,我们需要至多能给A0.51,至少要给B0.49。即,我们至多能给A(1-0.49),至少要给B(1-0.51)。我们需要加入的偏移量Δ应满足(1-0.51)<Δ<(1-0.49)

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

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

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

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

考察两个式子的极限,发现 limk[1(0.5+10k)]=limk[1(0.510k)]=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+10k)1-\left( 0.5+10^{-k} \right) 单调递增, 1(0.510k)1-\left( 0.5-10^{-k} \right) 单调递减。

考察两个式子的极限,发现 limk[1(0.5+10k)]=limk[1(0.510k)]=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+10k)Δ<1(0.510k)1-\left( 0.5+10^{-k} \right) \leq\Delta <1-\left( 0.5-10^{-k} \right) kN\forall k\in \mathbb{N}^* 成立,则取 kk \rightarrow \infty, 有 0.5=limk[1(0.5+10k)]Δlimk[1(0.510k)]=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+10k)Δ1(0.510k)1-\left( 0.5+10^{-k} \right) \leq\Delta \leq 1-\left( 0.5-10^{-k} \right)

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

an=1(0.5+10k),bn=1(0.510k)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. limk(bkak)=limk(2×10k)=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]

考察两个式子的极限,发现 limk[1(0.5+10k)]=limk[1(0.510k)]=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时有结果分别为AB+1。则直接全体取反,可得Δ=-0.5时,满足四舍五入的要求。

法2. 四舍五入的情况(采用ε语言证明)#

上文我们直观地感受了一下大概的情况,现在我们进行严谨的考虑。

(1) 考虑正数情况#

我们考虑 nN,ε>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+ε,ab\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) 考虑正数情况#

我们考虑 nN,ε>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.90.1nεΔ0.90.1n+ε0.9-0.1n-\varepsilon \leq \Delta \leq 0.9-0.1n+\varepsilon .

由于 ε>0,均有0.90.1nεΔ0.90.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.90.1nε)Δlimε0+(0.90.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.90.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)中,我们可得CDΔ=0.9-0.1n时有结果分别为AB+1。则直接全体取反,可得Δ=-(0.9-0.1n)时,满足n舍n+1入的要求。

二、复杂解答#

定义#

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

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

  2. 定义取整准则: 考虑实数 XRX\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)={Isgn(X),f<T(I+1)sgn(X),fTR\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,fT\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    Δ1Tlimϵ0(Tϵ)+Δ<1    Δ1T\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}

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

(2) 考虑负数域#

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

由于在复数域下,可得: If+Δ={I,f<TI1,fT\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,fT\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,fT\lfloor I+f+\Delta_0 \rfloor =\left\{ \begin{array}{c} I,f<T\\ I+1,f\ge T\\ \end{array} \right.

则由情况(1),可得 Δ0=1T\Delta_0 = 1 - T , 进而有: Δ=(1T)\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.90.1×4)\xsim精度损失2.5+0.49999999999=2.99999999999static_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