summieren Array von Doppel mit großem Wert span: richtigen Algorithmus

Question

Ich habe einen Algorithmus, wo ich (viel Zeit) doppelte Zahlen in der E-40 bis e + 40 summieren müssen.

Array Beispiel (zufällig aus realen Anwendung dumped):

-2.06991e-05 
7.58132e-06 
-3.91367e-06 
7.38921e-07 
-5.33143e-09 
-4.13195e-11 
4.01724e-14 
6.03221e-17 
-4.4202e-20 
6.58873 
-1.22257 
-0.0606178 
0.00036508 
2.67599e-07 
0 
-627.061 
-59.048 
5.92985 
0.0885884 
0.000276455 
-2.02579e-07 

Es versteht sich von selbst, die ich bin mir bewusst, der Effekt Rundung wird dies dazu führen, ich versuche, es unter Kontrolle zu halten: das Endergebnis sollte keine fehlenden Informationen im Bruchteil des doppelten oder, wenn nicht vermeidbaren Ergebnisses sollten mindestens n-stellig genau sein (mit n definiert). Das Endergebnis benötigt etwa 5 Ziffern plus Exponent.

Nach einem paar anständigen Denken, landete ich mit folgendem Algorithmus auf:

• sortiert das Array, so dass der größte Absolutwert an erster Stelle steht, die am nächsten zu Null reicht.
• alles in einer Schleife

Die Idee ist, in diesem Fall hinzufügen, dass jede Stornierung von großen Werten (Negative und positive) wird letztere kleinere Werte nicht beeinflussen. Kurz In:

• (10e40 - 10e40) + 1 = 1: Ergebnis wie erwartet
• (1 + 10e40) - 10e40 = 0: nicht gut

Ich landete mit std :: multiset (Benchmark auf meinem PC gab 20% höhere Geschwindigkeit mit langen Doppel im Vergleich zu normalen Doppel - ich bin in Ordnung Doppelauflösung) mit einer benutzerdefinierten Sortierfunktion mit Std: Fabs.

Es ist immer noch ziemlich langsam (es dauert 5 Sekunden, um das Ganze zu tun) und ich habe immer noch das Gefühl von "Sie haben etwas in Ihrem Algo verpasst". Jede Empfehlung:

1. für die Geschwindigkeitsoptimierung. Gibt es eine bessere Möglichkeit, die Zwischenprodukte zu sortieren? Das Sortieren einer Menge von 40 Zwischenergebnissen (typischerweise) dauert etwa 70% der gesamten Ausführungszeit.
2. für verpasste Probleme. Gibt es eine Chance, weiterhin kritische Daten zu verlieren (eine, die im Bruchteil des Endergebnisses liegen sollte)? (Z (jw) elektrische Impedanz)

---

auf ein größeres Bild, ich Polynom Klassen von rein imaginären variablen reellen Koeffizienten bin der Umsetzung. Z ist ein großes Polynom, das ein benutzerdefiniertes System darstellt, wobei der Koeffizientenexponent sehr weit reicht.
Das "große" kommt von Hinzufügen von Sachen wie Zc1 = 1/jC1w zu Zc2 = 1/jC2w:
Zc1 + Zc2 = (C1C2 (jw)^2 + 0 (jw))/(C1 + C2) (jw)

In diesem Fall, mit C1 und C2 in Nanofarad (10e-9), ist C1C2 bereits in 10e-18 (und es begann nur ...

)

meine Sortierfunktion eine Manhattan-Distanz von komplexen Variablen verwenden (weil, Minen entweder rein reell oder rein imaginär) sind:

struct manhattan_complex_distance 
{ 
     bool operator() (std::complex<long double> a, std::complex<long double> b) 
     { 
      return std::fabs(std::real(a) + std::imag(a)) > std::fabs(std::real(b) + std::imag(b)); 
     } 
}; 

und meinen Multi Satz in Aktion:

std:complex<long double> get_value(std::vector<std::complex<long double>>& frequency_vector) 
{ 
    //frequency_vector is precalculated once for all to have at index n the value (jw)^n. 
    std::multiset<std::complex<long double>, manhattan_distance> temp_list; 
    for (int i=0; i<m_coeficients.size(); ++i) 
    { 
     // element of :  ℝ   *   ℂ 
     temp_list.insert(m_coeficients[i] * frequency_vector[i]); 
    } 
    std::complex<long double> ret=0; 
    for (auto i:temp_list) 
    { 
     // it is VERY important to start adding the big values before adding the small ones. 
     // in informatics, 10^60 - 10^60 + 1 = 1; while 1 + 10^60 - 10^60 = 0. Of course you'd expected to get 1, not 0. 
     ret += i; 
    } 
    return ret; 
} 

The Projekt, das ich habe, ist C++ 11 aktiviert (hauptsächlich für die Verbesserung der Mathematik lib und komplexe Anzahl Werkzeuge)

PS: Ich refaktoriert den Code zu machen ist einfach zu lesen, in Wirklichkeit alle Komplexe und lange Doppelnamen sind Vorlage: Ich kann das Polynom Art in kürzester Zeit ändern oder die Klasse für reguläres Polynom r verwenden

Answer 1

Als GuyGreer vorgeschlagen, können Sie Kahan summation verwenden:

double sum = 0.0; 
double c = 0.0; 
for (double value : values) { 
    double y = value - c; 
    double t = sum + y; 
    c = (t - sum) - y; 
    sum = t; 
} 

EDIT: Sie kann auch in Betracht ziehen sollten Verwenden Horner's method, um das Polynom auszuwerten.

double value = coeffs[degree]; 
for (auto i = degree; i-- > 0;) { 
    value *= x; 
    value += coeffs[i]; 
} 

Answer 2

Das Sortieren der Daten ist auf dem richtigen Weg. Aber Sie sollten auf jeden Fall von der kleinsten Größe zum größten, nicht vom größten zum kleinsten summieren. Wenn Sie vom kleinsten zum größten Wert bis zum kleinsten Wert kommen, kann das Ausrichten des nächsten Werts mit der aktuellen Summe dazu führen, dass die meisten oder alle Bits des nächsten Werts "vom Ende fallen". Summiert man stattdessen von der kleinsten zur größten, erhalten die kleinsten Werte eine Chance, eine anständige Größe zu sammeln, für die mehr Bits in die größte hineinkommen. In Kombination mit der Kahan-Summe sollte das eine ziemlich genaue Summe ergeben.

Answer 3

Erstens: Lassen Sie Ihre Mathematik Fehler verfolgen. Ersetzen Sie Ihre Doubles durch fehlerbewusste Typen, und wenn Sie zwei Doubles addieren oder multiplizieren, berechnet sie auch den Maximumsfehler.

Dies ist die einzige Möglichkeit, mit der Sie garantieren können, dass Ihr Code genaue Ergebnisse liefert und gleichzeitig relativ schnell ist.

Zweitens, verwenden Sie keine multiset. Die assoziativen Container sind nicht zum Sortieren vorgesehen, sie sind für , die eine sortierte Sammlung verwalten, während sie in der Lage sind, schrittweise Elemente effizient hinzuzufügen oder zu entfernen.

Die Fähigkeit, Elemente inkrementell hinzuzufügen/zu entfernen, bedeutet, dass es knotenbasiert ist und knotenbasiert bedeutet, dass es im Allgemeinen langsam ist.

Wenn Sie einfach eine sortierte Sammlung möchten, beginnen Sie mit einem vector dann std::sort es.

Als nächstes, um Fehler zu minimieren, behalten Sie eine Liste der positiven und negativen Elemente. Beginne mit Null als deine Summe. Wählen Sie nun das kleinste der positiven oder negativen Elemente, so dass die Summe Ihrer Summe und dieses Elements am nächsten bei Null liegt.

Tun Sie dies mit Elementen, die ihre Fehlergrenzen berechnen.

Am Ende, bestimmen Sie, ob Sie 5 Ziffern der Genauigkeit haben oder nicht.

Diese fehlerpropagierenden Doppelungen sollten idealerweise so früh wie möglich im Algorithmus verwendet werden.