C / C ++ Aufrundung Dezimalzahlen mit einer gewissen Genauigkeit, effizient

Question

Ich versuche, die folgenden zu optimieren. Der Code unten tut dies:

Wenn a = 0,775 und ich brauche Präzision 2 dp dann a => 0,78

Grundsätzlich, wenn die letzte Ziffer 5 ist, rundet nach oben der nächsten Stelle, sonst ist es nicht.

Mein Problem war, dass 0,45 doesnt rund 0,5 mit 1 Dezimalpunkt, als der Wert als ,44999999343 gespeichert .... und setprecision rundet es auf 0,4.

Das ist, warum setprecision gezwungen ist höher setprecision(p+10) zu sein, und dann, wenn es wirklich in einem 5 endet, fügen Sie die kleine Menge, um richtig abzurunden.

Ist das erledigt, vergleicht es mit einer Schnur b und gibt das Ergebnis. Das Problem ist, wird diese Funktion einige Milliarden Mal aufgerufen, um das Programm craw machen. Eine bessere Idee, wie man umschreiben / optimieren diese und welche Funktionen im Code sind so schwer, auf der Maschine?

bool match(double a,string b,int p) { //p = precision no greater than 7dp

    double t[] = {0.2, 0.02, 0.002, 0.0002, 0.00002, 0.000002, 0.0000002, 0.00000002};

    stringstream buff;
    string temp;

    buff << setprecision(p+10) << setiosflags(ios_base::fixed) << a; // 10 decimal precision
    buff >> temp;

    if(temp[temp.size()-10] == '5')  a += t[p]; // help to round upwards

    ostringstream test;
    test << setprecision(p) << setiosflags(ios_base::fixed) << a;
    temp = test.str();

    if(b.compare(temp) == 0) return true;

    return false;
}

Answer 1

I eine ganze Zahl Quadratwurzel Unterprogramm mit nichts schrieb mehr als ein paar Dutzend Zeilen ASM, ohne API-Aufrufe auch immer - und es könnte immer noch nur etwa 50 Millionen SqRoots / Sekunde tun (das war vor etwa fünf Jahren ...) .

Der Punkt, den ich mache, ist, dass, wenn Sie Milliarden von Anrufen fahren für, auch die heutige Technologie ersticken wird.

Aber wenn Sie wirklich wollen, sich anstrengen, um es zu beschleunigen, entfernen Sie so viele API Verwendungen wie nur irgend möglich. Dies kann Sie benötigen API Aufgaben manuell durchzuführen, anstatt dass die Bibliotheken zu tun es für Sie. Insbesondere entfernt jede Art von Strom-Betrieb. Das ist langsamer als Schmutz in diesem Zusammenhang. Sie können wirklich da improvisieren müssen.

Das einzige, was noch zu tun danach so viele Zeilen von C ++, wie Sie mit benutzerdefinierter ASM können zu ersetzen ist - aber Sie werden ein Perfektionist darüber sein müssen. Stellen Sie sicher, dass Sie alle Vorteile von jedem CPU-Zyklus und das Register nehmen - ebenso wie jedes Byte des CPU-Cache und Stapelspeicher.

Sie sollten versuchen ganzzahlige Werte anstelle von Floating-Punkte, da diese weit mehr ASM freundlicher und wesentlich effizienter sind. Sie müßten die Zahl von 10 ^ 7 multiplizieren (oder 10 ^ p, je nachdem, wie Sie sich entscheiden, Ihre Logik zu bilden) dem Dezimalsystem der ganzen Weg über nach rechts zu bewegen. Dann könnten Sie sicher die Gleitkommazahlen in eine Grund ganzen Zahl konvertieren.

Sie werden auf der Computer-Hardware verlassen müssen, den Rest zu tun.

<--Microsoft Specific-->
Ich werde auch hinzufügen, dass C ++ Bezeichner (einschließlich statisch diejenigen, wie Donnie DeBoer erwähnte) ist direkt von ASM Blöcken verschachtelt in C ++ Code. Dies macht inline ASM ein Kinderspiel.
<--End Microsoft Specific-->

Answer 2

Je nachdem, was Sie wollen die Zahlen für, können Sie Festpunktzahlen statt Gleitkomma verwenden. Eine schnelle Suche taucht dieser rel="nofollow.

Answer 3

Ich denke, man kann nur 0,005 für Präzision in den Hundertsteln, 0,0005 für Tausende usw. snprintf das Ergebnis mit so etwas wie „% 1.2f“ (Hundertstel, Tausendstel 1.3f, etc.) und die Saiten vergleichen. Sie sollten diese Logik tabellen ize oder parametrierbar sein.

Answer 4

Sie könnten einige wichtige Zyklen in geposteten Code speichern, indem Sie einfach zu machen, dass eine doppelte t [] statisch, so dass es nicht ist es immer und immer wieder zugewiesen wird.

Answer 5

Versuchen Sie stattdessen:

#include <cmath>

double setprecision(double x, int prec) {
    return 
        ceil( x * pow(10,(double)prec) - .4999999999999)
        / pow(10,(double)prec);
}

Es ist wahrscheinlich schneller. Vielleicht versuchen Sie es auch inlining, aber das könnte weh tun, wenn es hilft nicht.

Beispiel dafür, wie es funktioniert:

2.345* 100 (10 to the 2nd power) = 234.5
234.5 - .4999999999999 = 234.0000000000001
ceil( 234.0000000000001 ) = 235
235 / 100 (10 to the 2nd power) = 2.35

Die ,4999999999999 wurde wegen der Präzision für einen C ++ gewählte Doppel auf einem 32-Bit-System. Wenn Sie auf einem 64-Bit-Plattform sind, werden Sie wahrscheinlich mehr Neunen benötigen. Wenn Sie die Neunen weiter auf einem 32-Bit-System erhöhen überläuft es und rundet statt nach oben, d. e. 234,00000000000001 im Doppel bis 234 in (meine) 32-Bit-Umgebung abgeschnitten wird.

Answer 6

Mit Floating-Point (eine ungenaue Darstellung) bedeutet, dass Sie einige Informationen über die tatsächliche Zahl verloren haben. Sie können nicht einfach „reparieren“ den im doppelten gespeicherten Wert durch einen Fudge Wert hinzufügen. Das könnte beheben bestimmten Fällen (wie .45), aber es wird den anderen Fällen brechen. Sie werden am Aufrundung Zahlen enden, die nach unten abgerundet werden sollten.

Hier ist ein verwandter Artikel: http://www.theregister.co.uk/2006/08/12 / floating_point_approximation /

Answer 7

Ich nehme an erraten, was meinen Sie wirklich zu tun. Ich vermute, dass Sie versuchen, um zu sehen, ob ein String eine Dezimaldarstellung eines doppelten bis zu einem gewissen Genauigkeit enthält. Vielleicht ist es ein arithmetisches Quiz-Programm und Sie versuchen, zu sehen, ob die Antwort des Benutzers wird „nahe genug“, um die richtige Antwort. Wenn das der Fall ist, dann kann es einfacher sein, um die Zeichenfolge zu einem Doppel zu konvertieren und sehen, ob der absolute Wert der Differenz zwischen den beiden Doppel innerhalb eines gewissen Toleranz ist.

double string_to_double(const std::string &s)
{
    std::stringstream buffer(s);
    double d = 0.0;
    buffer >> d;
    return d;
}

bool match(const std::string &guess, double answer, int precision)
{
    const static double thresh[] = { 0.5, 0.05, 0.005, 0.0005, /* etc. */ };
    const double g = string_to_double(guess);
    const double delta = g - answer;
    return -thresh[precision] < delta && delta <= thresh[precision];
}

Eine andere Möglichkeit ist zunächst die Antwort abzurunden (während es noch numerisch ist), bevor es in einen String umgewandelt wird.

bool match2(const std::string &guess, double answer, int precision)
{
    const static double thresh[] = {0.5, 0.05, 0.005, 0.0005, /* etc. */ };
    const double rounded = answer + thresh[precision];
    std::stringstream buffer;
    buffer << std::setprecision(precision) << rounded;
    return guess == buffer.str();
}

Beide Lösungen sollten Ihre Beispielcode schneller sein als, aber ich bin nicht sicher, ob sie das tun, was Sie wirklich wollen.

Answer 8

Soweit ich sehe, dass Sie überprüfen, ob ein auf p Punkten gerundet ist gleich b.

Insted von a String zu ändern, machen andere Art und Weise und ändert Zeichenfolge zu verdoppeln - (nur Multiplikationen und addion oder nur additoins Tischchen mit) - dann subtrahieren sowohl Zahlen als auch überprüfen, ob Substraktion in richtigem Bereich liegt (wenn p == 1 => abs (p-a) <0,05)

Answer 9

Alte Zeit Entwickler Trick aus den dunklen Zeiten des Pfunds, Schilling und Pence in der alten Heimat.

Der Trick war, um den Wert als ganze Zahl fo Halb pennys zu speichern. (Oder was auch immer Ihre kleinste Einheit ist). Dann werden alle Ihre nachfolgenden arithmatic ist einfach integer arithimatic und etc Rundung wird für sich selbst sorgen.

Also in Ihrem Fall, dass Sie speichern Ihre Daten in Einheiten von 200ths von was auch immer Sie zählen, tun einfache Integer-Berechnungen auf diesen Werten und dividieren durch 200 in einen Schwimmer varaible, wenn Sie das Ergebnis angezeigt werden soll.

Ich glaube, Boost-in diesen Tagen eine „BigDecimal“ Bibliothek tut, aber, Ihre Anforderung für die Laufzeitgeschwindigkeit wahrscheinlich diese sonst ausgezeichnete Lösung ausschließen würde.

Answer 10

Sieht aus wie das, was Sie versuchen, nicht eine echte Rundung zu tun ist. 0,45 ist in der Tat 0,45 in binärer Schreibweise und ,44999999343 ist nicht dasselbe.

Mai werden Sie mehrere Runden tun müssen, -. Ersten 3 Dezimalstellen sagen, dann zwei, dann ein

Die Frage ist, was wollen Sie erreichen? Sollte Ihr Einstimmungskriterium sein

abs(a-b) < 10 ** -p

statt?