浮子的平均值是否满足机器精度平分的条件?

Does the average of floats satisfy conditions for machine-precision bisection?

提问人:user11130854 提问时间:8/20/2022 最后编辑:user11130854 更新时间:8/20/2022 访问量:81

问:

假设您想运行一个平分算法/二进制搜索,精确到机器精度,由于浮点数范围的指数减半,该算法/二进制搜索将始终在几百步内终止。为此,应满足以下条件:让浮点数 A<B 和 M = (A+B)/2。然后

  1. 当且仅当 A 和 B 不是相邻浮点时,A < M < B。

  2. 当且仅当 A 和 B 是相邻浮点数时,A=M 或 M=B。

这在浮点运算中总是有保证吗?

如果不是,这些条件成立的中点M是否有任何合理的定义?(显然,将 M 定义为 A 的上邻是可行的,但这不是一个合理的定义。

编辑1:正如评论中指出的,A + B的总和可能会溢出。我不一定问这个特定的操作顺序,像 M = A/2 + B/2 这样的东西也是有效的,以及其他中点方法。

编辑 2:https://scicomp.stackexchange.com/questions/20369/robust-computation-of-the-mean-of-two-numbers-in-floating-point/20379 是相关的,因为 min(A,B) <= M <= max(A,B) 的较弱条件,它适用于 M=A+(B/2−A/2) 并且也不会溢出。另一种有趣的二分法是基于将浮点数重新解释为整数:https://www.juliabloggers.com/bisecting-floating-point-numbers/

数值 浮点精度

评论

1赞 Eric Postpischil 8/20/2022
如果 A 和 B 是两个最大的有限可表示值,则产生 ∞,也会产生,因此 M < B 不成立。A+B(A+B)/2
0赞 user11130854 8/20/2022
是的,好点子。我已经更新了问题。
1赞 njuffa 8/21/2022
可能相关:Sylvie Boldo,“计算浮点平均值的程序的形式验证”。2015 年 11 月,法国巴黎,第 17-32 页(HAL 预印本在线)
1赞 Eric Postpischil 8/23/2022
这在某些浮点格式中不成立。考虑一位十进制浮点格式,取 A = 7•10^0, B = 9•10^0。那么 A+B 在实数算术中将是 16,因此以一位十进制计算它会产生 2•10^1。将其除以 2 得到 1•10^1 = 10。所以 M = 10,并且违反了 A < M < B。它也不适用于更多数字:四位数字,(9997•10^0 + 9999•10^0)/2 → (2000•10^1)/2 = 1000•10^1 = 10,000。我怀疑它以二为基数的格式成立。
1赞 Eric Postpischil 8/23/2022
它还需要四舍五入到最接近。向上舍入时,A = 1−2^−53(1 低于 1 的 ULP)和 B = 1+2^−52(高于 1 的 1 ULP,由于不同的 binade 而具有不同的 ULP)将不起作用。在实数算术中,A+B 是 2+1^−53,这是不可表示的,所以向上舍入得到 2+2^−51,然后除以 2 得到 1+2^−52,所以我们有 M = B.其他四舍五入模式也存在类似的情况,除了,我预计,四舍五入到最接近。对于四舍五入到最接近,A+B 在 A 和 B 之间产生 2,即 M = 1。

答:

0赞 user11130854 8/20/2022 #1

这是中点方法的实现,它实际上不使用平均值,而是在 A 和 B 之间的中间位置拆分浮点数集。这是基于 https://www.juliabloggers.com/bisecting-floating-point-numbers/ 的,我相信它满足了要求。代码审查是值得赞赏的。

#include <cstdint> 
#include <math.h> 
#include <cstring>
#include <cassert>


double bisect_float(double L, double R) {
        
    // Use the usual float rules for combining non-finite numbers
    if(!isfinite(L) || !isfinite(R)){
        return(L+R);
    }
    
    if (L==R){return(L);}
    

    // Always return 0.0 when inputs have opposite sign and neither is zero
    if ( (L>0.0 && R<0.0) || (L<0.0 && R>0.0) )   {
        return(0.0);
    }
    
    // check whether we need to change the sign
    bool negate = (L < 0.0 || R < 0.0);
        
    // reinterpret floats as integers
    // this gives their ordering index
    uint64_t Li;
    uint64_t Ri;
    assert(sizeof(uint64_t) == sizeof L);
    assert(sizeof(uint64_t) == sizeof R);
    L = abs(L); // remove sign bit
    R = abs(R); // remove sign bit
    memcpy(&Li, &L, sizeof Li);
    memcpy(&Ri, &R, sizeof Ri);
    
    // find the median float representation
    uint64_t res_i;
    if (Li>Ri){
        std::swap(Li, Ri);
    }
    res_i = Li + ((Ri-Li)>>1);
    //  NOTE: (Li>>1) + (Ri>>1) would be wrong for (3,5), as it would be 1+2=3 and hence not the midpoint
    
    // reinterpret median index as float
    double res;
    memcpy(&res, &res_i, sizeof res);
    
    if (negate){
        return(-res);
    } else {
        return(res);
    }   
}

评论

1赞 Sam Mason 8/22/2022
我想我会把那些 s 变成 s,也许使用而不是所有这些浮点数比较assertstatic_assertstd::signbit
0赞 user11130854 8/22/2022
那么有符号的零呢?我们需要测试这些数字是严格的正数还是负数。
1赞 Sam Mason 8/22/2022
用于符号检查的 Julia 代码看起来不错,即 .godbolt.org/z/96ehMGo7E 看起来更干净一些,但里面不多。因此,“也许使用”前缀。我还注意到 s 不需要在它们的表达式周围加上括号(它们不是函数调用)std::signbit(L) != std::signbit(R) && L != 0.0 && R != 0.0return