Manuelles Parsen einer Gleitkommazahl aus einer Zeichenkette

Question

Natürlich haben die meisten Sprachen dafür Bibliotheksfunktionen, aber nehmen wir an, ich möchte das selbst machen.

Angenommen, der Float wird wie in einem C- oder Java-Programm angegeben (mit Ausnahme des Suffixes 'f' oder 'd'), zum Beispiel " 4.2e1 ", " .42e2 " oder einfach " 42 ". Im Allgemeinen haben wir den "ganzzahligen Teil" vor dem Komma, den "gebrochenen Teil" nach dem Komma und den "Exponenten". Alle drei sind ganze Zahlen.

Es ist einfach, die einzelnen Ziffern zu finden und zu verarbeiten, aber wie setzt man sie zu einem Wert des Typs float o double ohne an Präzision zu verlieren?

Ich denke daran, den ganzzahligen Teil mit 10^ zu multiplizieren. n , donde n die Anzahl der Ziffern des gebrochenen Teils ist, dann wird der gebrochene Teil zum ganzzahligen Teil addiert und subtrahiert n aus dem Exponenten. Dies macht effektiv 4.2e1 in 42e0 zum Beispiel. Dann könnte ich die pow Funktion zur Berechnung von 10^ Exponent und multiplizieren das Ergebnis mit dem neuen ganzzahligen Teil. Die Frage ist, ob diese Methode durchgehend eine maximale Genauigkeit garantiert.

Haben Sie dazu eine Meinung?

Answer 1

Alle anderen Antworten haben übersehen, wie hart ist es, dies richtig zu tun. Man kann einen ersten Ansatz machen, der bis zu einem gewissen Grad genau ist, aber solange man nicht die IEEE-Rundungsmodi (u.a.) berücksichtigt, wird man nie die rechts Antwort. Ich habe schon früher naive Implementierungen mit einer ziemlich großen Fehlerquote geschrieben.

Wenn Sie keine Angst vor Mathe haben, empfehle ich Ihnen, den folgenden Artikel von David Goldberg zu lesen, Was jeder Informatiker über Fließkommaarithmetik wissen sollte . Sie werden ein besseres Verständnis dafür bekommen, was unter der Haube vor sich geht und warum die Teile so angeordnet sind.

Mein bester Rat ist, mit einer funktionierenden atoi-Implementierung zu beginnen und von dort aus weiterzugehen. Sie werden schnell feststellen, dass Sie Dinge vermissen, aber ein paar Blicke auf strtod und Sie werden auf dem richtigen Weg sein (der ein langer, langer Weg ist). Letztendlich werden Sie loben Hier eine Gottheit einfügen dass es Standardbibliotheken gibt.

/* use this to start your atof implementation */

/* atoi - christopher.watford@gmail.com */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
  unsigned long ival = 0, c, n = 1, i = 0, oval;
  for( ; c = value[i]; ++i) /* chomp leading spaces */
    if(!isspace(c)) break;
  if(c == '-' || c == '+') { /* chomp sign */
    n = (c != '-' ? n : -1);
    i++;
  }
  while(c = value[i++]) { /* parse number */
    if(!isdigit(c)) return 0;
    ival = (ival * 10) + (c - '0'); /* mult/accum */
    if((n > 0 && ival > LONG_MAX)
    || (n < 0 && ival > (LONG_MAX + 1UL))) {
      /* report overflow/underflow */
      errno = ERANGE;
      return (n > 0 ? LONG_MAX : LONG_MIN);
    }
  }
  return (n>0 ? (long)ival : -(long)ival);
}

Answer 2

Der "Standard"-Algorithmus für die Umwandlung einer Dezimalzahl in die beste Gleitkomma-Näherung ist William Clinger's Wie man Fließkommazahlen genau liest , herunterladbar von aquí . Beachten Sie, dass für eine korrekte Durchführung dieses Verfahrens zumindest in einem bestimmten Prozentsatz der Fälle ganze Zahlen mit mehrfacher Genauigkeit erforderlich sind, um Eckfälle zu behandeln.

Algorithmen für den umgekehrten Weg, d.h. für das Drucken der besten Dezimalzahl aus einer Fließkommazahl, finden sich in Burger und Dybvig's Schnelles und genaues Drucken von Fließkommazahlen , herunterladbar aquí . Dies erfordert auch die Arithmetik ganzer Zahlen mit Mehrfachpräzision

Siehe auch David M. Gay's Korrekt gerundete Binär-Dezimal- und Dezimal-Binär-Umwandlungen für Algorithmen in beide Richtungen.

Answer 3

Ich würde die Fließkommazahl direkt aus ihrer binären Darstellung zusammensetzen.

Lesen Sie die Zahl ein Zeichen nach dem anderen ein und suchen Sie zunächst alle Ziffern. Machen Sie das in ganzzahliger Arithmetik. Achten Sie auch auf den Dezimalpunkt und den Exponenten. Das wird später noch wichtig sein.

Jetzt können Sie Ihre Fließkommazahl zusammensetzen. Als Erstes müssen Sie die Ganzzahldarstellung der Ziffern nach dem ersten gesetzten Ein-Bit (höchstes bis niedrigstes) durchsuchen.

Die Bits, die unmittelbar auf das erste Ein-Bit folgen, sind Ihre Mantisse.

Auch die Ermittlung des Exponenten ist nicht schwer. Sie kennen die erste Ein-Bit-Position, die Position des Dezimalpunkts und den optionalen Exponenten aus der wissenschaftlichen Notation. Kombinieren Sie diese und fügen Sie den Fließkomma-Exponenten hinzu (ich glaube, es ist 127, aber schauen Sie bitte in einer Referenz nach).

Dieser Exponent sollte irgendwo im Bereich von 0 bis 255 liegen. Wenn er größer oder kleiner ist, handelt es sich um eine positive oder negative unendliche Zahl (Sonderfall).

Speichern Sie den Exponenten in den Bits 24 bis 30 Ihres Floats.

Das wichtigste Bit ist einfach das Vorzeichen. Eins bedeutet negativ, Null bedeutet positiv.

Versuchen Sie einmal, eine Fließkommazahl zu zerlegen, und sehen Sie sich den Exponenten und die Mantisse an, dann werden Sie sehen, wie einfach es wirklich ist.

Btw - die Arithmetik in Fließkomma selbst ist eine schlechte Idee, weil Sie immer Ihre Mantisse zwingen, auf 23 signifikante Bits abgeschnitten werden. Auf diese Weise erhalten Sie keine exakte Darstellung.

Answer 4

Sie könnten die Dezimalstelle beim Parsen ignorieren (mit Ausnahme ihrer Position). Angenommen, die Eingabe war: 156.7834e10... Dies könnte leicht in die Ganzzahl 1567834, gefolgt von e10, zerlegt werden, die Sie dann in e6 ändern würden, da die Dezimalstelle 4 Stellen vom Ende des "Zahlen"-Teils des Floats entfernt ist.

Präzision ist ein Thema. Sie müssen die IEEE-Spezifikation der Sprache, die Sie verwenden, überprüfen. Wenn die Anzahl der Bits in der Mantisse (oder im Bruchteil) größer ist als die Anzahl der Bits in Ihrem Integer-Typ, dann verlieren Sie möglicherweise an Präzision, wenn jemand eine Zahl wie z. B.:

5123.123123e0 - konvertiert in unserer Methode zu 5123123123, was NICHT in einen Integer passt, aber die Bits für 5.123123123 können in die Mantisse der Float-Spezifikation passen.

Natürlich können Sie auch eine Methode verwenden, die jede Stelle vor dem Komma nimmt, die aktuelle Summe (in einer Fließkommazahl) mit 10 multipliziert und dann die neue Stelle addiert. Bei Nachkommastellen wird die Ziffer mit einer wachsenden Potenz von 10 multipliziert, bevor sie zur aktuellen Summe addiert wird. Bei dieser Methode stellt sich jedoch die Frage, warum Sie das überhaupt tun, da sie die Verwendung der Fließkomma-Primitive erfordert, ohne die leicht verfügbaren Parsing-Bibliotheken zu verwenden.

Wie auch immer, viel Glück!

Answer 5

Ja können Sie die Konstruktion in Gleitkommaoperationen zerlegen so lange wie diese Vorgänge sind EXAKT und Sie können sich eine einzige endgültige ungenaue Betrieb.

Leider sind Gleitkommaoperationen bald ungenau werden, wenn Sie die Genauigkeit der Mantisse überschreiten, werden die Ergebnisse gerundet. Sobald ein Rundungsfehler auftritt, wird er bei weiteren Operationen kumuliert...
Also, ganz allgemein, NO Sie können einen solchen naiven Algorithmus nicht verwenden, um beliebige Dezimalzahlen zu konvertieren, da dies zu einer falsch gerundeten Zahl führen kann, die um mehrere ulp von der korrekten Zahl abweicht, wie andere Ihnen bereits gesagt haben.

ABER WIR WERDEN SEHEN, WIE WEIT WIR GEHEN KÖNNEN:

Wenn Sie den Wagen sorgfältig rekonstruieren, sieht das so aus:

if(biasedExponent >= 0)
    return integerMantissa * (10^biasedExponent);
else
    return integerMantissa / (10^(-biasedExponent));

es besteht die Gefahr, die Genauigkeit zu überschreiten, sowohl bei der Kumulierung der GanzzahlMantissa, wenn sie viele Stellen hat, als auch bei der Erhöhung von 10 hoch biasedExponent...

Wenn die ersten beiden Operationen exakt sind, kann man sich glücklicherweise eine letzte ungenaue Operation * oder / leisten, denn dank der IEEE-Eigenschaften wird das Ergebnis korrekt gerundet.

Wenden wir dies auf einfache Präzisions-Gleitkommazahlen an, die eine Genauigkeit von 24 Bit haben.

10^8 > 2^24 > 10^7

Da das Vielfache von 2 nur den Exponenten erhöht und die Mantisse unverändert lässt, müssen wir uns bei der Potenzierung von 10 nur mit Potenzen von 5 befassen:

5^11 > 2^24 > 5^10

Sie können sich jedoch eine Genauigkeit von 7 Ziffern in der integerMantissa und einen verzerrten Exponenten zwischen -10 und 10 leisten.

In doppelter Genauigkeit, 53 Bits,

10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22

Sie können sich also 15 Dezimalstellen und einen verzerrten Exponenten zwischen -22 und 22 leisten.

Es liegt an Ihnen zu sehen, ob Ihre Zahlen immer in den richtigen Bereich fallen... (Wenn Sie wirklich trickreich sind, können Sie Mantisse und Exponent durch Einfügen/Entfernen von Nullen am Ende ausgleichen).

Andernfalls müssen Sie eine erweiterte Präzision verwenden.
Wenn Ihre Sprache Integer mit beliebiger Genauigkeit anbietet, dann ist es ein bisschen knifflig, es richtig zu machen, aber nicht so schwierig, ich habe das in Smalltalk gemacht und darüber gebloggt unter http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html y http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

Beachten Sie, dass dies einfache und naive Implementierungen sind. Glücklicherweise ist die libc besser optimiert.