浮点类型的数学运算与整数类型相同:如果 n 是基数的幂(二进制为2),则 f modulo n 可以通过将表示值 n 或更大值的数字(也称为高位或高位数字)归零来计算。 因此,对于位数为b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0的二进制整数,我们可以通过将b15设置为b2为零来计算余数模4,只剩下b1 b0。 类似地,如果浮点格式的基数是2,我们可以通过删除所有值为4或更大的数字来计算模4的余数。这不需要除法,但需要检查表示值的位。仅使用简单的位掩码是不够的。 C标准将浮点类型的特征描述为一个符号(±1)、一个基数 b、一个指数和一些基数 b 的数字。因此,如果我们知道一个特定的C实现用来表示浮点类型的格式(符号、指数和数字被编码成比特的方式),那么计算 f 模 n 的算法,其中 n 是 b 的幂,是:
令 y = f。
使用 y 的指数和 n 的指数之间的差来确定 y 中哪些数字的位置值小于 n。
把这些数字改成零。
返回 f − y。
一些注意事项:
该算法必须处理无穷大、NaN、次法线和其他特殊情况。
将副本 y 中的低位数字归零并从 f 中减去而不是直接将 f 中的高位数字归零的目的是避免将IEEE 754格式中的隐式位归零的需要。(在所述算法中,如果 y 中的隐式位需要归零,则将所有 y 归零,因此这很容易。)
虽然没有使用除法,但操作并不像位掩码那样简单,并且通常不太可能有用。然而,存在特殊情况,通常具有已知的 d 值和有限的 x 值,其中浮点表示的这种位操作是有用的。
示例代码:
// This code assumes double is IEEE 754 basic 64-bit binary floating-point.
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
// Return the bits representing the double x.
static uint64_t Bits(double x)
{ return (union { double d; uint64_t u; }) { x } .u; }
// Return the double represented by bits x.
static double Double(uint64_t x)
{ return (union { uint64_t u; double d; }) { x } .d; }
// Return x modulo 2**E.
static double Mod(double x, int E)
{
uint64_t b = Bits(x);
int e = b >> 52 & 0x7ff;
// If x is a NaN, return it.
if (x != x) return x;
// Is x is infinite, return a NaN.
if (!isfinite(x)) return NAN;
// If x is subnormal, adjust its exponent.
if (e == 0) e = 1;
// Remove the encoding bias from e and get the difference in exponents.
e = (e-1023) - E;
// Calculate number of bits to keep. (Could be consolidated above, kept for illustration.)
e = 52 - e;
if (e <= 0) return 0;
if (53 <= e) return x;
// Remove the low e bits (temporarily).
b = b >> e << e;
/* Convert b to a double and subtract the bits we left in it from the
original number, thus leaving the bits that were removed from b.
*/
return x - Double(b);
}
static void Try(double x, int E)
{
double expected = fmod(x, scalb(1, E));
double observed = Mod(x, E);
if (expected == observed)
printf("Mod(%a, %d) = %a.\n", x, E, observed);
else
{
printf("Error, Mod(%g, %d) = %g, but expected %g.\n",
x, E, observed, expected);
exit(EXIT_FAILURE);
}
}
int main(void)
{
double n = 4;
// Calculate the base-two logarithm of n.
int E;
frexp(n, &E);
E -= 1;
Try(7, E);
Try(0x1p53 + 2, E);
Try(0x1p53 + 6, E);
Try(3.75, E);
Try(-7, E);
Try(0x1p-1049, E);
}
4条答案
按热度按时间cuxqih211#
如果
n == 1.0
或n == -1.0
,则可以执行以下操作:在x86_64上,
trunc
通常会使用ROUNDSD
指令,所以这会非常快。如果
n
是2的幂,其大小大于或等于1,并且您的平台具有本机的fma
函数(对于Intel,这意味着Haswell或更新版本),那么您可以任何合理的编译器都应该将除法转换为乘法,并将取反折叠到适当的FMA(或常量)中,从而产生乘法,截断和FMA。
这也适用于2的较小幂,只要结果不溢出(因此编译器不会随意替换它)。
是否有编译器会这样做是另一回事,浮点余数函数并不常用,也没有得到编译器作者的太多关注,例如https://bugs.llvm.org/show_bug.cgi?id=3359
ddrv8njm2#
浮点类型的数学运算与整数类型相同:如果 n 是基数的幂(二进制为2),则 f modulo n 可以通过将表示值 n 或更大值的数字(也称为高位或高位数字)归零来计算。
因此,对于位数为b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0的二进制整数,我们可以通过将b15设置为b2为零来计算余数模4,只剩下b1 b0。
类似地,如果浮点格式的基数是2,我们可以通过删除所有值为4或更大的数字来计算模4的余数。这不需要除法,但需要检查表示值的位。仅使用简单的位掩码是不够的。
C标准将浮点类型的特征描述为一个符号(±1)、一个基数 b、一个指数和一些基数 b 的数字。因此,如果我们知道一个特定的C实现用来表示浮点类型的格式(符号、指数和数字被编码成比特的方式),那么计算 f 模 n 的算法,其中 n 是 b 的幂,是:
一些注意事项:
示例代码:
jgovgodb3#
然而,由于浮点的“模糊”性质(至少是IEEE 754),有一些滥用技巧可以通过近似从根本上加速某些计算,以内存,精度,可移植性,可维护性或这些组合为代价。
最简单的方法是预先计算操作,并在运行前将结果存储到查找表中。表越大,使用的内存越多,但精度也越高。
一种更独特的方法涉及内存中的浮点表示。其中一个更著名的浮点黑客是fast inverse square root。通过这些概念,一般的想法是你可以为任何你想要的东西制作一个近似函数,而不仅仅是平方根的倒数。如果你知道你的输入范围和你的误差容限,你可以构建这样一个算法,它可以根据你的目的进行精确的调整。
如果不说明基准测试的重要性,那将是我的失职!如果你想应用这些技术中的任何一种来加速你的程序,首先进行基准测试,并确保你优化的是正确的地方!
wljmcqd84#
是的,当它们是2的幂时,也有可能使用 * 伪掩码 * 进行模运算,但在这种情况下,我们必须考虑浮点数的格式符合IEEE-754标准。
让我们假设我们做同样的操作,但这一次,由于数字是真实的,2的幂将是一个
1
位,后面跟着无限多个0
s。为了得到 mask,我们做与整数相同的事情......将
1
更改为0
,并且该数字之后的所有位都更改为1
s。但这是一个 * 全1掩码 *,所以尾数永远不会被触及,除了超过模数的位当我们将所有这些位归零时,我们不需要做任何事情,只需要将它们移到左边,让它们落入废纸篓,因为它们被屏蔽了。所以尾数的屏蔽总是左移(在数字的右边填入更多的数字---哎呀,我们没有这些数字,所以用零/随机位/1填充...),然后 * 归一化 * 数字(这意味着移动数字,直到第一个有效数字到达第一位,并协调调整指数偏差)
让我们看一个例子:我们用
2.0
作为模,M_PI
(3.141592...
)作为掩码:如预期的那样是
1.141592...
。正如你所看到的,我们必须检查有偏指数之间的差异,并将尾数左移该差异所指示的位置。同时,我们需要将该差异减去有偏指数(并检查下溢或次正常情况)并重新规范化数字(左移尾数,并递减指数,直到尾数中的第一个到达 * 隐藏 * 位)。
注解
我假设模的偏置指数低于要操作的数字的指数,因为在另一种情况下,掩码都是1,并且数字不受掩码的影响。