Precisão numérica e algoritmos de classificação?

Question

Sedgewick e Wayne falam sobre como algoritmos de classificação e, especificamente, filas de prioridade são usados ​​para desenvolver maneiras de melhorar a precisão em cálculos de ponto flutuante: https://algs4.cs.princeton.edu/25applications/

A computação científica muitas vezes se preocupa com a precisão (quão perto estamos da resposta verdadeira?).A precisão é extremamente importante quando realizamos milhões de cálculos com valores estimados, como a representação de ponto flutuante de números reais que comumente usamos em computadores.Alguns algoritmos numéricos usam filas de prioridade e classificação para controlar a precisão dos cálculos.

Quais "algoritmos numéricos" usam filas de prioridade e classificação assim?

Answer 1

Vou te dar um exemplo simples.

Suponha que você tenha alguns números de ponto flutuante para somar.Assumiremos que todos não são negativos para que o cancelamento não seja um problema.

Para os fins deste exemplo, usarei decimal com quatro dígitos significativos de precisão apenas para ilustrar o ponto.

Os números são:

1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e+0

Ou seja, dez exemplares 1e-4 e uma cópia de 1.

Esta soma pode ser perfeitamente representada em nosso formato de ponto flutuante de brinquedo:

1.001e+0

Mas a resposta que você obtém depende da ordem em que você faz as adições!Se você começar no topo da lista e descer, as somas parciais serão:

1.000e-4
2.000e-4
3.000e-4
4.000e-4
5.000e-4
6.000e-4
7.000e-4
8.000e-4
9.000e-4
1.000e-3
1.001e+0

Mas se você começar de baixo e chegar ao topo, as somas parciais serão:

1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0

Claramente, você precisa adicionar os números pequenos primeiro.Então aqui estão dois algoritmos possíveis.

• Classifique os números em ordem crescente e some-os nessa ordem.
• Insira os números em uma fila de prioridade.Remova os dois números menores, some-os e insira a soma novamente na fila de prioridade.Repita até que reste um número.

Exercícios:

1. Existe um conjunto de números para os quais esses dois algoritmos retornam respostas diferentes?
2. Um desses algoritmos é melhor que o outro, no sentido de retornar sempre uma resposta final mais precisa?
3. Podemos fazer ainda melhor?