数学研发论坛

 找回密码
 欢迎注册
查看: 564|回复: 15

[讨论] 如何快速求最相邻近的浮点数(C++)

[复制链接]
发表于 2019-7-29 17:18:36 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
已知:一个 double 型浮点数 \(c \; (c \gt 1.0)\),
求:另一个 double 型浮点数 \(x\),使得其差 \(d =\abs{x-c}\) 非 \(0.0\) 但尽可能地小。

备注:数据存储遵循 IEEE 二进制浮点数算术标准(IEEE 754)

要求:在满足需求的前提下,实现应尽可能地高效(用 C/C++ 语言)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-7-29 17:21:05 | 显示全部楼层
我当前的策略是:令 \(x = c * ( 1.0 \pm \text{DBL_EPSILON} )\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-29 18:27:38 来自手机 | 显示全部楼层
看出64位整数加1看看

点评

如果-1,正负0会出问题,需要单独处理(如果是正负0,加1,其他情况都可以减1)  发表于 2019-7-29 18:51
+1与-1,+0.999与-0.999都是只有最高位不相同,因此-1同时适用于正数与负数 ……一会儿我再测试一下-0.的问题  发表于 2019-7-29 18:42
应该减1才对,加1会在某些特殊场合出问题(比如最接近1的是0.999999....而非1.000...0002)  发表于 2019-7-29 18:41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-29 18:39:42 | 显示全部楼层
mathe 发表于 2019-7-29 18:27
看出64位整数加1看看

typedef union {
        double d;
        long long ll;
} dll;
double near(dll in){in.ll^=1;return in.d;}
double nearest(dll in){in.ll-=1;return in.d;}
前面那个理论上更快一点,然而后面那个能正确地输出最小值(比如最接近1的数字)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-7-30 07:41:15 | 显示全部楼层
用整型计算替换浮点计算,是算法加速的技巧之一。
我现在需要的可能是“左相邻”,也可能是“右相邻”的数;但究竟是需要左还是右,得上下文决定。

换个话题:假设对于已知 \(c\),我们得到其“左相邻”或“右相邻”的浮点数 \(x\),其是否真正相邻,可否用下列代码判定:
  1. const double m = 0.5 * ( x + c );

  2. assert( x != c && ( m == x || m == c ));
复制代码

点评

那用.·.·.的异或方案应该很不错  发表于 2019-7-30 11:02
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-31 08:54:19 | 显示全部楼层
boost里有关于float的对比, 很具体,分成了三类:
https://www.boost.org/doc/libs/1 ... oat_comparison.html

Absolute difference/error: the absolute difference between two values a and b is simply fabs(a-b). This is the only meaningful comparison to make if we know that the result may have cancellation error (see below).
The edit distance between the two values: i.e. how many (binary) floating-point values are between two values a and b?
The relative distance/error between two values. This is quick and easy to compute, and is generally the method of choice when checking that your results are "tolerably close" to one another.

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-31 09:39:39 | 显示全部楼层
找出double型数的52位尾数部分(实际上是53位,因最高位总是1,故不存储),在最低位加1或者减1,找出最合适的。
需要,要注意极端情况,52位尾数为全1,或者全0.

点评

说得没错。我印象当中是这样的。当浮点数特别小时,在指数取到最小时仍不能正确表示,这时使用非正规形式,尾数部分的最高位可为0.  发表于 2019-8-1 15:39
(比如0.跟-0.)  发表于 2019-7-31 23:53
没记错浮点数最高位不总是1……有特例的……  发表于 2019-7-31 23:53
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-1 15:39:03 | 显示全部楼层
liangbch 发表于 2019-7-31 09:39
找出double型数的52位尾数部分(实际上是53位,因最高位总是1,故不存储),在最低位加1或者减1,找出最合适 ...

说得没错。我印象当中是这样的。当浮点数特别小时,在指数取到最小时仍不能正确表示,这时使用非正规形式,尾数部分的最高位可为0.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-8-2 17:20:02 | 显示全部楼层
好消息,今天无意中搜到了一组函数,
原来在 C++11 起就已经提供了:std::nextafter, std::nexttoward
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-11-15 08:46 , Processed in 0.068683 second(s), 22 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表