In welcher Reihenfolge sollten Floats hinzugefügt werden, um das genaueste Ergebnis zu erzielen?

105

Dies war eine Frage, die mir kürzlich bei meinem Interview gestellt wurde und die ich wissen möchte (ich erinnere mich nicht wirklich an die Theorie der numerischen Analyse, also helfen Sie mir bitte :)

Wenn wir eine Funktion haben, die Gleitkommazahlen akkumuliert:

std::accumulate(v.begin(), v.end(), 0.0);

vist ein std::vector<float>zum Beispiel.

  • Wäre es besser, diese Zahlen zu sortieren, bevor Sie sie akkumulieren?

  • Welche Reihenfolge würde die genaueste Antwort geben?

Ich vermute , dass die Sortieren Sie die Zahlen in aufsteigender Reihenfolge tatsächlich die numerischen Fehler machen würde weniger , aber leider kann ich es selbst nicht beweisen.

PS Mir ist klar, dass dies wahrscheinlich nichts mit realer Programmierung zu tun hat, nur neugierig zu sein.

Yippie-Ki-Yay
quelle
17
Dies hat eigentlich alles mit realer Programmierung zu tun. Viele Anwendungen kümmern sich jedoch nicht wirklich um die absolut beste Genauigkeit der Berechnung, solange sie "ziemlich nah" ist. Technische Anwendungen? Extrem wichtig. Medizinische Anwendungen? Extrem wichtig. Umfangreiche Statistiken? Etwas weniger Genauigkeit ist akzeptabel.
Zéychin
18
Bitte antworten Sie nur, wenn Sie es tatsächlich wissen und auf eine Seite verweisen können, auf der Ihre Argumentation ausführlich erläutert wird. Es gibt schon so viel Mist über herumfliegende Gleitkommazahlen, dass wir nichts hinzufügen wollen. Wenn du denkst, du weißt es. HALT. denn wenn du nur denkst, dass du es weißt, dann liegst du wahrscheinlich falsch.
Martin York
4
@ Zéychin "Technische Anwendungen? Extrem wichtig. Medizinische Anwendungen? Extrem wichtig." ??? Ich denke, Sie wären überrascht, wenn Sie die Wahrheit wüssten :)
BЈовић
3
@Zeychin Absoluter Fehler ist irrelevant. Wichtig ist der relative Fehler. Wenn einige Hundertstel eines Bogenmaßes 0,001% betragen, wen interessiert das dann?
BЈовић
3
Ich empfehle diese Lektüre wirklich: "Was jeder Informatiker über Gleitkomma wissen muss" perso.ens-lyon.fr/jean-michel.muller/goldberg.pdf
Mohammad Alaggan

Antworten:

108

Ihr Instinkt ist im Grunde richtig, das Sortieren in aufsteigender Reihenfolge (der Größe) verbessert normalerweise die Dinge etwas. Stellen Sie sich den Fall vor, in dem wir Floats mit einfacher Genauigkeit (32 Bit) hinzufügen und 1 Milliarde Werte gleich 1 / (1 Milliarde) und einen Wert gleich 1 sind. Wenn die 1 an erster Stelle steht, kommt die Summe auf 1, da 1 + (1/1 Milliarde) aufgrund von Genauigkeitsverlust 1 ist. Jede Addition hat keinerlei Einfluss auf die Gesamtsumme.

Wenn die kleinen Werte an erster Stelle stehen, summieren sie sich zumindest zu etwas, obwohl ich selbst dann 2 ^ 30 davon habe, während ich nach ungefähr 2 ^ 25 wieder in der Situation bin, in der jeder einzelne die Summe nicht beeinflusst nicht mehr. Also werde ich noch mehr Tricks brauchen.

Das ist ein Extremfall, aber im Allgemeinen ist das Hinzufügen von zwei Werten ähnlicher Größe genauer als das Hinzufügen von zwei Werten sehr unterschiedlicher Größen, da Sie auf diese Weise weniger Genauigkeitsbits in dem kleineren Wert "verwerfen". Indem Sie die Zahlen sortieren, gruppieren Sie Werte ähnlicher Größe, und indem Sie sie in aufsteigender Reihenfolge hinzufügen, geben Sie den kleinen Werten eine "Chance", kumulativ die Größe der größeren Zahlen zu erreichen.

Wenn es sich jedoch um negative Zahlen handelt, ist es einfach, diesen Ansatz zu "überlisten". Betrachten Sie drei Werte, um zu summieren {1, -1, 1 billionth}. Die arithmetisch korrekte Summe ist 1 billionth, aber wenn meine erste Addition den winzigen Wert beinhaltet, ist meine endgültige Summe 0. Von den 6 möglichen Ordnungen sind nur 2 "korrekt" - {1, -1, 1 billionth}und {-1, 1, 1 billionth}. Alle 6 Ordnungen liefern Ergebnisse, die auf der Skala des größten Größenwerts in der Eingabe (0,0000001% out) genau sind, aber für 4 von ihnen ist das Ergebnis auf der Skala der wahren Lösung (100% out) ungenau. Das spezielle Problem, das Sie lösen, zeigt Ihnen, ob das erstere gut genug ist oder nicht.

Tatsächlich können Sie viel mehr Streiche spielen, als sie nur in sortierter Reihenfolge hinzuzufügen. Wenn Sie viele sehr kleine Werte, eine mittlere Anzahl mittlerer Werte und eine kleine Anzahl großer Werte haben, ist es möglicherweise am genauesten, zuerst alle kleinen Werte zu addieren, dann die mittleren Werte separat zu addieren und diese beiden Summen zu addieren zusammen dann die großen hinzufügen. Es ist überhaupt nicht trivial, die genaueste Kombination von Gleitkomma-Additionen zu finden, aber um mit wirklich schlimmen Fällen fertig zu werden, können Sie eine ganze Reihe laufender Summen in verschiedenen Größen beibehalten und jeden neuen Wert zu der Summe hinzufügen, die seiner Größe am besten entspricht. und wenn eine laufende Summe für ihre Größe zu groß wird, addieren Sie sie zur nächsten Summe und starten Sie eine neue. Auf den logischen Punkt gebracht, entspricht dieser Prozess der Ausführung der Summe in einem Typ mit beliebiger Genauigkeit (also Sie ' d mach das). Angesichts der vereinfachten Wahl, in aufsteigender oder absteigender Größenordnung zu addieren, ist aufsteigend die bessere Wahl.

Es hat eine gewisse Beziehung zur realen Programmierung, da es einige Fälle gibt, in denen Ihre Berechnung sehr schlecht laufen kann, wenn Sie versehentlich einen "schweren" Schwanz abhacken, der aus einer großen Anzahl von Werten besteht, von denen jeder zu klein ist, um ihn einzeln zu beeinflussen die Summe, oder wenn Sie zu viel Präzision von vielen kleinen Werten wegwerfen, die einzeln nur die letzten Bits der Summe beeinflussen. In Fällen, in denen der Schwanz sowieso vernachlässigbar ist, ist es Ihnen wahrscheinlich egal. Zum Beispiel, wenn Sie zunächst nur eine kleine Anzahl von Werten addieren und nur einige signifikante Zahlen der Summe verwenden.

Steve Jessop
quelle
8
+1 zur Erklärung. Dies ist etwas kontraintuitiv, da die Addition normalerweise numerisch stabil ist (im Gegensatz zu Subtraktion und Division).
Konrad Rudolph
2
@Konrad, es kann numerisch stabil sein, aber es ist nicht präzise angesichts unterschiedlicher Größen von Operanden :)
MSN
3
@ 6502: Sie sind in der Größenordnung sortiert, sodass die -1 am Ende steht. Wenn der wahre Wert der Summe die Größe 1 hat, ist das in Ordnung. Wenn Sie drei Werte addieren: 1 / Milliarde, 1 und -1, erhalten Sie 0, und an diesem Punkt müssen Sie die interessante praktische Frage beantworten. Benötigen Sie eine Antwort, die auf der Skala der genau ist? wahre Summe, oder brauchen Sie nur eine Antwort, die auf der Skala der größten Werte genau ist? Für einige praktische Anwendungen ist Letzteres gut genug, aber wenn dies nicht der Fall ist, benötigen Sie einen differenzierteren Ansatz. Die Quantenphysik nutzt die Renormierung.
Steve Jessop
8
Wenn Sie sich an dieses einfache Schema halten, würde ich immer die beiden Zahlen mit der niedrigsten Größe addieren und die Summe wieder in die Menge einfügen. (Nun, wahrscheinlich würde eine Zusammenführungssortierung hier am besten funktionieren. Sie könnten den Teil des Arrays, der die zuvor summierten Zahlen enthält, als Arbeitsbereich für die Teilsummen verwenden.)
Neil
2
@ Kevin Panko: Die einfache Version ist, dass ein Float mit einfacher Genauigkeit 24 Binärziffern hat, von denen die größte das größte gesetzte Bit in der Zahl ist. Wenn Sie also zwei Zahlen addieren, deren Größe sich um mehr als 2 ^ 24 unterscheidet, erleiden Sie einen Totalverlust des kleineren Werts, und wenn sie sich in der Größe um einen geringeren Grad unterscheiden, verlieren Sie eine entsprechende Anzahl von Genauigkeitsbits des kleineren Nummer.
Steve Jessop
88

Es gibt auch einen Algorithmus für diese Art von Akkumulationsoperation namens Kahan Summation , den Sie wahrscheinlich kennen sollten.

Laut Wikipedia

Der Kahan-Summationsalgorithmus (auch als kompensierte Summation bezeichnet ) reduziert den numerischen Fehler in der Summe, der durch Hinzufügen einer Folge von Gleitkommazahlen mit endlicher Genauigkeit erhalten wird, im Vergleich zum offensichtlichen Ansatz erheblich. Dies erfolgt durch Beibehalten einer separaten Laufkompensation (eine Variable zum Akkumulieren kleiner Fehler).

Im Pseudocode lautet der Algorithmus:

function kahanSum(input)
 var sum = input[1]
 var c = 0.0          //A running compensation for lost low-order bits.
 for i = 2 to input.length
  y = input[i] - c    //So far, so good: c is zero.
  t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
  c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
  sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
 next i               //Next time around, the lost low part will be added to y in a fresh attempt.
return sum
Daniel Pryden
quelle
3
+1 schöne Ergänzung zu diesem Thread. Jeder Compiler, der diese Anweisungen "eifrig optimiert", sollte gesperrt werden.
Chris A.
1
Es ist eine einfache Methode , um fast die Präzision zu verdoppeln, indem man zwei Summenvariablen sumund cdie Größe unterscheiden. Es kann trivial auf N Variablen erweitert werden.
MSalters
2
@ ChrisA. Nun, Sie können dies explizit auf allen Compilern steuern, die zählen (z. B. über -ffast-mathGCC).
Konrad Rudolph
6
@Konrad Rudolph danke für den Hinweis, dass dies eine mögliche Optimierung mit ist -ffast-math. Was ich aus dieser Diskussion und diesem Link gelernt habe , ist, dass Sie, wenn Sie sich für die numerische Genauigkeit interessieren, die Verwendung wahrscheinlich vermeiden sollten, dies -ffast-mathaber in vielen Anwendungen, in denen Sie möglicherweise CPU-gebunden sind, sich aber nicht für präzise numerische Berechnungen interessieren (z. B. Spielprogrammierung) ) -ffast-mathist vernünftig zu bedienen. Daher möchte ich meinen stark formulierten "verbotenen" Kommentar ändern.
Chris A.
Die Verwendung von Variablen mit doppelter Genauigkeit für sum, c, t, yhilft dabei. Sie müssen auch sum -= cvorher hinzufügen return sum.
G. Cohen
34

Ich habe das extreme Beispiel in der Antwort von Steve Jessop ausprobiert.

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    for (long i = 0; i < billion; ++i)
        sum += small;
    std::cout << std::scientific << std::setprecision(1) << big << " + " << billion << " * " << small << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    sum = 0;
    for (long i = 0; i < billion; ++i)
        sum += small;
    sum += big;
    std::cout  << std::scientific << std::setprecision(1) << billion << " * " << small << " + " << big << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

Ich habe folgendes Ergebnis erhalten:

1.0e+00 + 1000000000 * 1.0e-09 = 2.000000082740371    (difference = 0.000000082740371)
1000000000 * 1.0e-09 + 1.0e+00 = 1.999999992539933    (difference = 0.000000007460067)

Der Fehler in der ersten Zeile ist in der zweiten mehr als zehnmal größer.

Wenn ich das doubles floatim obigen Code in s ändere , erhalte ich:

1.0e+00 + 1000000000 * 1.0e-09 = 1.000000000000000    (difference = 1.000000000000000)
1000000000 * 1.0e-09 + 1.0e+00 = 1.031250000000000    (difference = 0.968750000000000)

Keine der Antworten liegt in der Nähe von 2,0 (aber die zweite ist etwas näher).

Verwendung der Kahan-Summation (mit doubles) wie von Daniel Pryden beschrieben:

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    double c = 0.0;
    for (long i = 0; i < billion; ++i) {
        double y = small - c;
        double t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }

    std::cout << "Kahan sum  = " << std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

Ich bekomme genau 2.0:

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

Und selbst wenn ich das doubles floatim obigen Code in s ändere , erhalte ich:

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

Es scheint, dass Kahan der richtige Weg ist!

Andrew Stein
quelle
Mein "großer" Wert ist gleich 1, nicht 1e9. Ihre zweite Antwort, die in aufsteigender Reihenfolge hinzugefügt wird, ist mathematisch korrekt (1 Milliarde plus eine Milliarde Milliardstel ist 1 Milliarde und 1), obwohl mehr Glück jede allgemeine Solidität der Methode ist :-) Beachten Sie, dass doubledas nicht schlecht leidet Präzisionsverlust beim Addieren einer Milliarde Milliardstel, da es 52 signifikante Bits hat, während IEEE floatnur 24 hat und würde.
Steve Jessop
@Steve, mein Fehler, entschuldige mich. Ich habe den Beispielcode auf Ihre Absicht aktualisiert.
Andrew Stein
4
Kahan hat immer noch eine begrenzte Genauigkeit, aber um einen Killerfall zu konstruieren, benötigen Sie sowohl die Hauptsumme als auch den Fehlerakkumulator c, um Werte zu enthalten, die viel größer als der nächste Summand sind. Dies bedeutet, dass der Summand viel, viel kleiner als die Hauptsumme ist, so dass es sehr viele von ihnen geben muss, um viel zu ergeben. Besonders mit doubleArithmetik.
Steve Jessop
14

Es gibt eine Klasse von Algorithmen, die genau dieses Problem lösen, ohne dass die Daten sortiert oder anderweitig neu angeordnet werden müssen .

Mit anderen Worten kann die Summierung in einem Durchgang über die Daten erfolgen. Dies macht solche Algorithmen auch in Situationen anwendbar, in denen der Datensatz nicht im Voraus bekannt ist, z. B. wenn die Daten in Echtzeit eintreffen und die laufende Summe beibehalten werden muss.

Hier ist die Zusammenfassung eines kürzlich erschienenen Papiers:

Wir präsentieren einen neuartigen Online-Algorithmus zur exakten Summierung eines Stroms von Gleitkommazahlen. Mit "online" meinen wir, dass der Algorithmus jeweils nur eine Eingabe sehen muss und einen Eingabestrom beliebiger Länge solcher Eingaben aufnehmen kann, während nur konstanter Speicher benötigt wird. Mit "genau" meinen wir, dass die Summe des internen Arrays unseres Algorithmus genau gleich der Summe aller Eingaben ist und das zurückgegebene Ergebnis die korrekt gerundete Summe ist. Der Korrektheitsnachweis gilt für alle Eingaben (einschließlich nicht normalisierter Zahlen, aber Modulo-Zwischenüberlauf) und ist unabhängig von der Anzahl der Summanden oder der Bedingungsnummer der Summe. Der Algorithmus benötigt asymptotisch nur 5 FLOPs pro Summand und läuft aufgrund der Parallelität auf Befehlsebene nur etwa zwei- bis dreimal langsamer als die offensichtliche. schnelle, aber dumme "gewöhnliche rekursive Summations" -Schleife, wenn die Anzahl der Summanden größer als 10.000 ist. Nach unserem Kenntnisstand ist es daher das schnellste, genaueste und speichereffizienteste unter bekannten Algorithmen. In der Tat ist es schwierig zu erkennen, wie ein schnellerer Algorithmus oder ein Algorithmus, der deutlich weniger FLOPs erfordert, ohne Hardwareverbesserungen existieren könnte. Ein Antrag für eine große Anzahl von Summanden wird gestellt.

Quelle: Algorithmus 908: Exakte Online-Summierung von Gleitkomma-Streams .

NPE
quelle
1
@Inverse: Es gibt immer noch stationäre Bibliotheken. Alternativ kostet der Online-Kauf des PDFs 5 bis 15 US-Dollar (je nachdem, ob Sie ein ACM-Mitglied sind). Schließlich scheint DeepDyve anzubieten, das Papier für 24 Stunden für 2,99 USD auszuleihen (wenn Sie DeepDyve noch nicht kennen, können Sie es möglicherweise sogar im Rahmen der kostenlosen Testversion kostenlos erhalten): deepdyve.com/lp/acm /…
NPE
2

Aufbauend auf Steves Antwort, die Zahlen zuerst in aufsteigender Reihenfolge zu sortieren, möchte ich zwei weitere Ideen vorstellen:

  1. Entscheiden Sie sich für den Exponentenunterschied zweier Zahlen, über dem Sie möglicherweise entscheiden, dass Sie zu viel Präzision verlieren würden.

  2. Addieren Sie dann die Zahlen der Reihe nach, bis der Exponent des Akkumulators für die nächste Nummer zu groß ist. Stellen Sie den Akkumulator dann in eine temporäre Warteschlange und starten Sie den Akkumulator mit der nächsten Nummer. Fahren Sie fort, bis Sie die ursprüngliche Liste erschöpft haben.

Sie wiederholen den Vorgang mit der temporären Warteschlange (nachdem Sie sie sortiert haben) und mit einem möglicherweise größeren Exponentenunterschied.

Ich denke, das wird ziemlich langsam sein, wenn Sie ständig Exponenten berechnen müssen.

Ich hatte einen schnellen Versuch mit einem Programm und das Ergebnis war 1.99903

Quamrana
quelle
2

Ich denke, Sie können es besser machen, als die Zahlen zu sortieren, bevor Sie sie akkumulieren, denn während des Akkumulationsprozesses wird der Akkumulator immer größer. Wenn Sie eine große Anzahl ähnlicher Zahlen haben, verlieren Sie schnell an Präzision. Folgendes würde ich stattdessen vorschlagen:

while the list has multiple elements
    remove the two smallest elements from the list
    add them and put the result back in
the single element in the list is the result

Natürlich ist dieser Algorithmus mit einer Prioritätswarteschlange anstelle einer Liste am effizientesten. C ++ - Code:

template <typename Queue>
void reduce(Queue& queue)
{
    typedef typename Queue::value_type vt;
    while (queue.size() > 1)
    {
        vt x = queue.top();
        queue.pop();
        vt y = queue.top();
        queue.pop();
        queue.push(x + y);
    }
}

Treiber:

#include <iterator>
#include <queue>

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type
reduce(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type vt;
    std::priority_queue<vt> positive_queue;
    positive_queue.push(0);
    std::priority_queue<vt> negative_queue;
    negative_queue.push(0);
    for (; begin != end; ++begin)
    {
        vt x = *begin;
        if (x < 0)
        {
            negative_queue.push(x);
        }
        else
        {
            positive_queue.push(-x);
        }
    }
    reduce(positive_queue);
    reduce(negative_queue);
    return negative_queue.top() - positive_queue.top();
}

Die Zahlen in der Warteschlange sind negativ, weil sie topdie größte Zahl ergeben, aber wir wollen die kleinste . Ich hätte der Warteschlange mehr Vorlagenargumente zur Verfügung stellen können, aber dieser Ansatz scheint einfacher zu sein.

Fredoverflow
quelle
2

Dies beantwortet Ihre Frage nicht ganz, aber es ist klug, die Summe zweimal auszuführen, einmal im Rundungsmodus "Aufrunden" und einmal mit " ". Vergleichen Sie die beiden Antworten, und Sie wissen / wie / ungenau Ihre Ergebnisse sind und ob Sie daher eine klügere Summierungsstrategie verwenden müssen. Leider machen die meisten Sprachen das Ändern des Gleitkomma-Rundungsmodus nicht so einfach, wie es sein sollte, da die Leute nicht wissen, dass es tatsächlich für alltägliche Berechnungen nützlich ist.

Werfen Sie einen Blick auf die Intervallarithmetik, bei der Sie alle Berechnungen auf diese Weise durchführen und dabei die höchsten und niedrigsten Werte beibehalten. Dies führt zu interessanten Ergebnissen und Optimierungen.

rjmunro
quelle
0

Die einfachste Sorte , die die Genauigkeit verbessert, besteht darin, nach dem aufsteigenden Absolutwert zu sortieren. Auf diese Weise können sich die kleinsten Größenwerte ansammeln oder aufheben, bevor sie mit größeren Größenwerten interagieren, die einen Genauigkeitsverlust auslösen würden.

Das heißt, Sie können es besser machen, indem Sie mehrere nicht überlappende Teilsummen verfolgen. Hier ist ein Artikel, der die Technik beschreibt und einen Genauigkeitsnachweis vorlegt: www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps

Dieser Algorithmus und andere Ansätze zur exakten Gleitkommasummierung werden in einfachem Python unter folgender Adresse implementiert: http://code.activestate.com/recipes/393090/ Mindestens zwei davon können trivial in C ++ konvertiert werden.

Raymond Hettinger
quelle
0

Für IEEE 754-Nummern mit einfacher oder doppelter Genauigkeit oder bekannten Formatnummern besteht eine andere Alternative darin, ein Array von Zahlen (vom Aufrufer übergeben oder in einer Klasse für C ++) zu verwenden, die vom Exponenten indiziert werden. Beim Hinzufügen von Zahlen zum Array werden nur Zahlen mit demselben Exponenten hinzugefügt (bis ein leerer Steckplatz gefunden und die Zahl gespeichert ist). Wenn eine Summe angefordert wird, wird das Array vom kleinsten zum größten summiert, um das Abschneiden zu minimieren. Beispiel mit einfacher Genauigkeit:

/* clear array */
void clearsum(float asum[256])
{
size_t i;
    for(i = 0; i < 256; i++)
        asum[i] = 0.f;
}

/* add a number into array */
void addtosum(float f, float asum[256])
{
size_t i;
    while(1){
        /* i = exponent of f */
        i = ((size_t)((*(unsigned int *)&f)>>23))&0xff;
        if(i == 0xff){          /* max exponent, could be overflow */
            asum[i] += f;
            return;
        }
        if(asum[i] == 0.f){     /* if empty slot store f */
            asum[i] = f;
            return;
        }
        f += asum[i];           /* else add slot to f, clear slot */
        asum[i] = 0.f;          /* and continue until empty slot */
    }
}

/* return sum from array */
float returnsum(float asum[256])
{
float sum = 0.f;
size_t i;
    for(i = 0; i < 256; i++)
        sum += asum[i];
    return sum;
}

Beispiel mit doppelter Genauigkeit:

/* clear array */
void clearsum(double asum[2048])
{
size_t i;
    for(i = 0; i < 2048; i++)
        asum[i] = 0.;
}

/* add a number into array */
void addtosum(double d, double asum[2048])
{
size_t i;
    while(1){
        /* i = exponent of d */
        i = ((size_t)((*(unsigned long long *)&d)>>52))&0x7ff;
        if(i == 0x7ff){         /* max exponent, could be overflow */
            asum[i] += d;
            return;
        }
        if(asum[i] == 0.){      /* if empty slot store d */
            asum[i] = d;
            return;
        }
        d += asum[i];           /* else add slot to d, clear slot */
        asum[i] = 0.;           /* and continue until empty slot */
    }
}

/* return sum from array */
double returnsum(double asum[2048])
{
double sum = 0.;
size_t i;
    for(i = 0; i < 2048; i++)
        sum += asum[i];
    return sum;
}
rcgldr
quelle
Dies klingt etwas nach der Methode von Malcolm 1971 oder eher nach seiner Variante, die den Exponenten von Demmel und Hida verwendet ("Algorithmus 3"). Es gibt einen anderen Algorithmus, der eine Carry-basierte Schleife wie Ihre ausführt, aber ich kann sie im Moment nicht finden.
ZachB
@ZachB - Das Konzept ähnelt der Bottom-Up-Zusammenführungssortierung für verknüpfte Listen , bei der auch ein kleines Array verwendet wird, wobei Array [i] auf eine Liste mit 2 ^ i-Knoten zeigt. Ich weiß nicht, wie weit das zurückreicht. In meinem Fall war es eine Selbstfindung in den 1970er Jahren.
rcgldr
-1

Ihre Schwimmer sollten mit doppelter Genauigkeit hinzugefügt werden. Das gibt Ihnen mehr Präzision als jede andere Technik. Für ein bisschen mehr Präzision und deutlich mehr Geschwindigkeit können Sie beispielsweise vier Summen erstellen und am Ende addieren.

Wenn Sie Zahlen mit doppelter Genauigkeit hinzufügen, verwenden Sie long double für die Summe. Dies wirkt sich jedoch nur positiv auf Implementierungen aus, bei denen long double tatsächlich eine höhere Genauigkeit als double aufweist (normalerweise x86, PowerPC, abhängig von den Compilereinstellungen).

gnasher729
quelle
1
"Das gibt Ihnen mehr Präzision als jede andere Technik." Ist Ihnen klar, dass Ihre Antwort mehr als ein Jahr nach einer früheren späten Antwort kommt, in der beschrieben wurde, wie die exakte Summierung verwendet wird?
Pascal Cuoq
Der Typ "Long Double" ist schrecklich und sollte nicht verwendet werden.
Jeff
-1

In Bezug auf die Sortierung scheint es mir, dass, wenn Sie eine Stornierung erwarten, die Zahlen in absteigender Größenordnung und nicht in aufsteigender Reihenfolge hinzugefügt werden sollten . Zum Beispiel:

((-1 + 1) + 1e-20) ergibt 1e-20

aber

((1e-20 + 1) - 1) ergibt 0

In der ersten Gleichung werden zwei große Zahlen aufgehoben, während in der zweiten der 1e-20-Term verloren geht, wenn er zu 1 addiert wird, da die Genauigkeit nicht ausreicht, um ihn beizubehalten.

Außerdem ist die paarweise Summierung ziemlich anständig, um viele Zahlen zu summieren.

KOAD
quelle