提问人:user11130854 提问时间:8/20/2022 最后编辑:user11130854 更新时间:8/20/2022 访问量:81
浮子的平均值是否满足机器精度平分的条件?
Does the average of floats satisfy conditions for machine-precision bisection?
问:
假设您想运行一个平分算法/二进制搜索,精确到机器精度,由于浮点数范围的指数减半,该算法/二进制搜索将始终在几百步内终止。为此,应满足以下条件:让浮点数 A<B 和 M = (A+B)/2。然后
当且仅当 A 和 B 不是相邻浮点时,A < M < B。
当且仅当 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/
答:
这是中点方法的实现,它实际上不使用平均值,而是在 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);
}
}
评论
assert
static_assert
std::signbit
std::signbit(L) != std::signbit(R) && L != 0.0 && R != 0.0
return
评论
A+B
(A+B)/2