부동 소수점 번호를 많이 요약하는 것이 가장 좋습니까?

StackOverflow https://stackoverflow.com/questions/394174

문제

모든 종류의 크기의 큰 부동 소수점 번호가 있다고 상상해보십시오. 최소 오류로 합계를 계산하는 가장 올바른 방법은 무엇입니까? 예를 들어 배열이 다음과 같이 보일 때 다음과 같습니다.

[1.0, 1e-10, 1e-10, ... 1e-10.0]

그리고 당신은 간단한 루프로 왼쪽에서 오른쪽으로 추가합니다.

sum = 0
numbers.each do |val|
    sum += val
end

추가 할 때마다 더 작은 숫자가 정밀 임계 값 아래로 떨어질 수 있으므로 오류가 커지고 커질 수 있습니다. 내가 아는 한 가장 좋은 방법은 배열을 정렬하고 가장 낮은 곳에서 가장 높은 숫자를 추가하기 시작하지만 더 나은 방법 (더 빠르고 정확한)이 있는지 궁금합니다.

편집하다: 답변 주셔서 감사합니다. 이제 Java에서 이중 값을 완벽하게 요약하는 작업 코드가 있습니다. 그것은 승리 답변의 파이썬 포스트에서 직선 포트입니다. 솔루션은 모든 단위 테스트를 통과합니다. (더 길지만 최적화 된 버전은 여기에서 사용할 수 있습니다. Summarizer.java)

/**
 * Adds up numbers in an array with perfect precision, and in O(n).
 * 
 * @see http://code.activestate.com/recipes/393090/
 */
public class Summarizer {

    /**
     * Perfectly sums up numbers, without rounding errors (if at all possible).
     * 
     * @param values
     *            The values to sum up.
     * @return The sum.
     */
    public static double msum(double... values) {
        List<Double> partials = new ArrayList<Double>();
        for (double x : values) {
            int i = 0;
            for (double y : partials) {
                if (Math.abs(x) < Math.abs(y)) {
                    double tmp = x;
                    x = y;
                    y = tmp;
                }
                double hi = x + y;
                double lo = y - (hi - x);
                if (lo != 0.0) {
                    partials.set(i, lo);
                    ++i;
                }
                x = hi;
            }
            if (i < partials.size()) {
                partials.set(i, x);
                partials.subList(i + 1, partials.size()).clear();
            } else {
                partials.add(x);
            }
        }
        return sum(partials);
    }

    /**
     * Sums up the rest of the partial numbers which cannot be summed up without
     * loss of precision.
     */
    public static double sum(Collection<Double> values) {
        double s = 0.0;
        for (Double d : values) {
            s += d;
        }
        return s;
    }
}
도움이 되었습니까?

해결책

"더 정확한": 파이썬 요리 책 의이 레시피 서브 토탈을 추적하여 전체 정밀도를 유지하는 합산 알고리즘이 있습니다. 코드는 파이썬에 있지만 파이썬을 모르더라도 다른 언어에 적응하기에 충분히 분명합니다.

모든 세부 사항이 제공됩니다 이 종이.

다른 팁

또한보십시오: 카한 합산 알고리즘 O (N) 저장이 필요하지 않고 O (1) 만 필요합니다.

원하는 것에 따라 많은 알고리즘이 있습니다. 일반적으로 부분 합계를 추적해야합니다. 합계 x [k+1] -x [k] 만 유지하면 Kahan 알고리즘이 나타납니다. 모든 부분 합계 (따라서 O (n^2) 알고리즘을 산출하는 경우)를 추적하면 @DF의 답변이 나타납니다.

귀하의 문제에 추가로 수치를 합산합니다. 다른 징후 매우 문제가 있습니다.

이제 모든 부분 합계를 추적하는 것보다 간단한 레시피가 있습니다.

  • 합산하기 전에 숫자를 정렬하고 모든 네거티브와 긍정적 인 것을 독립적으로 합산하십시오. 숫자를 정렬 한 경우 괜찮습니다. 그렇지 않으면 O (N log N) 알고리즘이 있습니다. 크기를 증가시켜 합계.
  • 쌍으로 합계, 쌍 쌍 등

개인적인 경험은 일반적으로 Kahan의 방법보다 더 멋진 것을 필요로하지 않는다는 것을 보여줍니다.

글쎄, 당신이 정렬하고 싶지 않다면, 당신은 단순히 개별 값보다 더 높은 정밀도의 유형의 변수로 총계를 유지할 수 있습니다 (예 : 두 배를 사용하여 플로트의 합을 유지하거나 "쿼드"를 유지합니다. 복식의 합). 이것은 성과 페널티를 부과하지만 분류 비용보다 적을 수 있습니다.

응용 프로그램이 숫자 처리에 의존하는 경우 임의의 정밀 산술 라이브러리를 검색하지만 이러한 종류의 파이썬 라이브러리가 있는지 모르겠습니다. 물론, 모두가 원하는 정밀 자릿수의 수에 따라 다릅니다.주의해서 사용하면 표준 IEEE 부동 소수점으로 좋은 결과를 얻을 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top