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

Solange Sie keine genaue geschlossene Form verwenden, ist eine von klein nach groß geordnete Summierung wahrscheinlich die genaueste einfache Lösung (mir ist nicht klar, warum eine log-exp helfen würde - das ist zwar ein netter Trick, aber damit gewinnen Sie hier nichts, soweit ich das beurteilen kann).

Sie können noch mehr Präzision erreichen, wenn Sie sich vergegenwärtigen, dass die Summe nach einer gewissen Zeit "quantisiert" wird: Wenn Sie eine Genauigkeit von 2 Stellen haben, ergibt die Addition von 1,3 zu 41 42 und nicht 42,3 - aber Sie erreichen fast eine Verdoppelung der Genauigkeit, indem Sie einen "Fehlerterm" beibehalten. Dies wird als Kahan-Resümee . Man berechnet den Fehlerterm (42-41-1,3 == -0,3) und korrigiert ihn bei der nächsten Addition, indem man 0,3 zum nächsten Term addiert, bevor man ihn wieder hinzufügt.

Kahan Summation zusätzlich zu einer kleinen bis großen Bestellung ist wahrscheinlich so genau, wie Sie jemals brauchen werden. Ich bezweifle ernsthaft, dass Sie jemals etwas Besseres für die harmonische Reihe brauchen werden - schließlich haben Sie es selbst nach 2^45 Iterationen (wahnsinnig viele) nur mit Zahlen zu tun, die mindestens 1/2^45 groß sind, und einer Summe, die in der Größenordnung von 45 (<2^6) liegt, was einem Größenunterschied von 51 Zweierpotenzen entspricht - d.h. sogar noch in einer Variablen mit doppelter Genauigkeit darstellbar ist, wenn Sie die "falsche" Reihenfolge hinzufügen.

Wenn man von klein nach groß geht und die Kahan-Summation verwendet, wird die Sonne wahrscheinlich erlöschen, bevor die heutigen Prozessoren ein Prozent des Fehlers erreichen - und man stößt auf andere knifflige Genauigkeitsprobleme, allein aufgrund des individuellen Termfehlers auf dieser Skala (da eine Zahl in der Größenordnung von 2^53 oder größer ohnehin nicht genau als Pasch dargestellt werden kann).

Answer 2

Ich bin mir nicht sicher, ob die Reihenfolge der Summierung eine wichtige Rolle spielt, ich habe das noch nie gehört. Ich vermute, Sie wollen dies in Fließkomma-Arithmetik tun, also ist das erste, was mehr inline von (1.0/1.0 + 1.0/2.0+1.0/3.0) zu denken - sonst wird der Compiler Integer-Division tun

um die Reihenfolge der Auswertung zu bestimmen, vielleicht eine for-Schleife oder Klammern?

z.B..

float f = 0.0;
for (int i=n; i>0; --i) 
{
    f += 1.0/static_cast<float>(i);
}

oh vergessen zu sagen, Compiler haben normalerweise Schalter, um den Fließkomma-Auswertungsmodus zu bestimmen. Dies hängt vielleicht damit zusammen, was Sie über die Reihenfolge der Summierung sagen - in Visual C+ finden Sie diese in den Code-Generierungskompilierungseinstellungen, in G++ gibt es die Optionen -float, die dies handhaben

Eigentlich hat der andere Typ recht - man sollte die Summierung in der Reihenfolge der kleinsten Komponente zuerst durchführen; also 1/n + 1/(n-1) 1/1

Dies liegt daran, dass die Genauigkeit einer Gleitkommazahl mit der Skala verknüpft ist. Wenn Sie bei 1 beginnen, haben Sie 23 Bits Genauigkeit relativ zu 1,0. Wenn Sie bei einer kleineren Zahl beginnen, ist die Genauigkeit relativ zu der kleineren Zahl, so dass Sie 23 Bits Genauigkeit relativ zu 1xe-200 oder was auch immer erhalten. wenn die Zahl größer wird, treten Rundungsfehler auf, aber der Gesamtfehler ist geringer als in der anderen Richtung