En JavaScript, podemos realizar sumas, restas, divisiones y módulos de 48 bits:
In JavaScript, we can perform 48-bit addition, subtraction, division and modulus, using the native Number type: function u48_add(a, b) { return (a + b) % Math.pow(2, 48); } function u48_sub(a, b) { return (a - b + Math.pow(2,48)) % Math.pow(2, 48); } function u48_div(a, b) { return Math.floor(a / b); } function u48_mod(a, b) { return a % b; } Todas estas operaciones funcionan porque los valores intermedios no pueden pasar Number.MAX_SAFE_INTEGER . Sin embargo, para la multiplicación, podrían:
function u48_mul(a, b) { return (a * b) % Math.pow(2, 48); } Entonces u48_mul podría devolver resultados incorrectos. Una solución sería usar BigInt:
function u48_mul(a, b) { return Number((BigInt(a) * BigInt(b)) % (2n ** 48n)); }Pero, en la mayoría de los navegadores, es drásticamente más lento. ¿Hay algún truco inteligente que nos permita realizar multiplicaciones sin signo de 48 bits en JavaScript más rápido?
Suponiendo que a, b >= 0, si escribe a y b como enteros de base 2 24 , tiene a = a 1 ⋅2 24 + a 0 y b = b 1 ⋅2 24 + b 0 ,
0 <= un 1 , un 0 , segundo 1 , segundo 0 < 2 24 .
De esta forma a⋅b = a 1 ⋅b 1 ⋅2 48 + (a 1 ⋅b 0 + a 0 ⋅b 1 )⋅2 24 + a 0 ⋅b 0 . Ahora, tomar este mod 2 48 hace que el primer término se convierta en 0. Los productos como 1 ⋅b 0 son la multiplicación de dos números enteros de 24 bits, por lo que multiplicados como números JS producen el resultado exacto de 48 bits. La suma de dos de estos valores puede producir un valor de 49 bits, pero sigue siendo < 2 53 y, por lo tanto, exacto. Como vamos a multiplicar por 2 24 , solo necesitamos retener los 24 bits de orden inferior de esta suma. Eso es bueno porque cuando hacemos AND (&) con una máscara de 24 bits, JS mantendrá solo los 32 bits de orden inferior. Finalmente sumamos el resultado a 0 ⋅b 0 , otro valor de 48 bits. El resultado puede exceder 2 48 y, si lo hace, simplemente restaremos 2 48 .
function mulmod48(a, b) { const two_to_the_24th = 16777216; const two_to_the_48th = two_to_the_24th * two_to_the_24th; const mask24 = two_to_the_24th - 1; let a0 = a & mask24; let a1 = (a - a0) / two_to_the_24th; let b0 = b & mask24; let b1 = (b - b0) / two_to_the_24th; let t1 = ((a1 * b0 + a0 * b1) & mask24) * two_to_the_24th; let result = t1 + a0 * b0; if (result >= two_to_the_48th) { result -= two_to_the_48th; } return result; }Esto se puede mejorar eliminando una de las divisiones por 2 24 , gracias a una observación de @Mark Dickinson. Aunque IEEE 754 binary64 floats puede representar exactamente todos los números enteros entre -2 53 y 2 53 , esos no son los únicos números enteros que se pueden representar exactamente. En particular, un número entero de 48 o 49 bits multiplicado por una potencia de 2 dentro del rango de exponente IEEE 754 especificado también se puede representar exactamente. Así podemos reemplazar estas cinco líneas
let a0 = a & mask24; let a1 = (a - a0) / two_to_the_24th; let b0 = b & mask24; let b1 = (b - b0) / two_to_the_24th; let t1 = ((a1 * b0 + a0 * b1) & mask24) * two_to_the_24th;con estos tres
let a0 = a & mask24; let b0 = b & mask24; let t1 = ((((a - a0) * b0 + a0 * (b - b0)) / two_to_the_24th) & mask24) * two_to_the_24th; dado que tanto (a - a0) como (b - b0) son múltiplos de 2 24 , también deben hacerlo los productos de estos con b0 y a0 y, por lo tanto, también debe hacerlo la suma de estos productos. En otras palabras, tanto (a - a0) como (b - b0) tienen solo 24 bits significativos , por lo que los productos tienen solo 48 bits significativos y la suma de estos tiene solo 49 bits significativos.
Ahora, ¿es esto más rápido que usar Bigints? En un experimento en Chrome 96.0.4664.55 (Official Build) (x86_64) , fue casi 6 veces más rápido que su versión BigInt de u48_mul .