algorithm - 获取特殊素数 float 模数的快速、可向量化方法？

Question

有没有一种快速取 float 模数的方法？

对于整数，梅森素数有一些技巧，因此可以计算 y = x MOD 2^31-1 而无需除法。 integer trick

是否可以将任何类似的技巧应用于 float ？

最好以一种可以转换为矢量/SIMD 操作或移入 GPGPU 代码的方式进行。这排除了对 float 据使用整数计算。

我感兴趣的素数是 2^7-1 和 2^31-1，尽管如果有更高效的 float ，那将是受欢迎的。

此算法的一个预期用途是在将输入 float 读入算法时计算输入 float 的运行“校验和”。为了避免占用太多的计算能力，我想保持这个轻量级。

显然，类似的技术用于较大的数字，尤其是 2^127 - 1。不幸的是，论文中的数学超出了我的范围，我无法弄清楚如何将其转换为较小的素数。< br/> Example of floating point MOD 2^127 - 1 - HASH127

Answer 1

我查看了 djb 的论文，你说的更简单，因为 31 位非常适合 53 位精度双有效位。假设您的校验和由 Z/(2**31 - 1) 上的一些环操作组成，解决计算 x mod Z/(2**31 - 的小代表的轻松问题将更容易(也更快) 1);最后，您可以使用整数算法来找到一个规范的算法，这很慢但不应该经常发生。

基本的归约步骤是将整数 x = y + 2**31 * z 替换为 y + z。 djb 使用的技巧是计算 w = (x + L) - L，其中 L 是一个精心选择的大整数，以 z = 2**-31 * w 的方式引起舍入。然后计算 y = x - w 并输出 y + z，其大小最多为 2**32。 (如果此操作还不够，我深表歉意；如果是这样，请发布您的校验和算法。)

L 的选择涉及了解有效数字的精确程度。对于模数 2**31 - 1，我们希望最小精度单位 (ulp) 为 2**31。对于 [1.0, 2.0) 范围内的 double 值，ulp 为 2**-52，因此 L 应为 2**52 * 2**31。如果您使用模数 2**7 - 1 执行此操作，那么您将采用 L = 2**52 * 2**7。正如 djb 指出的那样，这个技巧主要取决于以更高的精度计算而不是的中间结果。