rust - 如何检查大于 2 ^ 54 的 u64 数是否可以被 f64 整除且精度损失最小？

Question

对于小于 2 ^ 54 的 u64 数字，可以通过转换为 f64 来完成，而不会造成太多精度损失:

((6 as f64) % 1.5) < f64::EPSILON

对于较大的数字，会有显着的精度损失:

1u64 << 63           // 9223372036854775808
(1u64 << 63) as f64  // 9223372036854776000

并且将检查不同数字的可除性。

上下文:JSONSchema的multipleOf关键字实现

问题:检查u64/i64 不符合f64< 的数字的整除性的最有效方法是什么 尾数大小(f64::MANTISSA_DIGITS 为 53)？

Answer 1

如果 u 是某个整数并且 x 是一个有限的非零 IEEE-754 二进制 64 数，我们将使用它进行 IEEE-754 算术，这是一个解决方案。 x 被假定代表一个特定的数字，如 IEEE-754 所指定的，并且不考虑在获取 x 时发生的先前舍入错误。这个答案涉及所涉及的数学，而不是 Rust 语义，因为我不熟悉 Rust。

首先，找到x = F • 2^E的表示，其中F 是奇数，E 是整数。一个简单的方法是:

• 将F设为x，将E设为0。
• 虽然 F 不是整数，但将 F 乘以二，然后从 E 中减一。
• 当 F 是偶数时，将 F 除以二，然后在 E 上加一。

所有上述操作都可以在 IEEE-754 算法中执行，没有舍入误差。如果 Rust 提供了一种分离 float 的尾数和指数的方法，类似于 C 的 frexp 函数，那么将其合并到上面可以提高效率。

现在考虑 u 是否是 x 的倍数 = F • 2^{E 。根据定义，当且仅当存在整数 k 时 u = k • F • 2E。当且仅当 u 是 F 的倍数并且是 2E，并且其中的每一个都可以被测试。}

如果 2^E 是一个整数(E 是非负数)并且这样的 k 存在，那么 u 是 F 的倍数并且是 2^E 的倍数。相反，如果 u 不是 F 的倍数或不是 2^E 的倍数，则没有这样的k 存在(通过算术基本定理)。

F 必须在请求的整数格式范围内(最多 53 位)，我们假设 F 可以转换为该格式。然后可以测试 u 被 F 整除。如果 2^E 超过了表示 u 的整数格式的最大值，则 u 不是2^E 的倍数。否则，2^E可以转化为格式，u被2^E整除 可以测试。

如果 2^E 不是整数(E 是负数)，那么，如果要求的 k存在(所以 u 是 F 的倍数)，它是 2^−E 的倍数。相反，如果 k 不是 2^−E 的倍数，则 k • F • 2^E 不是整数，因此它不能等于 u。因此 u 是 x 的倍数当且仅当 u 是 F 的倍数。