많은 수의 작은 수레를 함께 추가하는 좋은 방법은 무엇입니까?

Question

배열에 100000000 개의 32 비트 부동 소수점 값이 있고 각 부동 소수점의 값이 0.0에서 1.0 사이 인 경우를 가정 해 보겠습니다. 이

result = 0.0; 
for (i = 0; i < 100000000; i++) { 
    result += array[i]; 
} 

처럼 그들 모두를 요약하려고하면 result 1.0보다 훨씬 커질수록 당신은 문제로 실행하는 것입니다.

그렇다면 합계를보다 정확하게 수행하는 몇 가지 방법은 무엇입니까?

Answer 1

Kahan Summation과 같은 소리가 들립니다. 위키에 따르면

,

은 Kahan은 (또한 라고도 요약 보상) 요약 알고리즘 크게 유한 정밀도 부동 소수점 숫자의 시퀀스를 가산 한 합계 수치 에러를 감소 비해 분명한 접근 방식으로 이것은 별도의 실행 보정 (작은 오류를 누적하는 변수)을 유지함으로써 수행됩니다.

의사에서, 알고리즘은 다음과 같습니다

function kahanSum(input) 
var sum = input[1] 
var c = 0.0   //A running compensation for lost low-order bits. 
for i = 2 to input.length 
    y = input[i] - c //So far, so good: c is zero. 
    t = sum + y   //Alas, sum is big, y small, so low-order digits of y are lost. 
    c = (t - sum) - y //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y) 
    sum = t    //Algebraically, c should always be zero. Beware eagerly optimising compilers! 
next i    //Next time around, the lost low part will be added to y in a fresh attempt. 
return sum 

Answer 2

결과를 두 배로 만듭니다 (C 또는 C++ 가정).

Answer 3

.NET에서 IEnumerable에있는 LINQ .Sum() 확장 메서드를 사용하는 경우. 그렇다면 단지 :

var result = array.Sum(); 

Answer 4

당신이 (자바) 약간의 여분의 공간을 허용 할 수있는 경우 :

float temp = new float[1000000]; 
float temp2 = new float[1000]; 
float sum = 0.0f; 
for (i=0 ; i<1000000000 ; i++) temp[i/1000] += array[i]; 
for (i=0 ; i<1000000 ; i++) temp2[i/1000] += temp[i]; 
for (i=0 ; i<1000 ; i++) sum += temp2[i]; 

표준 분할 정복 알고리즘, 기본적으로합니다. 숫자가 임의로 흩어져있는 경우에만 작동합니다. 처음 수 십억 개가 1e-12이고 두 번째 수십억 개가 훨씬 더 큰 경우에는 작동하지 않습니다.

하지만 그 중 하나를 수행하기 전에 결과를 두 배로 누적 할 수 있습니다. 그것은 많은 도움이 될 것입니다. ;

가

PriorityQueue<Float> q = new PriorityQueue<Float>(); 
for(float x : list) q.add(x); 
while(q.size() > 1) q.add(q.pop() + q.pop()); 
return q.pop(); 

(일반적 큐가 절대 값으로 정렬되어야이 코드 번호 양성 가정)

Answer 5

절대적으로 최적의 방법은 다음과 같은 방법으로, 우선 순위 대기열을 사용하는 것 설명 : 주어진 숫자 목록을 가능한 한 정확하게 추가하려면 번호를 닫기 위해 노력해야합니다. ti 크고 작은 것의 차이를 제거하십시오. 그래서 두 개의 가장 작은 숫자를 합산하여 목록의 최소값을 늘리고 목록에서 최소값과 최대 값의 차이를 줄이고 문제 크기를 1 씩 줄이려는 것입니다.

불행히도 나는 OpenCL을 사용한다고 가정 할 때 이것이 어떻게 벡터화 될 수 있습니까? 그러나 나는 그것이 가능할 것이라고 거의 확신한다. 벡터 알고리즘에 대한 책을 살펴보면 실제로 얼마나 강력한 지 놀랍습니다. Vector Models for Data-Parallel Computing