是否有任何数字可以对浮点数进行快速模计算？

Question

我知道对于无符号整数，如果除数是 2 的幂，我可以用位掩码替换模运算。对于浮点数，是否有任何数字具有类似的属性？也就是说，是否有任何数字n可以f mod n比一般情况更有效地计算，而不必使用位掩码？

当然，除了一个。 脑部衰竭

编辑：澄清一下，f是任何浮点数（在运行时确定）， n是任何格式的任何编译时常量，我希望结果是浮点数。

Answer 1

浮点类型的数学原理与整数类型相同：如果n是基数的幂（二进制为 2），则可以通过将表示值n或更大的数字归零来计算f模n（也称为高位或高位数字）。

\n

_{因此，对于具有位 b 15} b ₁₄ b ₁₃ b 12 b ₁₁ b ₁₀ b ₉ b ₈ b ₇ b ₆ b ₅ b ₄ b ₃ b ₂ b ₁ b 0的二进制整数，我们可以简单地计算模四_的余数_：将b ₁₅至b ₂设置为零，仅留下b ₁ b ₀。

\n

类似地，如果浮点格式的基数为 2，我们可以通过删除所有值为 4 或更大的数字来计算模 4 的余数。这不需要除法，但确实需要检查表示该值的位。仅一个简单的位掩码是不够的。

\n

C 标准将浮点类型描述为符号 (\xc2\xb11)、基数b、指数和一定数量的基数b数字。因此，如果我们知道特定 C 实现用于表示浮点类型的格式（符号、指数和数字编码为位的方式），则可以计算f模n的算法，其中n是b，是：

\n

\n
• 设y = f。
\n
• 使用y的指数和n的指数之间的差来确定y中哪些数字的位置值小于n。
\n
• 将这些数字更改为零。
\n
• 返回f \xe2\x88\x92 y。
\n

\n

一些注意事项：

\n

\n
• 该算法必须处理无穷大、NaN、次正规数和其他特殊情况。
\n
• 将副本y中的低位清零并从f中减去而不是直接将f中的高位清零的目的是避免需要将 IEEE 754 格式中的隐式位清零。（在上述算法中，如果需要将y中的隐式位清零，则将所有y清零，因此很容易。）
\n
• 尽管没有使用除法，但操作并不像位掩码那么简单，并且一般不太可能有用。然而，在一些特殊情况下，通常是已知的d值和有限的x值，这种浮点表示的位操作是有用的。
\n

\n

示例代码：

\n

//  This code assumes double is IEEE 754 basic 64-bit binary floating-point.\n\n#include <math.h>\n#include <stdint.h>\n#include <stdio.h>\n#include <stdlib.h>\n\n\n//  Return the bits representing the double x.\nstatic uint64_t Bits(double x)\n    { return (union { double d; uint64_t u; }) { x } .u; }\n\n\n//  Return the double represented by bits x.\nstatic double Double(uint64_t x)\n    { return (union { uint64_t u; double d; }) { x } .d; }\n\n\n//  Return x modulo 2**E.\nstatic double Mod(double x, int E)\n{\n    uint64_t b = Bits(x);\n    int      e = b >> 52 & 0x7ff;\n\n    //  If x is a NaN, return it.\n    if (x != x) return x;\n\n    //  Is x is infinite, return a NaN.\n    if (!isfinite(x)) return NAN;\n\n    //  If x is subnormal, adjust its exponent.\n    if (e == 0) e = 1;\n\n    //  Remove the encoding bias from e and get the difference in exponents.\n    e = (e-1023) - E;\n\n    //  Calculate number of bits to keep.  (Could be consolidated above, kept for illustration.)\n    e = 52 - e;\n\n    if (e <= 0) return 0;\n    if (53 <= e) return x;\n\n    //  Remove the low e bits (temporarily).\n    b = b >> e << e;\n\n    /*  Convert b to a double and subtract the bits we left in it from the\n        original number, thus leaving the bits that were removed from b.\n    */\n    return x - Double(b);\n}\n\n\nstatic void Try(double x, int E)\n{\n    double expected = fmod(x, scalb(1, E));\n    double observed = Mod(x, E);\n\n    if (expected == observed)\n        printf("Mod(%a, %d) = %a.\\n", x, E, observed);\n    else\n    {\n        printf("Error, Mod(%g, %d) = %g, but expected %g.\\n",\n            x, E, observed, expected);\n        exit(EXIT_FAILURE);\n    }\n}\n\n\nint main(void)\n{\n    double n = 4;\n\n    //  Calculate the base-two logarithm of n.\n    int E;\n    frexp(n, &E);\n    E -= 1;\n\n    Try(7, E);\n    Try(0x1p53 + 2, E);\n    Try(0x1p53 + 6, E);\n    Try(3.75, E);\n    Try(-7, E);\n    Try(0x1p-1049, E);\n}\n

\n

Answer 2

如果n == 1.0或n == -1.0，那么你可以这样做：

r = f - trunc(f);

在 x86_64 上，trunc通常会使用该ROUNDSD指令，因此速度会相当快。

如果n是 2 的幂，其大小大于或等于 1，并且您的平台具有fma本机函数（对于 Intel，这意味着 Haswell 或更新版本），那么您可以这样做

r = fma(-trunc(f / n), n, f);

任何合理的编译器都应该将除法切换为乘法，并将负数折叠到适当的 FMA（或常数）中，从而产生乘法、截断和 FMA。

只要结果不溢出，这也适用于 2 的较小幂（因此编译器无法随意替换它）。

是否有编译器实际上会这样做是另一回事。浮点余数函数使用不多，也没有引起编译器编写者的太多关注，例如https://bugs.llvm.org/show_bug.cgi?id=3359