가장 정확한 결과를 얻으려면 어떤 순서로 수레를 추가해야합니까?

가장 정확한 결과를 얻으려면 어떤 순서로 수레를 추가해야합니까?

---

이것은 최근 인터뷰에서 물어 본 질문이었고 알고 싶습니다 (실제로 수치 분석 이론을 기억하지 못하므로 도와주세요 :)

부동 소수점 숫자를 축적하는 함수가 있다면 :

std::accumulate(v.begin(), v.end(), 0.0);

vA는 std::vector<float>, 예를 들면.

• 이 숫자를 누적하기 전에 정렬하는 것이 더 낫습니까?

• 어떤 순서가 가장 정확한 답을 줄까요?

나는 의심 정렬 오름차순으로 번호 것은 실제로 수치 오류 만들 것 덜 하지만, 불행히도 내가 직접 증명할 수 없습니다.

추신 : 나는 이것이 아마도 실제 프로그래밍과 관련이 없다는 것을 알고 있습니다.

---

본능은 기본적으로 옳으며, 오름차순 (크기)으로 정렬하면 일반적으로 상황이 다소 개선됩니다. 단 정밀도 (32 비트) 부동 소수점을 추가하고 1 / (10 억)에 해당하는 10 억 개의 값과 1에 해당하는 하나의 값이있는 경우를 생각해보십시오. 1이 먼저 오면 합계가 나옵니다. 정밀도 손실로 인해 1 + (1/10 억)이 1이므로 1로 설정됩니다. 각 추가는 합계에 전혀 영향을주지 않습니다.

작은 값이 먼저 나오면 적어도 어떤 값을 합할 것입니다. 그래도 2 ^ 30 개를 가지고있는 반면 2 ^ 25 정도 후에는 각각의 값이 총계에 영향을 미치지 않는 상황으로 돌아 왔습니다. 더 이상. 그래서 나는 여전히 더 많은 트릭이 필요할 것입니다.

이는 극단적 인 경우이지만 일반적으로 비슷한 크기의 두 값을 추가하는 것이 크기가 매우 다른 두 값을 추가하는 것보다 더 정확합니다. 그렇게하면 더 작은 값에서 더 적은 정밀도 비트를 "버려"기 때문입니다. 숫자를 정렬하면 비슷한 크기의 값을 함께 그룹화하고 오름차순으로 추가하면 작은 값이 더 큰 숫자의 크기에 누적 될 수있는 "기회"를 부여합니다.

그래도 음수가 관련되면이 접근 방식을 "앞으로"하기 쉽습니다. 합할 세 값을 고려하십시오 {1, -1, 1 billionth}. 산술적으로 정확한 합계는 1 billionth이지만 첫 번째 추가에 작은 값이 포함되면 최종 합계는 0이됩니다. 가능한 6 개의 주문 중 2 개만 "올바른"- {1, -1, 1 billionth}및 {-1, 1, 1 billionth}. 6 개 차수는 모두 입력에서 가장 큰 크기 값 (0.0000001 % 출력)의 척도로 정확한 결과를 제공하지만, 그중 4 개의 차수에 대해서는 실제 솔루션 (100 % 출력)의 척도에서 정확하지 않습니다. 해결하려는 특정 문제는 전자가 충분히 좋은지 여부를 알려줍니다.

사실, 정렬 된 순서로 추가하는 것보다 훨씬 더 많은 트릭을 사용할 수 있습니다. 매우 작은 값이 많고 중간 값이 많고 큰 값이 적은 경우 먼저 작은 값을 모두 더한 다음 중간 값을 따로 합하고이 두 합계를 더하는 것이 가장 정확할 수 있습니다. 함께 큰 것을 추가하십시오. 부동 소수점 덧셈의 가장 정확한 조합을 찾는 것은 결코 쉬운 일이 아니지만 정말 나쁜 경우에 대처하기 위해 전체 누적 합계 배열을 다른 크기로 유지하고 각 새 값을 해당 크기와 가장 일치하는 합계에 추가 할 수 있습니다. 누적 합계가 크기에 비해 너무 커지기 시작하면 다음 합계에 추가하고 새 합계를 시작합니다. 논리적 인 극단으로 볼 때이 프로세스는 임의 정밀도 유형으로 합계를 수행하는 것과 동일합니다. d). 그러나 오름차순 또는 내림차순으로 추가하는 단순한 선택을 고려할 때 오름차순이 더 나은 방법입니다.

실제 프로그래밍과 약간의 관련이 있습니다. 왜냐하면 각각의 값이 너무 작아서 개별적으로 영향을주기에는 너무 작은 값으로 구성된 "무거운"꼬리를 실수로 잘라 내면 계산이 매우 잘못 될 수있는 경우가 있기 때문입니다. 합계 또는 합계의 마지막 몇 비트에만 개별적으로 영향을 미치는 많은 작은 값에서 너무 많은 정밀도를 버리는 경우. 어쨌든 꼬리가 무시할만한 경우에는 아마도 신경 쓰지 않을 것입니다. 예를 들어 처음에 적은 수의 값만 합산하고 합의 유효 숫자 몇 개만 사용하는 경우입니다.

---

Kahan Summation 이라는 이러한 종류의 누적 연산을 위해 설계된 알고리즘도 있습니다.

Wikipedia에 따르면

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

---

Steve Jessop이 제공 한 답변에서 극단적 인 예를 시도했습니다.

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    for (long i = 0; i < billion; ++i)
        sum += small;
    std::cout << std::scientific << std::setprecision(1) << big << " + " << billion << " * " << small << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    sum = 0;
    for (long i = 0; i < billion; ++i)
        sum += small;
    sum += big;
    std::cout  << std::scientific << std::setprecision(1) << billion << " * " << small << " + " << big << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

다음과 같은 결과를 얻었습니다.

1.0e+00 + 1000000000 * 1.0e-09 = 2.000000082740371    (difference = 0.000000082740371)
1000000000 * 1.0e-09 + 1.0e+00 = 1.999999992539933    (difference = 0.000000007460067)

첫 번째 줄의 오류는 두 번째 줄의 10 배 이상 더 큽니다.

위 코드에서 doubles를 floats로 변경하면 다음과 같이 표시됩니다.

1.0e+00 + 1000000000 * 1.0e-09 = 1.000000000000000    (difference = 1.000000000000000)
1000000000 * 1.0e-09 + 1.0e+00 = 1.031250000000000    (difference = 0.968750000000000)

두 답변 모두 2.0에 가깝지는 않지만 두 번째 답변은 약간 더 가깝습니다.

doubleDaniel Pryden이 설명한대로 Kahan 합계 ( s 포함) 사용 :

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    double c = 0.0;
    for (long i = 0; i < billion; ++i) {
        double y = small - c;
        double t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }

    std::cout << "Kahan sum  = " << std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

정확히 2.0 :

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

위 코드에서 doubles를 floats로 변경해도 다음과 같은 결과가 나타납니다 .

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

Kahan이 갈 길인 것 같습니다!

---

데이터를 정렬하거나 재정렬 할 필요없이이 정확한 문제를 해결하는 알고리즘 클래스가 있습니다 .

즉, 데이터에 대한 한 번의 패스로 합계를 수행 할 수 있습니다. 이는 또한 데이터가 실시간으로 도착하고 누적 합계를 유지해야하는 경우와 같이 데이터 세트가 미리 알려지지 않은 상황에서도 이러한 알고리즘을 적용 할 수있게합니다.

다음은 최근 논문의 요약입니다.

우리는 부동 소수점 숫자 스트림의 정확한 합계를위한 새로운 온라인 알고리즘을 제시합니다. "온라인"이란 알고리즘이 한 번에 하나의 입력 만 볼 필요가 있고 이러한 입력의 임의 길이 입력 스트림을 가져 오면서 일정한 메모리 만 요구할 수 있음을 의미합니다. "정확함"이란 알고리즘의 내부 배열의 합이 모든 입력의 합과 정확히 같고 반환 된 결과가 올바르게 반올림 된 합임을 의미합니다. 정확성 증명은 모든 입력 (정규화되지 않은 숫자 포함하지만 모듈로 중간 오버플로 포함)에 대해 유효하며 합계의 수 또는 합계의 조건 번호와 무관합니다. 알고리즘은 점근 적으로 summand 당 5 개의 FLOP 만 필요하며 명령 수준 병렬 처리로 인해 명백한 것보다 약 2-3 배 느리게 실행됩니다. summand의 수가 10,000보다 클 때 빠르지 만 멍청한 "보통 재귀 합산"루프. 따라서 우리가 아는 한, 알려진 알고리즘 중에서 가장 빠르고 정확하며 메모리 효율성이 가장 높습니다. 실제로 더 빠른 알고리즘이나 훨씬 더 적은 FLOP를 필요로하는 알고리즘이 하드웨어 개선없이 어떻게 존재할 수 있는지보기는 어렵습니다. 다수의 요약에 대한 응용 프로그램이 제공됩니다.

출처 : 알고리즘 908 : 부동 소수점 스트림의 온라인 정확한 합계 .

---

먼저 숫자를 오름차순으로 정렬하는 Steve의 대답을 바탕으로 두 가지 아이디어를 더 소개합니다.

1. 너무 많은 정밀도를 잃을 것이라고 결정할 수있는 두 숫자의 지수 차이를 결정하십시오.

2. 그런 다음 누산기의 지수가 다음 숫자에 비해 너무 클 때까지 숫자를 더한 다음 누산기를 임시 대기열에 넣고 다음 숫자로 누산기를 시작합니다. 원래 목록을 모두 사용할 때까지 계속하십시오.

임시 큐 (정렬 된)와 더 큰 지수 차이로 프로세스를 반복합니다.

항상 지수를 계산해야한다면 상당히 느릴 것이라고 생각합니다.

나는 프로그램을 빠르게 진행했고 결과는 1.99903이었습니다.

---

누적하는 과정에서 누적 기가 점점 커지기 때문에 누적하기 전에 숫자를 정렬하는 것보다 더 잘할 수 있다고 생각합니다. 비슷한 숫자가 많으면 정확도가 빨리 떨어지기 시작합니다. 대신 제안 할 내용은 다음과 같습니다.

while the list has multiple elements
    remove the two smallest elements from the list
    add them and put the result back in
the single element in the list is the result

물론이 알고리즘은 목록 대신 우선 순위 대기열을 사용하면 가장 효율적입니다. C ++ 코드 :

template <typename Queue>
void reduce(Queue& queue)
{
    typedef typename Queue::value_type vt;
    while (queue.size() > 1)
    {
        vt x = queue.top();
        queue.pop();
        vt y = queue.top();
        queue.pop();
        queue.push(x + y);
    }
}

운전사:

#include <iterator>
#include <queue>

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type
reduce(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type vt;
    std::priority_queue<vt> positive_queue;
    positive_queue.push(0);
    std::priority_queue<vt> negative_queue;
    negative_queue.push(0);
    for (; begin != end; ++begin)
    {
        vt x = *begin;
        if (x < 0)
        {
            negative_queue.push(x);
        }
        else
        {
            positive_queue.push(-x);
        }
    }
    reduce(positive_queue);
    reduce(negative_queue);
    return negative_queue.top() - positive_queue.top();
}

큐의 숫자 top는 가장 큰 숫자를 산출 하기 때문에 음수 이지만 가장 작은 . 대기열에 더 많은 템플릿 인수를 제공 할 수 있었지만이 방법은 더 간단 해 보입니다.

---

This doesn't quite answer your question, but a clever thing to do is to run the sum twice, once with rounding mode "round up" and once with "round down". Compare the two answers, and you know /how/ inaccurate your results are, and if you therefore need to use a cleverer summing strategy. Unfortunately, most languages don't make changing the floating point rounding mode as easy as it should be, because people don't know that it's actually useful in everyday calculations.

Take a look at Interval arithmetic where you do all maths like this, keeping highest and lowest values as you go. It leads to some interesting results and optimisations.

---

The simplest sort that improves accuracy is to sort by the ascending absolute value. That lets the smallest magnitude values have a chance to accumulate or cancel before interacting with larger magnitude values that have would trigger a loss of precision.

That said, you can do better by tracking multiple non-overlapping partial sums. Here is a paper describing the technique and presenting a proof-of-accuracy: www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps

That algorithm and other approaches to exact floating point summation are implemented in simple Python at: http://code.activestate.com/recipes/393090/ At least two of those can be trivially converted to C++.

---

For IEEE 754 single or double precision or known format numbers, another alternative is to use an array of numbers (passed by caller, or in a class for C++) indexed by the exponent. When adding numbers into the array, only numbers with the same exponent are added (until an empty slot is found and the number stored). When a sum is called for, the array is summed from smallest to largest to minimize truncation. Single precision example:

/* clear array */
void clearsum(float asum[256])
{
size_t i;
    for(i = 0; i < 256; i++)
        asum[i] = 0.f;
}

/* add a number into array */
void addtosum(float f, float asum[256])
{
size_t i;
    while(1){
        /* i = exponent of f */
        i = ((size_t)((*(unsigned int *)&f)>>23))&0xff;
        if(i == 0xff){          /* max exponent, could be overflow */
            asum[i] += f;
            return;
        }
        if(asum[i] == 0.f){     /* if empty slot store f */
            asum[i] = f;
            return;
        }
        f += asum[i];           /* else add slot to f, clear slot */
        asum[i] = 0.f;          /* and continue until empty slot */
    }
}

/* return sum from array */
float returnsum(float asum[256])
{
float sum = 0.f;
size_t i;
    for(i = 0; i < 256; i++)
        sum += asum[i];
    return sum;
}

double precision example:

/* clear array */
void clearsum(double asum[2048])
{
size_t i;
    for(i = 0; i < 2048; i++)
        asum[i] = 0.;
}

/* add a number into array */
void addtosum(double d, double asum[2048])
{
size_t i;
    while(1){
        /* i = exponent of d */
        i = ((size_t)((*(unsigned long long *)&d)>>52))&0x7ff;
        if(i == 0x7ff){         /* max exponent, could be overflow */
            asum[i] += d;
            return;
        }
        if(asum[i] == 0.){      /* if empty slot store d */
            asum[i] = d;
            return;
        }
        d += asum[i];           /* else add slot to d, clear slot */
        asum[i] = 0.;           /* and continue until empty slot */
    }
}

/* return sum from array */
double returnsum(double asum[2048])
{
double sum = 0.;
size_t i;
    for(i = 0; i < 2048; i++)
        sum += asum[i];
    return sum;
}

---

Your floats should be added in double precision. That will give you more additional precision than any other technique can. For a bit more precision and significantly more speed, you can create say four sums, and add them up at the end.

If you are adding double precision numbers, use long double for the sum - however, this will only have a positive effect in implementations where long double actually has more precision than double (typically x86, PowerPC depending on compiler settings).

---

Regarding sorting, it seems to me that if you expect cancellation then the numbers should be added in descending order of magnitude, not ascending. For instance:

((-1 + 1) + 1e-20) will give 1e-20

but

((1e-20 + 1) - 1) will give 0

In the first equation that two large numbers are cancelled out, whereas in the second the 1e-20 term gets lost when added to 1, since there is not enough precision to retain it.

Also, pairwise summation is pretty decent for summing lots of numbers.

참고URL : https://stackoverflow.com/questions/6699066/in-which-order-should-floats-be-added-to-get-the-most-precise-result