[Russ Cox] La révolution de la conversion en virgule flottante : plus facile, plus rapide et plus simple

Résumé :

• Le nouvel algorithme de conversion en virgule flottante proposé par Russ Cox est plus simple tout en offrant de meilleures performances que les algorithmes complexes existants (Ryū, Dragonbox, etc.).
• Grâce à une primitive clé appelée « Unrounded Scaling », il accélère la conversion entre binaire et décimal jusqu’au niveau d’une seule multiplication 64 bits.
• Cette implémentation devrait être intégrée à Go 1.27 (prévu pour août 2026) et prend en charge à la fois la sortie à précision fixe ainsi que le parsing et l’affichage en largeur minimale.
• Gains de performance par rapport aux implémentations existantes
• Performances d’affichage (Printing) : amélioration d’environ 10 à 30 %
• Performances de parsing (Parsing) : amélioration d’environ 5 à 15 %

Résumé détaillé :

1. Contexte : la complexité chronique de la conversion en virgule flottante

La conversion des nombres en virgule flottante binaires (floating-point) des ordinateurs en décimaux lisibles par l’humain, ou l’opération inverse, est depuis des décennies un domaine où de nombreux algorithmes (Dragon4, Grisu3, Ryū, Dragonbox, etc.) se disputent la meilleure approche. Russ Cox avait autrefois déclaré que « la conversion est facile, mais la vitesse est le problème » ; dans ce billet, il démontre au contraire que « les algorithmes de conversion rapides peuvent aussi être simples ».

2. Idée centrale : les nombres non arrondis (⟨x⟩)

La base de cet algorithme est le type unrounded. Il conserve non seulement la partie entière d’un nombre, mais aussi deux bits d’information supplémentaires nécessaires à l’arrondi : le bit ½ et la valeur OR de tous les bits inférieurs (« sticky bit »).

• Structure : ⟨x⟩ = ⌊4x⌋ | (4x ≠ ⌊4x⌋)
• Avantage : en conservant cette forme, on peut effectuer à très faible coût les opérations floor, ceil, ainsi que l’opération la plus importante en virgule flottante, « round-to-nearest, ties-to-even ».

3. Mise à l’échelle rapide non arrondie (Fast Unrounded Scaling)

La fonction la plus importante est uscale(x, e, p). Elle calcule le résultat unrounded.
Là où les algorithmes existants nécessitaient de très grands calculs sur entiers, cette approche reste dans le cadre d’opérations 64 bits grâce au principe suivant.

// Exemple d’implémentation conceptuelle (la version réellement optimisée est plus complexe)  
func uscale(x uint64, e, p int) unrounded {  
    // calcule 10^p en l’approximant par 2^k * une fraction exacte  
    // dans la plupart des cas, cela se ramène à une seule multiplication 64 bits (mul64) et des décalages  
}  
  

4. Principaux résultats et performances

• Simplicité : le code d’implémentation est très court, ce qui facilite la maintenance et permet une démonstration logique.
• Performances : selon les benchmarks, l’algorithme est encore plus rapide que Dragonbox (affichage) et Eisel-Lemire (parsing), aujourd’hui considérés comme les plus rapides dans leur catégorie.
• Polyvalence : il s’applique aussi bien à l’affichage à largeur fixe (Fixed-width printing) qu’à l’affichage en largeur minimale garantissant une reconstruction parfaite de la valeur d’origine (Shortest-width printing).

5. Ce que cela signifie pour les développeurs

Cet algorithme devrait être intégré à la bibliothèque standard du langage Go. Les développeurs obtiendront donc des résultats exacts tout en consommant moins de ressources CPU lors des conversions décimales internes (par exemple fmt.Printf("%f", f) ou strconv.ParseFloat). Il offre aussi une source d’inspiration pour un contrôle numérique précis via le concept unrounded, sans recourir à des bibliothèques d’analyse numérique complexes.```