Los miembros en radix 2^51 superan a las cadenas de suma con acarreo al diferir los acarreos

Sumar números más anchos que 64 bits debería ser fácil: dividir cada entero de 256 bits en cuatro piezas de 64 bits, sumarlas y propagar cualquier desbordamiento hacia arriba. El problema es el desbordamiento: sin acarreos la respuesta es incorrecta, así que la versión correcta encadena la instrucción de suma con acarreo de x86 (adc) desde el miembro menos significativo hacia arriba. En las CPU modernas con ejecución fuera de orden esa cadena es más lenta que el código paralelo incorrecto: adc es una instrucción más pesada, y cada una depende del flag de acarreo producido por la anterior. Una CPU Haswell puede emitir hasta cuatro sumas independientes por ciclo, pero los adc encadenados se ejecutan en serie.

La solución contraintuitiva, conocida en la literatura criptográfica como representación radix 2^51, consiste en usar más miembros, cada uno más pequeño que un registro. Donde el enfoque obvio divide 256 bits en cuatro dígitos en base 2^64, este enfoque lo divide en cinco dígitos en base 2^51; cada miembro de 64 bits todavía contiene su dígito, pero los 12–13 bits superiores quedan vacíos como espacio donde pueden acumularse los acarreos. Gracias a ese margen, sumar valores normalizados no produce ningún acarreo hasta que se llenan los bits libres —hasta aproximadamente 2^13 sumas—, de modo que cada suma es independiente y el procesador las programa en paralelo.

Los acarreos no se eliminan, solo se difieren. Cuando se agota el margen, una pasada de normalización desplaza el desbordamiento de cada miembro al miembro superior y limpia el espacio libre, y la resta funciona de la misma manera tratando los miembros como con signo, a costa de un bit de margen. Los benchmarks rápidos del autor en una máquina Haswell encontraron que la suma en radix 2^51 ya era más rápida que la suma en radix 2^64 con tan solo tres sumas, incluido el costo de convertir hacia y desde la representación, y el ahorro crece a medida que se acumulan más sumas.

La publicación construye primero la intuición sobre el papel: en base 10, ampliar el rango de cada dígito para que pueda contar más allá de 9 permite sumar varios números normalizados antes de que cualquier dígito se desborde, y una pasada de normalización convierte el resultado de vuelta. Trasladado a registros binarios, el mismo principio es la razón por la que la representación es estándar en criptografía —y por la que, contraintuitivamente, repartir un número entre más registros y emitir más instrucciones hace que la aritmética sea más rápida. Publicado por primera vez en 2017, el artículo se publicó en Hacker News en mayo de 2020 y obtuvo 518 puntos y 83 comentarios.

Reducir los miembros a 51 bits para que los bits libres absorban los acarreos: las sumas se mantienen independientes y en paralelo, y la normalización ocurre una sola vez al final

Los acarreos son la dependencia: las instrucciones adc encadenadas se serializan porque cada una espera al flag de acarreo anterior, mientras que las sumas simples independientes pueden emitirse cuatro por ciclo en Haswell.

El margen vacío es el truco: los dígitos de 51 bits dentro de registros de 64 bits dejan 12–13 bits libres, de modo que ocurren aproximadamente 2^13 sumas antes de que deba propagarse algún acarreo.

Una pasada diferida supera a muchas inmediatas: la normalización al final es un barrido fijo en lugar de una dependencia de acarreo en cada operación.

El miembro extra se paga solo: cinco sumas simples superan a cuatro cadenas adc a partir de tan solo tres sumas, incluso contando el costo de conversión.

Para romper una dependencia serial, añade holgura que pagas después: reserva margen para que la operación crítica se ejecute libre, y luego resuelve el trabajo diferido en una sola pasada.

Publicado en 2017 y publicado en Hacker News en mayo de 2020, obtuvo 518 puntos y 83 comentarios. Los profesionales anclaron el truco a código real: los comentaristas señalaron que la aritmética de campo de Curve25519 funciona módulo 2^255−19, por lo que los valores caben en miembros de 51 bits, con una variante radix 2^25.5 en CPU de 32 bits; otros debatieron las instrucciones ADCX/ADOX de Broadwell y las paradas de registro parcial, y uno señaló un error en la explicación del artículo sobre el miembro superior. La técnica siguió siendo lo que la publicación la llamó: una representación estándar radix 2^51 en criptografía, usada donde la aritmética de campo debe ser rápida y de tiempo constante.