Qual a melhor forma de resumir lotes de números de ponto flutuante?

Question

Imagine que você tem uma grande variedade de números de ponto flutuante, de todos os tipos de tamanhos. Qual é a maneira mais correta para calcular a soma, com o mínimo de erro? Por exemplo, quando os olhares de matriz como este:

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

e você somar, da esquerda para a direita com um laço simples, como

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

sempre que você somar os números menores podem cair abaixo do limiar de precisão para que o erro fica cada vez maior. Tanto quanto eu sei que a melhor maneira é classificar a matriz e começar a adicionar números menor para o maior, mas eu estou querendo saber se existe uma maneira ainda melhor (mais rápido, mais preciso)?

Editar : Obrigado pela resposta, agora tenho um código de trabalho que resume perfeitamente valores double em Java. É um porto direto do pós Python da resposta vencedora. A solução passa de todos os testes de unidade. (A mais longa, mas a versão optimizada desta está disponível aqui 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;
    }
}

Answer 1

Para "mais preciso": esta receita no Python Cookbook tem algoritmos soma que mantêm a precisão total (por manter o controle dos subtotais). Código é em Python, mas mesmo se você não sabe Python é bastante claro para adaptar-se a qualquer outra língua.

Todos os detalhes são dadas em neste artigo .

Answer 2

Veja também: Kahan somatório algoritmo Não requer O (n) de armazenamento, mas apenas O (1).

Answer 3

Existem muitos algoritmos, dependendo do que você quer. Normalmente eles exigem manter o controle das somas parciais. Se você manter apenas o do somas x [k + 1] - x [k] algoritmo, você começa Kahan. Se você manter o controle de todas as somas parciais (daí resultando O (n ^ 2) algoritmo), você recebe a resposta de @dF.

Note que, adicionalmente, para o seu problema, soma números de diferentes sinais é muito problemática.

Agora, há receitas mais simples do que se manter a par de todas as somas parciais:

• Separar os números antes de soma, somar todos os negativos e os positivos de forma independente. Se você tem números classificadas, bem, caso contrário, você tem O (n log n) algoritmo. Soma aumentando magnitude.
• Sum por pares, em seguida, pares de pares, etc.

experiência pessoal mostra que você geralmente não precisa de coisas mais extravagantes do que o método de Kahan.

Answer 4

Bem, se você não quer classificar, então você pode simplesmente manter o total em uma variável com um tipo de maior precisão do que os valores individuais (por exemplo, usar uma dupla para manter a soma de carros alegóricos, ou de um "quad" para manter a soma de duplas). Isto irá impor uma penalidade de desempenho, mas pode ser menos do que o custo da classificação.

Answer 5

Se o seu aplicativo se baseia em pesquisa de processamento numérico para uma precisão biblioteca aritmética arbitrária, porém eu não sei se existem bibliotecas Python deste tipo. Claro, tudo depende de quantos dígitos de precisão que você quer - você pode conseguir bons resultados com ponto flutuante IEEE padrão se você usá-lo com cuidado

.