Genaue Bewertung von 1/1 + 1/2 + ... 1 / n Zeile

Wenn Sie die Summierung für große N durchführen, ist das Hinzufügen der Reihenfolge von der kleinsten zur größten nicht der beste Weg - Sie können immer noch in eine Situation kommen, in der die Zahlen, die Sie hinzufügen, zu klein sind Summe, um ein genaues Ergebnis zu erzielen.

Sehen Sie sich das Problem so an: Sie haben N Summierungen, unabhängig von der Reihenfolge, und Sie möchten den geringsten Gesamtfehler haben. Daher sollten Sie in der Lage sein, den kleinsten Gesamtfehler zu erhalten, indem Sie den Fehler jeder Summierung minimieren - und Sie minimieren den Fehler in einer Summierung, indem Sie Werte so nahe wie möglich hinzufügen. Ich glaube, dass das Folgen dieser Logik einen binären Baum von Teilsummen ergibt:

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.

Natürlich, wenn N keine Zweierpotenz ist, werden Sie in jeder Phase Reste übrig haben, die Sie in der nächsten Stufe in die Summierungen übertragen müssen.

(Die Ränder von StackOverflow sind natürlich zu klein, um einen Beweis dafür zu liefern, dass dies optimal ist. Zum Teil, weil ich mir nicht die Zeit genommen habe, es zu beweisen. Aber es funktioniert für jedes N, egal wie groß die Additionen addieren Werte von nahezu identischer Größe Nun, alle außer log (N) von ihnen im schlechtesten Nicht-Potenz-2-Fall, und das ist verschwindend klein im Vergleich zu N.)

Für große n sollten Sie besser asymptotische Formeln verwenden, wie die auf Ссылка ;

Eine andere Möglichkeit ist die Verwendung von exp-log Transformation. Grundsätzlich:

H_n = 1 + 1/2 + 1/3 + ... + 1 / n = log (exp (1 + 1/2 + 1/3 + ... + 1 / n)) = log (exp (1) * exp (1/2) * exp (1/3) * ... * exp (1 / n)).

Exponenten und Logarithmen können von Ihrer Standardbibliothek ziemlich schnell und genau berechnet werden. Mit Multiplikation sollten Sie viel genauere Ergebnisse erhalten.

Wenn dies Ihre Hausaufgaben sind und Sie eine einfache Ergänzung benötigen, fügen Sie besser von der kleinsten zur größten hinzu, wie andere vorgeschlagen haben.

Der Grund für die mangelnde Genauigkeit ist die Genauigkeit der Float-, Double- und Long-Double-Typen. Sie speichern nur so viele "Dezimalstellen". Das Hinzufügen eines sehr kleinen Werts zu einem großen Wert hat keine Auswirkung, der kleine Ausdruck ist in dem größeren "verloren".

Die Serie, die du summierst, hat einen "langen Schwanz" in dem Sinne, dass die kleinen Begriffe zu einem großen Beitrag summieren sollten. Wenn Sie jedoch in absteigender Reihenfolge summieren, hat jeder neue kleine Ausdruck nach einer Weile keine Wirkung mehr (sogar davor werden die meisten Dezimalstellen verworfen). Sobald Sie an diesen Punkt kommen, können Sie eine Milliarde weitere Terme hinzufügen, und wenn Sie sie nacheinander ausführen, hat das immer noch keine Auswirkungen.

Ich denke, dass die Summierung in aufsteigender Reihenfolge die beste Genauigkeit für diese Art von Serie geben sollte, obwohl es möglich ist, dass einige Eckenfehler auftreten, bei denen Fehler aufgrund von Rundungen auf Potenzen von 1/2 auftreten könnten Antwort für einige Zusatzaufträge als andere. Sie können das wahrscheinlich nicht wirklich vorhersagen.

Ссылка Sie können Bibliotheken mit gebrauchsfertiger Implementierung für C / C ++ finden.

Zum Beispiel Ссылка

Wenn Sie nicht eine genaue geschlossene Darstellung verwenden, ist eine kleine bis große geordnete Summe wahrscheinlich die genaueste einfache Lösung (es ist mir nicht klar, warum ein Log-Exp helfen würde - das ist ein netter Trick, aber Sie Ich werde nichts damit gewinnen, soweit ich das beurteilen kann.

Sie können die Genauigkeit weiter erhöhen, indem Sie erkennen, dass die Summe nach einer Weile "quantisiert" wird: Wenn Sie zwei Stellen haben, ergibt das Hinzufügen von 1,3 zu 41 Ergebnissen 42 statt 42,3 - aber Sie erreichen fast eine Genauigkeit Verdoppelung durch Beibehaltung eines "Fehler" -Begriffs. Dies wird Kahan Summation genannt. Sie würden den Fehlerterm (42-41-1.3 == -0.3) berechnen und diesen in der nächsten Addition korrigieren, indem Sie 0,3 zum nächsten Term hinzufügen, bevor Sie ihn erneut hinzufügen.

Kahan Summation zusätzlich zu einer kleinen bis großen Bestellung ist wahrscheinlich so genau wie Sie jemals brauchen werden. Ich bezweifle ernsthaft, dass du jemals etwas Besseres für die harmonische Serie brauchen wirst - schließlich, selbst nach 2 ^ 45 Iterationen (verrückt viele), würdest du immer noch nur Zahlen haben, die mindestens 1/2 ^ 45 groß sind, und eine Summe, die in der Größenordnung von 45 (& lt; 2 ^ 6) liegt, für eine Grßenordnungsdifferenz von 51 Zehnerpotenzen - dh sogar noch in einer Doppelpräzisionsvariablen darstellbar, wenn Sie die "falsche" Reihenfolge hinzufügen / p>

Wenn du klein zu groß gehst und Kahan Summation verwendest, wird die Sonne wahrscheinlich erlöschen, bevor die heutigen Prozessoren einen Fehlerprozentsatz erreichen - und du wirst anderen schwierigen Genauigkeitsproblemen begegnen, nur aufgrund des individuellen Laufzeitfehlers diese Skala sowieso (da eine Zahl in der Grössenordnung von 2 ^ 53 oder größer sowieso nicht als Doppelbild dargestellt werden kann).

Ich bin mir nicht sicher, ob die Reihenfolge der Summen eine wichtige Rolle spielt, ich habe das vorher noch nicht gehört. Ich denke, Sie wollen dies in Fließkomma-Arithmetik tun, so dass die erste Sache ist, mehr inline von (1.0 / 1.0 + 1.0 / 2.0 + 1.0 / 3.0) zu denken - ansonsten wird der Compiler eine ganzzahlige Division machen

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

z.B.

oh vergessen zu sagen, Compiler werden normalerweise Schalter haben, um den Gleitkommaauswertungsmodus zu bestimmen. das hängt vielleicht mit dem zusammen, was Sie über die Reihenfolge der Summation sagen - in visual C + sind diese in Code-Generierungs-Kompilierungseinstellungen zu finden, in g ++ gibt es Optionen -float, die das handhaben

Tatsächlich hat der andere Typ recht - Sie sollten zuerst die Summe in der Reihenfolge der kleinsten Komponente berechnen; damit 1 / n + 1 / (n-1) .. 1/1

Dies liegt daran, dass die Genauigkeit einer Fließkommazahl mit der Skala verknüpft ist. Wenn Sie bei 1 beginnen, haben Sie 23 Genauigkeitsbits 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 im Vergleich zu 1xe-200 oder was auch immer erhalten. Wenn dann die Zahl größer wird, wird ein Rundungsfehler auftreten, aber der Gesamtfehler ist geringer als die andere Richtung

Da alle Ihre Zahlen rationale sind, wäre es am einfachsten (und vielleicht auch am schnellsten, da weniger Gleitkommaoperationen erforderlich sind), die Berechnungen mit Rationalen durchzuführen (Tupel von 2 ganzen Zahlen p, q) und dann mache nur eine Gleitkomma-Division am Ende.

update Um diese Technik effektiv zu nutzen, müssen Sie bigints für p & amp; amp; q, wie sie ziemlich schnell wachsen ...

Ein schneller Prototyp in Lisp, der eingebaute Rationales zeigt:

Die nächstbeste Option könnte also sein, die Liste der Fließkomma-Punkte beizubehalten und sie so zu reduzieren, dass die beiden kleinsten Zahlen in jedem Schritt summiert werden ...