浮点乘法VS重复加法 [英] floating point multiplication vs repeated addition

问题描述

让 N 是一个编译时无符号整数。

Let N be an a compile time unsigned integer.

GCC可以优化

unsigned sum = 0;
for(unsigned i=0; i<N; i++) sum += a; // a is an unsigned integer   

简单地 A * N 。这可以理解，因为模运算称（A％K + B％K）％K =（A + B）％K 。

to simply a*N. This can be understood since modular arithmetic says (a%k + b%k)%k = (a+b)%k.

但是GCC不优化

float sum = 0;
for(unsigned i=0; i<N; i++) sum += a;  // a is a float

到 A *（浮点）N 。

但是，通过使用关联数学与例如 -Ofast 我发现，海湾合作委员会可以以 LOG2（N）步骤减少这种。例如对于 N = 8 它可以做三个加法的总和。

But by using associative math with e.g. -Ofast I discovered that GCC can reduce this in order log2(N) steps. E.g for N=8 it can do the sum in three additions.

sum = a + a
sum = sum + sum // (a + a) + (a + a)
sum = sum + sum // ((a + a) + (a + a)) + ((a + a) + (a + a))

虽然在某些时候N = 16 GCC追溯到做 N-1 款项。

Though some point after N=16 GCC goes back to doing N-1 sums.

我的问题是为什么GCC不做 A *（浮点）N 与 -Ofast ？

My question is why does GCC not do a*(float)N with -Ofast?

相反，它可以简单<$的是 O（N）或 O（日志（N）） C $ C> O（1）。由于 N 在编译时知道这是可能的，以确定是否 N 镶嵌在浮动。即使 N 是一个浮动它可以做太大总和= A×（浮动）（N＆安培; 0x0000ffff）+ A *（浮点）（N＆安培; FFFF0000）。事实上，我做了一个小测试，以检查的准确性和 A *（浮点）N 更准确呢（见code和下面的结果）。

Instead of being O(N) or O(Log(N)) it could be simply O(1). Since N is known at compile time it's possible to determine if N fits in a float. And even if N is too large for a float it could do sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000). In fact, I did a little test to check the accuracy and a*(float)N is more accurate anyway (see the code and results below).

//gcc -O3 foo.c
//don't use -Ofast or -ffast-math or -fassociative-math
#include <stdio.h>   
float sumf(float a, int n)
{
  float sum = 0;
  for(int i=0; i<n; i++) sum += a;
  return sum;
}

float sumf_kahan(float a, int n)
{
  float sum = 0;
  float c = 0;
  for(int i=0; i<n; i++) {
    float y = a - c;
    float t = sum + y;
    c = (t -sum) - y;
    sum = t;
  }
  return sum;
}  

float mulf(float a, int n)
{
  return a*n;
}  

int main(void)
{
  int n = 1<<24;
  float a = 3.14159;
  float t1 = sumf(a,n);
  float t2 = sumf_kahan(a,n);
  float t3 = mulf(a,n);
  printf("%f %f %f\n",t1,t2,t3);
}

结果 61848396.000000 52707136.000000 52707136.000000 这表明乘法和的 Kahan的总和有同样的结果，我想表明，乘法比简单叠加更加准确。

The result is 61848396.000000 52707136.000000 52707136.000000 which shows that multiplication and the Kahan summation have the same result which I think shows that the multiplication is more accurate than the simple sum.

推荐答案

有

 float funct( int N, float sum )
 {
     float value = 10.0;
     for( i = 0; i < N ;i ++ ) {
         sum += value;
     }
     return sum;
 }

和

float funct( int N, float sum )
{
    float value = 10.0;
    sum += value * N;
    return sum;
}

在总和接近FLT_EPSILON *比数值越大，反复对之无操作趋向。因此，氮的较大值，会导致没有变化总结为重复加入。对于乘法选择，结果（值* N）需要FLT_EPSILON *比之更小的操作有一个空操作。

When the sum approaches FLT_EPSILON * larger than value, the repeated sum tends towards a no-op. So any large value of N, would result in no change to sum for repeated addition. For the multiplication choice, the result (value * N) needs to be FLT_EPSILON * smaller than sum for the operation to have a no-op.

所以编译器不能做出最优化的，因为它不能告诉，如果你想要的确切行为（其中乘为佳），或实现的行为，其中一笔规模影响相加的结果。

So the compiler can't make the optimization, because it can't tell if you wanted the exact behavior (where multiply is better), or the implemented behavior, where the scale of sum affects the result of the addition.

这篇关于浮点乘法VS重复加法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！