Genaue Auswertung von 1/1 + 1/2 + ... 1/n Reihe

Question

Ich muss die Summe der Zeile auswerten: 1/1+1/2+1/3+...+1/n. In Anbetracht der Tatsache, dass in C++ die Auswertungen nicht vollständig genau sind, spielt die Reihenfolge der Summierung eine wichtige Rolle. Der Ausdruck 1/n+1/(n-1)+...+1/2+1/1 liefert das genauere Ergebnis. Ich muss also die Reihenfolge der Summierung herausfinden, die die maximale Genauigkeit liefert. Ich weiß nicht einmal, wo ich anfangen soll. Die bevorzugte Sprache für die Umsetzung ist C++. Bitte entschuldigen Sie mein Englisch, falls es irgendwelche Fehler gibt.

Answer 1

F h ;

A

H

E

I

Answer 2

Der Grund für die mangelnde Genauigkeit liegt in der Präzision der Typen float, double und long double. Sie können nur so viele "Dezimalstellen" speichern. Wenn man also einen sehr kleinen Wert zu einem großen Wert hinzufügt, hat das keine Auswirkung, der kleine Term geht in dem größeren "verloren".

Die Reihe, die Sie summieren, hat einen "langen Schwanz" in dem Sinne, dass sich die kleinen Terme zu einem großen Beitrag summieren sollten. Wenn Sie aber in absteigender Reihenfolge summieren, dann wird nach einer Weile jeder neue kleine Term

I

Answer 3

Ich weiß gar nicht, wo ich anfangen soll.

Hier: Was jeder Informatiker über Fließkommaarithmetik wissen sollte

Answer 4

Wenn Sie die Summierung für ein großes N durchführen, ist das Addieren in der Reihenfolge vom kleinsten zum größten Wert nicht der beste Weg - Sie können immer noch in eine Situation geraten, in der die Zahlen, die Sie addieren, relativ zur Summe zu klein sind, um ein genaues Ergebnis zu erzielen.

Betrachten Sie das Problem folgendermaßen: Sie haben N Summen, unabhängig von der Reihenfolge, und Sie möchten den geringsten Gesamtfehler haben. Sie sollten also in der Lage sein, den geringsten Gesamtfehler zu erzielen, indem Sie den Fehler jeder Summierung minimieren - und Sie minimieren den Fehler in einer Summierung, indem Sie Werte addieren, die so nahe wie möglich beieinander liegen. Ich glaube, wenn man dieser Logik folgt, erhält man einen binären Baum von Teilsummen:

Sum[0,i] = value[i]

Sum[1,i/2] = Sum[0,i] + Sum[0,i+1]

Sum[j+1,i/2] = Sum[j,i] + Sum[j,i+1]

und so weiter, bis Sie zu einer einzigen Antwort kommen.

Wenn N keine Zweierpotenz ist, bleiben natürlich in jeder Stufe Reste übrig, die in die Additionen der nächsten Stufe übernommen werden müssen.

(Die Ränder von StackOverflow sind natürlich zu klein, um einen Beweis dafür zu liefern, dass dies optimal ist. Das liegt zum Teil daran, dass ich mir nicht die Zeit genommen habe, es zu beweisen. Aber es funktioniert für jedes N, egal wie groß es ist, da alle Additionen Werte von nahezu identischer Größe addieren. Nun, alle bis auf log(N) im schlimmsten Fall, der keine Potenz von 2 ist, und das ist verschwindend klein im Vergleich zu N.)

Answer 5

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic Sie können Bibliotheken mit gebrauchsfertigen Implementierungen für C/C++ finden.

Zum Beispiel http://www.apfloat.org/apfloat/