부동 소수점 곱셈 대 반복 덧셈

부동 소수점 곱셈 대 반복 덧셈

허락하다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

로.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=16GCC는 다시 시작합니다.N-1합계

제 질문은 왜 GCC가 하지 않는가 하는 것입니다.a*(float)N와 함께-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곱셈과 카한 합이 같은 결과를 가지고 있다는 것을 보여주는 것은 곱셈이 단순한 합보다 더 정확하다는 것을 보여줍니다.

사이에는 몇 가지 근본적인 차이가 있습니다.

 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의 큰 값은 반복적인 덧셈에 대한 합으로 변경되지 않습니다.곱셈을 선택하려면 연산이 no-op이 되려면 결과(값 * N)가 FLT_EPSILON * 합계보다 작아야 합니다.

따라서 컴파일러는 최적화를 할 수 없습니다. 왜냐하면 당신이 정확한 동작(복수가 더 나은 곳)을 원했는지, 또는 합계의 척도가 덧셈의 결과에 영향을 미치는 구현된 동작을 원했는지 알 수 없기 때문입니다.

언급URL : https://stackoverflow.com/questions/33152446/floating-point-multiplication-vs-repeated-addition