Wiederkehrende Formeln zur Berechnung von Fehlern der iterativen Summierung von Binärzahlen begrenzter Länge

    In diesem Artikel beschäftigen wir uns weiterhin mit dem Problem der Computerberechnung von Dezimalzahlen mit binärer Arithmetik, das im vorherigen Thema [1] behandelt wurde. Der Artikel konzentriert sich auf Fehler, die in der Literatur allgemein als Rundungsfehler bezeichnet werden. Und insbesondere Fehler, die sich aus der iterativen Summierung einer großen Anzahl identischer Dezimalzahlen ergeben, die in binärer Form durch einen begrenzten Bitraum dargestellt werden. Als Ergebnis der Studien wurden einfache Wiederholungsrelationen erhalten, die es ermöglichen, den Fehler computeriterativer Berechnungen von Teilsummen einer beliebigen Anzahl identischer Terme in jedem Schritt der Iteration genau zu bestimmen.

    Wir betrachten echte positive Binärzahlen mit einer festen Anzahl von L signifikanten Stellen. Mit einer festen Anzahl von L signifikanten Stellen meinen wir L Stellen, die von links nach rechts gezählt werden, beginnend mit der höchsten Stelle ungleich Null. Fehlt L, wird die Anzahl der Ziffern in der Zahl rechts mit Nullen aufgefüllt. Wenn also die Anzahl der signifikanten Stellen mit dem Wert L = 5 festgelegt ist, hat die Zahl 0,0011 die folgenden signifikanten Stellen: 11000. Wenn wir unsere Zahl nun als Gleitkommazahl auf einen 5-Bit-Computer schreiben, wird sie im Bereich der Maschinenmantisse geschrieben: .11000 . Diese Zahl wird im Computer in normalisierter Form mit einem Exponenten von 2 ^ -2 dargestellt.

    Eine Gleitkommazahl wird in einem Maschinenwort als das Produkt einer gebrochenen Mantisse von einem Exponenten geschrieben, dessen Reihenfolge die Position des Punktes in einer in natürlicher Form dargestellten Zahl angibt. Wenn die Anzahl der Stellen der Mantisse der Zahl nicht mit der Anzahl L der Stellen der Maschinenmantisse übereinstimmt, wird die Zahl normalisiert, indem die Mantisse in die eine oder andere Richtung verschoben wird, so dass sich die höchste von Null verschiedene Stelle der Zahl im höchsten Bit der Maschinenmantisse befindet. In diesem Fall wird die Reihenfolge des Exponenten an die Anzahl der Schichten angepasst.

    Betrachten Sie die Zahl in natürlicher Form. Wenn die Anzahl ihrer signifikanten Stellen eine bestimmte feste Anzahl von L Stellen überschreitet, muss sie so konvertiert werden, dass die Anzahl ihrer signifikanten Stellen gleich L wird. Dies wird erreicht, indem die besonders niedrigen Stellen verworfen werden. Wenn Sie die unteren Ziffern verwerfen, kann die Zahl auf L Ziffern gerundet werden, oder es werden einfach die besonders niedrigen Ziffern abgeschnitten. Im Fall der Kürzung wird die Binärzahl 10.0011 in ihrer natürlichen Form für L = 5 als 10.001 geschrieben. Dieselbe Zahl, die in exponentiell normalisierter Form geschrieben wird, sieht aus wie 0,10001 * 2 ^ 2. Hier haben wir zwei äquivalente Einträge mit der gleichen Nummer.

    Die Reduktion einer in ihrer natürlichen Form dargestellten Zahl auf eine Zahl mit der Anzahl signifikanter Stellen L wird als Optimierung bezeichnet. Wir führen dieses Konzept ein, um es von der Normalisierung exponentiell geschriebener Zahlen zu unterscheiden. Aus mathematischer Sicht sind dies zwei gleichwertige Operationen.

    Als nächstes betrachten wir den Fall des Abschneidens der niedrigstwertigen Ziffern in einer Binärzahl ohne Rundung. Zahlen gelten als in ihrer natürlichen Form dargestellt.

    Angenommen, wir haben eine bestimmte Zahl 2 ^ p ≤ Z <2 ^ (p + 1), wobei p eine vorzeichenbehaftete ganze Zahl ist, die dem Abstand zwischen dem führenden Punkt und der führenden Ziffer ungleich Null in der Zahl Z in natürlicher Form entspricht. Befindet sich die führende Ziffer ungleich Null links vom Punkt, dann ist p> 0. Befindet sich die Ziffer rechts vom Punkt, dann ist p <0. Für die Zahl Z = 0.000101 haben wir also p = -4 und für diesen Fall: 2 ^ (- 4) ≤ Z <2 ^ (- 3).
    Man betrachte eine Folge von reellen Binärzahlen X 0 , X 1 , ... X i ..., die in den Intervallen liegen:
    2 ^ p ≤ X 0 <2 ^ (1 + p) ≤ X 1 <2 ^ (2 + p); .; 2 ^ (i + p) ≤ X i <2 ^ (i + p + 1) ...

    Zum Beispiel haben wir für p = -3 2 ^ p = 2 ^ -3 = 0,001. Unsere Folge sieht dann so aus: 0,001 ≤ X 0 <0,01 ≤ X 1 <0,1, ..., 2 ^ (i -3) ≤ X i <2 ^ (i -2) ...

    Nehmen Sie eine reelle Zahl 2 ^ (i +) p) ≤ X i <2 ^ (i + p + 1) mit einer begrenzten Anzahl von L signifikanten Stellen. Als nächstes nehmen wir die Summe der k i -Elementarterme: Z + Z + ... = k i Z, wobei Z = X 0 , k i ≥ 0 eine ganze Zahl ist. Wir wählen k i so, dass 2 ^ (i + p) ≤ X i + k i Z <2 ^ (i + p +1). In diesem Betrag ist die maximale Anzahl k iElementarterme Z, bei denen der Wert der Summe die rechte Grenze des Intervalls nicht überschreitet, ergeben sich aus der Formel k i = (2 ^ (i + p + 1) -X i ) / Z⌋, wobei die Klammern ⌊ ⌊ das Runden auf die nächste ganze Zahl in bedeuten kleinere Seite.

    Wenn wir nun einen weiteren Elementarterm Z zu X i + k i Z addieren, erhalten wir X i + 1 = X i + k i Z + Z = X i + Z (k i + 1) ≥ 2 ^ (i + p + 1) ) Der Wert des neu empfangenen Betrags überschreitet den rechten Grenzwert des Intervalls oder entspricht diesem. Daher ist die Anzahl der Ziffern in der Zahl X i + 1 = X i + Z (k i+1) wird zu L + 1. Um die Anforderung zu erfüllen, dass die Anzahl der signifikanten Stellen gleich L ist, muss die resultierende Anzahl optimiert werden, d.h. führen zu einer Zahl, in der es L signifikante Stellen geben wird. Dazu muss die niedrigste Ziffer verworfen werden. Der Betrieb der niedrigstwertigen Ziffer in der Anzahl der X Verwerfen i durch die X bezeichnet wird , i ¬1 . Wenn wir zum Beispiel in der Zahl X = 10.0011 eine niedrigstwertige Ziffer verwerfen, wird sie als X1 = 10.001 geschrieben . Im allgemeinen Fall bedeutet das Schreiben von Xt , dass t niederwertige Bits aus X herausfallen.

    Nach einer Teilsumme X i + 1 = X i + Z (k i+1) überschreitet den Wert 2 ^ (i + p +1), den wir als rechten Grenzwert bezeichnen. Die höchste Ziffer der Summe ungleich Null wird vom Festpunkt nach links verschoben. Die Gesamtzahl der signifikanten Stellen übersteigt die Zahl L um eins und das Ergebnis sollte optimiert werden. Als i-ten Schritt Iteration in Optimierungsergebnis unter X i jüngere Ziffer verworfen wird, wird die Zahl gleich X i ¬1 , dann sind die am wenigsten signifikante Ziffer des Begriff Z auch verworfen werden kann, da Weitere Berechnungen werden dadurch nicht beeinflusst.

    Zum Beispiel. Es sei L = 5. Suchen Sie die Summe zweier Zahlen X = 1.10111 und Z = 0.10011. Weil Wenn die Anzahl der Stellen in X den Wert von L überschreitet, muss dies optimiert werden. Nach der Optimierung erhalten wir: X ¬1= 1,1011. Fügen Sie zu dieser Zahl Z = 0.1001 ** 1 ** hinzu. Wir erhalten X1 + Z = 1.1011 + 0.1001 ** 1 ** = 10.0100 ** 1 **. Hier ist die Anzahl der Nachkommastellen im Term X ¬1 kleiner als die Anzahl der Ziffern im Term Z. Daher addiert sich die niedrigste fettgedruckte Ziffer in Z immer zu Null, und das Ergebnis der Addition der unteren Ziffern liegt in diesem Fall außerhalb des Bereichs L signifikante Stellen und daher, wenn sie abgeschnitten sind, hat dies keinen Einfluss auf den Gesamtbetrag. Daraus folgt, dass sich die Summe nicht ändert, wenn X ¬1 + Z ¬1 = 1.1011 + 0.1001 = 10.0100 geschrieben wird. Da die Anzahl der Stellen in dieser Summe den Wert von L überschreitet, sollte auch die resultierende Anzahl optimiert werden. Wenn wir die niedrigste Ziffer verwerfen, erhalten wir eine optimierte Zahl 10.010 mit L = 5 signifikanten Ziffern.

    Somit unterscheiden sich die Werte der Teilsummen X i und X i + 1 um maximal k i Elementarterme. Die Anzahl der signifikanten Stellen der Teilsummen, die im Intervall [X i , X i + 1 ) liegen, ist L, und daher werden ihre Werte ohne Rundung berechnet und führen dementsprechend nicht zu Fehlern. Addition (k i + 1) des Ausdrucks zu einer Teilsumme führt zum Überschreiten des rechten Grenzwertes oder seiner Gleichheit. Wenn die Teilsumme in einem Schritt der Iteration den rechten Grenzwert überschreitet oder diesem entspricht, wird die Anzahl der signifikanten Stellen in der Summe zu L + 1, und eine Optimierung ist erforderlich. Nach jedem Überschreiten des rechten Grenzwertes verringert sich die Anzahl der signifikanten Stellen der an der Bildung neuer Teilsummen beteiligten Elementarterme Z um eins und nach dem i-ten rechten Grenzwert wird der Elementarterm gleich Zi .

    X i + 1 = (X i + (k i + 1 + 1 ) Z i ) 1 , X 0 = Z i = 0,1 ...

    k i + 1 = ⌊ (2 ^ (p + i) - Xi ) / Z ¬i ⌋ , p ist eine vorzeichenbehaftete ganze Zahl.


    Die Iterationsschrittzahl N i + 1, bei der die Teilsumme X i + 1 den rechten Grenzwert überschritten hat, kann durch die Wiederholungsrelation bestimmt werden:

    N i + 1 = (k i + 1 + 1 ) + N i .

    Betrachten Sie nun, welchen Fehler wir erhalten, wenn wir als Ergebnis der Kürzungsoperation in Binärform dargestellte dezimale reelle Zahlen iterativ aufsummieren.

    Es ist bekannt, dass jede in binärer Form dargestellte Dezimalzahl X nach dem Abschneiden der Anzahl signifikanter Stellen als X = B + g geschrieben werden kann, wobei B eine Darstellung der Dezimalzahl X in binärer Form mit einer begrenzten festen Anzahl signifikanter Stellen ist, g der absolute Fehler ist Darstellungen der Zahl als Ergebnis der Kürzung. Dieser Fehler kann definiert werden als g = XB, g ≥0. Wenn i elementare Terme summiert werden, akkumuliert sich dieser Fehler und wird gleich ig.

    Dies ist jedoch nicht der einzige Fehler, der beim rekursiven Hinzufügen identischer elementarer Terme auftritt. Durch Rundung oder Kürzung entstehen bei der rekursiven Berechnung von Teilbeträgen auch Rundungsfehler.

    Die von uns abgeleiteten Wiederholungsrelationen ermöglichen es uns, in jedem Schritt der Iteration die genauen Werte des Fehlers bei der Berechnung der Summe der elementaren Terme mit denselben Werten zu erhalten.

    Betrachten Sie zum Beispiel Teilsummen der Elementarterme Z = 0,0011101, für die L = 5 ist. Für die Zahl Z haben wir p = 0,001. Tabelle 1 zeigt die Ergebnisse des Addierens von 10 elementaren Termen für jeden Iterationsschritt.


    In Spalte 1 der Tabelle sind die Zahlen i der Teilsummen X i angegeben , die die rechte Grenze des Intervalls überschritten haben oder gleich geworden sind. Die zweite Spalte zeigt die Iterationsnummern j. Spalte 3 zeigt die Notation der Teilsummen X i für einen bestimmten Wert von i. In Spalte 4 der Tabelle sind die Bezeichnungen der Teilsummen S j und der Elementarsummanden Z ¬i für jeden Iterationsschritt untereinander angegeben . Spalte 5 zeigt jeweils untereinander die Werte der Teilsummen S j und der Elementarterme Z ¬i für jeden Iterationsschritt. Rote Buchstaben kennzeichnen Ziffern von Zahlen, die nicht an der Bildung von Teilsummen beteiligt sind. Spalte 6 zeigt die Werte der Koeffizienten ki + 1 + 1 , die in unserer Wiederholungsformel zur Berechnung von X i + 1 verwendet werden . Spalte 7 zeigt jeweils untereinander die Werte der Teilsummen S j und der Elementarterme Z ¬i für jeden Iterationsschritt in dezimaler Form. In Spalte 8 sind die theoretischen Werte der Summen der Elementarterme Z angegeben, sofern Rundungsfehler nicht berücksichtigt werden. Die Spalte 9 zeigt die Werte der absoluten Fehler der Berechnung bei jedem Schritt der Iteration, die nach der Formel Δ = (S j ) 10 - jZ ¬0 berechnet werden . Die Spalte 9 zeigt die relativen Fehler, die durch die Formel berechnet werden: δ = Δ / jZ ¬0 .

    Wie aus der Tabelle ersichtlich ist, wird selbst unter der Voraussetzung, dass die Elementarterme ohne Darstellungsfehler genau dargestellt werden, während der iterativen Summierung sehr schnell ein derartiger Fehlerwert gebildet, dass Berechnungen bei einem bestimmten Iterationsschritt bedeutungslos werden. Der Grund für diesen Fehler liegt in den Einschränkungen des Maschinenworts sowie im Normalisierungsverfahren oder in unserem Fall in der Optimierung der Darstellung von Zahlen.

    Nachfolgend geben wir Tabelle 2 an, die die Werte von Teilsummen während der iterativen Summierung der Dezimalzahl 0,1 in binärer Form mit einer festen Anzahl von signifikanten Stellen für 51-Bit-Mantissen darstellt. Die Tabelle zeigt die Werte von Teilsummen an Punkten, die die rechten Grenzwerte überschreiten. Die in der Tabelle fett gedruckten Zahlen sind binär. Zahlen, die nicht fett gedruckt sind, sind Zahlen, die im Dezimalcode dargestellt werden. Diese Tabelle zeigt die Werte der Teilsummen X i , die Werte der Koeffizienten k i + 1 +1 zum Auffinden der nächsten Teilsumme X i + 1 gemäß unseren Wiederholungsrelationen.

    Iterationsschrittnummer N i + 1ab dem die nächste Teilsumme den rechten Grenzwert überschreitet, kann durch die Wiederholungsrelation bestimmt werden: N i + 1 = (k i + 1 +1) + N i .



    Wie aus Tabelle 2 ersichtlich ist, haben wir mit der Anzahl der Iterationen 5368712233 bereits in 6 Stellen der Teilsumme die falsche Zahl. Der absolute Berechnungsfehler für diesen Fall beträgt Δ = 536871223.3 - 536870912.084052 = 311.215948. Und der relative Fehler ist gleich δ = 311,215948 / 536871223,3≈0,0000006 = 0,00006%.

    Zur gleichen Zeit, wenn man die Fehlerdarstellung einer Dezimalzahl 0,1 in binärer Form mit 51 signifikanter Stelle zu berechnen, dann haben wir: 0,1 = 0.0001100110011001100110011001100110011001100110011001100≈ 0,09999999999999997779
    delta = 0.1-0.09999999999999997779≈2.221 * 10 ^ (- 17),
    Delta = 2.221 * 10 ^ (- 17) / 0,1 = 2,221 * 10 ^ (- 16) = 14 * 10 ^ (- 14)%.

    Beim Iterationsschritt gleich 5368712233 nimmt der absolute Gesamtfehler der Darstellung den Wert 5368712233 * 14 * 10 ^ (- 18) ≤ 0,000000075 an. Der relative Darstellungsfehler ändert sich in keinem Schritt der Iteration.

    Wie wir sehen können, ist der absolute Fehler der Darstellung im Vergleich zu dem Rundungsfehler während der iterativen Summation vernachlässigbar.
    Die hier vorgestellten Wiederholungsformeln ermöglichten es, während der iterativen Summierung einer großen Anzahl identischer, im Binärcode dargestellter Dezimalterme genau berechnete Rundungsfehler zu erhalten.

    Der Autor dankt dem Benutzer mayorovp für die gefundenen Ungenauigkeiten.

    REFERENZEN
    1. habrahabr.ru/post/309812

    Jetzt auch beliebt: