[Russ Cox] Revolution bei der Floating-Point-Konvertierung: einfacher, schneller und schlanker

Zusammenfassung:

• Der von Russ Cox vorgeschlagene neue Algorithmus zur Floating-Point-Konvertierung ist einfacher und zugleich leistungsfähiger als bestehende komplexe Algorithmen wie Ryū oder Dragonbox.
• Mit dem zentralen Primitive „Unrounded Scaling“ beschleunigt er die Konvertierung zwischen Binär- und Dezimaldarstellung auf das Niveau einer einzelnen 64-Bit-Multiplikation.
• Die Implementierung wird voraussichtlich in Go 1.27 (geplant für August 2026) enthalten sein und unterstützt sowohl Ausgaben mit fester Präzision als auch Parsing und Ausgabe mit minimaler Stellenzahl.
• Leistungsverbesserungen gegenüber bestehenden Implementierungen
• Ausgabe(Printing)-Performance: etwa 10–30 % schneller
• Parsing-Performance: etwa 5–15 % schneller

Detaillierte Zusammenfassung:

1. Hintergrund: die chronische Komplexität der Floating-Point-Konvertierung

Die Umwandlung von binären Floating-Point-Zahlen im Computer in für Menschen lesbare Dezimalzahlen und umgekehrt ist seit Jahrzehnten ein Feld, in dem zahlreiche Algorithmen wie Dragon4, Grisu3, Ryū und Dragonbox miteinander konkurrieren. Russ Cox sagte früher sinngemäß: „Die Konvertierung ist einfach, das Problem ist die Geschwindigkeit“, und zeigt in diesem Beitrag nun, dass „auch schnelle Konvertierungsalgorithmen einfach sein können“.

2. Zentrale Idee: Unrounded Numbers (⟨x⟩)

Die Grundlage dieses Algorithmus ist der Typ unrounded. Er speichert nicht nur den ganzzahligen Anteil einer Zahl, sondern zusätzlich 2 Bit an Informationen, die für das Runden nötig sind: das ½-Bit und den OR-Wert der darunterliegenden Bits, also das „sticky bit“.

• Struktur: ⟨x⟩ = ⌊4x⌋ | (4x ≠ ⌊4x⌋)
• Vorteil: Wenn dieses Format beibehalten wird, lassen sich die floor-Funktion, die ceil-Funktion sowie die für Floating-Point besonders wichtige Operation „Round-to-nearest, ties-to-even“ sehr kostengünstig ausführen.

3. Schnelles Unrounded Scaling

Die wichtigste Funktion ist uscale(x, e, p). Sie berechnet das unrounded-Ergebnis von .
Bestehende Algorithmen erfordern sehr große Ganzzahloperationen, doch dieser Ansatz verarbeitet das mit folgendem Prinzip innerhalb von 64-Bit-Operationen.

// Beispiel einer konzeptionellen Implementierung (die tatsächlich optimierte Version ist komplexer)  
func uscale(x uint64, e, p int) unrounded {  
    // 10^p wird als 2^k * exakter Bruch angenähert und berechnet  
    // In den meisten Fällen reduziert sich das auf eine einzelne 64-Bit-Multiplikation (mul64) und Shift-Operationen  
}  
  

4. Wichtigste Ergebnisse und Performance

• Einfachheit: Der Implementierungscode ist sehr kurz, dadurch leicht wartbar und logisch beweisbar.
• Performance: Benchmarks zeigen, dass er schneller ist als die derzeit als am schnellsten geltenden Algorithmen Dragonbox (Ausgabe) und Eisel-Lemire (Parsing).
• Vielseitigkeit: Er lässt sich sowohl für Festkomma-Ausgabe mit fester Breite als auch für die kürzeste Ausgabe anwenden, die den Originalwert vollständig wiederherstellt.

5. Bedeutung für Entwickler

Der Algorithmus soll in die Standardbibliothek der Programmiersprache Go integriert werden. Entwickler erhalten dadurch bei internen Dezimalkonvertierungen (z. B. fmt.Printf("%f", f) oder strconv.ParseFloat) exakte Ergebnisse bei geringerem CPU-Einsatz. Außerdem liefert das Konzept unrounded Impulse für präzise numerische Kontrolle auch ohne komplexe numerische Analysebibliotheken.