C语言 是否有任何数字可以在浮点数上进行快速取模计算?

ccrfmcuu  于 2023-04-05  发布在  其他
关注(0)|答案(4)|浏览(149)

我知道对于无符号整数,如果除数是2的幂,我可以用位掩码代替模运算。有没有任何数字对浮点数有类似的性质?也就是说,有没有任何数字n可以比一般情况下更有效地计算f mod n,不一定使用位掩码?
当然,除了一个,* 大脑故障 *
编辑:澄清一下,f是任何浮点数(在运行时确定),n是任何格式的任何编译时常数,我希望结果是浮点数。

cuxqih21

cuxqih211#

如果n == 1.0n == -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

ddrv8njm

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实现用来表示浮点类型的格式(符号、指数和数字被编码成比特的方式),那么计算 fn 的算法,其中 nb 的幂,是:

  • y = f
  • 使用 y 的指数和 n 的指数之间的差来确定 y 中哪些数字的位置值小于 n
  • 把这些数字改成零。
  • 返回 fy

一些注意事项:

  • 该算法必须处理无穷大、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);
}
jgovgodb

jgovgodb3#

然而,由于浮点的“模糊”性质(至少是IEEE 754),有一些滥用技巧可以通过近似从根本上加速某些计算,以内存,精度,可移植性,可维护性或这些组合为代价。
最简单的方法是预先计算操作,并在运行前将结果存储到查找表中。表越大,使用的内存越多,但精度也越高。
一种更独特的方法涉及内存中的浮点表示。其中一个更著名的浮点黑客是fast inverse square root。通过这些概念,一般的想法是你可以为任何你想要的东西制作一个近似函数,而不仅仅是平方根的倒数。如果你知道你的输入范围和你的误差容限,你可以构建这样一个算法,它可以根据你的目的进行精确的调整。
如果不说明基准测试的重要性,那将是我的失职!如果你想应用这些技术中的任何一种来加速你的程序,首先进行基准测试,并确保你优化的是正确的地方!

wljmcqd8

wljmcqd84#

是的,当它们是2的幂时,也有可能使用 * 伪掩码 * 进行模运算,但在这种情况下,我们必须考虑浮点数的格式符合IEEE-754标准。
让我们假设我们做同样的操作,但这一次,由于数字是真实的,2的幂将是一个1位,后面跟着无限多个0 s。

1000000000000000000000000... * 2^exp

为了得到 mask,我们做与整数相同的事情......将1更改为0,并且该数字之后的所有位都更改为1 s。

0111111111111111111111111... * 2^exp  =
1111111111111111111111111... * 2^(exp-1)
(THIS NUMBER IS (1.0 - FLT_EPSILON) * 2^(exp_of_module - 1))

但这是一个 * 全1掩码 *,所以尾数永远不会被触及,除了超过模数的位当我们将所有这些位归零时,我们不需要做任何事情,只需要将它们移到左边,让它们落入废纸篓,因为它们被屏蔽了。所以尾数的屏蔽总是左移(在数字的右边填入更多的数字---哎呀,我们没有这些数字,所以用零/随机位/1填充...),然后 * 归一化 * 数字(这意味着移动数字,直到第一个有效数字到达第一位,并协调调整指数偏差)
让我们看一个例子:我们用2.0作为模,M_PI3.141592...)作为掩码:

3.141592... = 40 49 0f db
            = 0100 0000 0100 1001 0000 1111 1101 1011...
; which represents
            = 0 (positive)
               100 0000 0 (exponent biased 128 ==> 1)
                     (1.)100 1001 0000 1111 1101 1011...
                      ^ Allways 1 so IEEE-754 doesn't include, we have to do, to operate.
                       11.00 1001 0000 1111 1101 1011...
                       01.11 1111 1111 1111 1111 1111...
             MASKED == 01.00 1001 0000 1111 1101 1011...
                       / // //// //// //// //// ////,-- introduced to complete format
       RENORMALIZED == 1.001 0010 0001 1111 1011 011X...
; result    = 0 (positive)
            =  011 1111 1 (new exponent after norm. 127 ==> 0)
                       1.001 0010 0001 1111 1011 011X
            = 0011 1111 1001 0010 0001 1111 1011 011X

如预期的那样是1.141592...
正如你所看到的,我们必须检查有偏指数之间的差异,并将尾数左移该差异所指示的位置。同时,我们需要将该差异减去有偏指数(并检查下溢或次正常情况)并重新规范化数字(左移尾数,并递减指数,直到尾数中的第一个到达 * 隐藏 * 位)。

注解

我假设模的偏置指数低于要操作的数字的指数,因为在另一种情况下,掩码都是1,并且数字不受掩码的影响。

相关问题