Les membres en base 2^51 surpassent les chaînes d'additions avec retenue en différant les retenues

Additionner des nombres plus larges que 64 bits devrait être simple : découper chaque entier de 256 bits en quatre morceaux de 64 bits, les additionner, et propager tout débordement vers le haut. Le hic, c'est le débordement — sans retenues le résultat est faux, donc la version correcte enchaîne l'instruction d'addition avec retenue (adc) de x86 depuis le membre de poids faible vers le haut. Sur les CPU out-of-order modernes, cette chaîne est plus lente que le code parallèle incorrect : adc est une instruction plus lourde, et chacune dépend du drapeau de retenue produit par la précédente. Un CPU Haswell peut émettre jusqu'à quatre additions indépendantes par cycle, mais les adc enchaînées s'exécutent en série.

La correction contre-intuitive, connue dans la littérature cryptographique sous le nom de représentation en base 2^51, consiste à utiliser plus de membres, chacun plus petit qu'un registre. Là où l'approche évidente découpe 256 bits en quatre chiffres en base 2^64, cette approche le découpe en cinq chiffres en base 2^51 ; chaque membre de 64 bits contient toujours son chiffre, mais les 12 à 13 bits supérieurs restent vides comme espace où les retenues peuvent s'accumuler. Grâce à cette marge, additionner des valeurs normalisées ne produit aucune retenue tant que les bits libres ne sont pas remplis — jusqu'à environ 2^13 additions — si bien que chaque addition est indépendante et que le processeur les ordonnance en parallèle.

Les retenues ne sont pas éliminées, seulement différées. Quand la marge est épuisée, une passe de normalisation décale le débordement de chaque membre vers le membre supérieur et remet à zéro la marge, et la soustraction fonctionne de la même manière en traitant les membres comme signés, au prix d'un bit de marge. Les benchmarks rapides de l'auteur sur une machine Haswell ont montré que l'addition en base 2^51 était déjà plus rapide que l'addition en base 2^64 dès trois additions, coût de conversion vers et depuis la représentation compris, l'économie augmentant à mesure que les additions s'accumulent.

L'article construit d'abord l'intuition sur le papier : en base 10, élargir la plage de chaque chiffre pour qu'il puisse compter au-delà de 9 permet d'additionner plusieurs nombres normalisés avant qu'un chiffre ne déborde, et une passe de normalisation reconvertit le résultat. Transposé aux registres binaires, le même principe explique pourquoi la représentation est standard en cryptographie — et pourquoi, contre-intuitivement, répartir un nombre sur plus de registres et émettre plus d'instructions rend l'arithmétique plus rapide. Publié pour la première fois en 2017, l'article a été posté sur Hacker News en mai 2020 et a recueilli 518 points et 83 commentaires.

Réduire les membres à 51 bits pour que les bits libres absorbent les retenues : les additions restent indépendantes et parallèles, et la normalisation n'a lieu qu'une fois à la fin

Les retenues sont la dépendance : les instructions adc enchaînées se sérialisent parce que chacune attend le drapeau de retenue de la précédente, tandis que des additions simples indépendantes peuvent être émises à quatre par cycle sur Haswell.

La marge vide est l'astuce : les chiffres de 51 bits dans des registres de 64 bits laissent 12 à 13 bits libres, si bien qu'environ 2^13 additions se produisent avant qu'une retenue doive se propager.

Une passe différée vaut mieux que de nombreuses passes immédiates : la normalisation à la fin est un balayage fixe au lieu d'une dépendance de retenue à chaque opération.

Le membre supplémentaire se rentabilise : cinq additions simples battent quatre chaînes adc dès trois additions, même en comptant le coût de conversion.

Pour briser une dépendance série, ajoutez une marge que vous remboursez plus tard : réservez de l'espace pour que l'opération critique s'exécute librement, puis réglez le travail différé en une seule passe.

Publié en 2017 et posté sur Hacker News en mai 2020, il a recueilli 518 points et 83 commentaires. Les praticiens ont rattaché l'astuce à du code réel : des commentateurs ont noté que l'arithmétique de corps de Curve25519 travaille modulo 2^255−19, si bien que les valeurs tiennent dans des membres de 51 bits, avec une variante en base 2^25,5 sur les CPU 32 bits ; d'autres ont débattu des instructions ADCX/ADOX de Broadwell et des blocages de registres partiels, et l'un a signalé une erreur dans l'explication du membre supérieur dans l'article. La technique est restée ce que l'article l'appelait : une représentation standard en base 2^51 en cryptographie, utilisée là où l'arithmétique de corps doit être rapide et à temps constant.