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

问题描述

让N成为一个编译时间的无符号整数.

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.

但是，GCC不会优化

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

to a*(float)N.

但是，通过将关联数学与例如-Ofast我发现GCC可以按顺序log2(N)步骤减少.例如，对于N=8，它可以在三个加法中进行总和.

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总和.

我的问题是为什么GCC不使用-Ofast?

而不是O(N)或O(Log(N))可以简单地O(1).由于N在编译时已知，因此可以确定N是否适合浮子.即使N太大而无法进行浮动，也可以做sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000).实际上，我进行了一些测试以检查准确性，无论如何a*(float)N还是更准确的(请参阅下面的代码和结果).

//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 ummantion 我认为这表明乘法比简单总和更准确.

推荐答案

 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 *大于值时，重复总和趋向于no-op.因此，任何大价值的n都不会导致重复添加的总和.对于乘法选择，结果(值 * n)需要flt_epsilon *小于该操作的总和.

因此，编译器无法进行优化，因为它无法确定您是否想要确切的行为(在乘以更好的情况下)或实现的行为，而总和的规模会影响加法的结果.<<<<<<<<<<<<

本文地址：https://www.itbaoku.cn/post/359140.html