在 JavaScript 中，我們可以執行 48 位加法、減法、除法和取模：
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;
}
所有這些操作都有效，因為中間值不能通過Number.MAX_SAFE_INTEGER。但是，對于乘法，他們可以：
function u48_mul(a, b) {
return (a * b) % Math.pow(2, 48);
}
所以u48_mul可能會回傳錯誤的結果。一個解決方案是使用 BigInt：
function u48_mul(a, b) {
return Number((BigInt(a) * BigInt(b)) % (2n ** 48n));
}
但是，在大多數瀏覽器中，它的速度要慢得多。有什么聰明的技巧可以讓我們在 JavaScript 中更快地執行 48 位無符號乘法？
uj5u.com熱心網友回復：
假設 a, b >= 0，如果你把 a 和 b 寫成基數 2 24 的整數，你有 a = a 1 ?2 24 a 0和 b = b 1 ?2 24 b 0 ,
0 <= a 1 , a 0 , b 1 , b 0 < 2 24。
在這種形式中，a?b = a 1 ?b 1 ?2 48 (a 1 ?b 0 a 0 ?b 1 )?2 24 a 0 ?b 0。現在取這個 mod 2 48會導致第一項變成 0。像 a 1 ?b 0這樣的乘積是兩個 24 位整數的乘積，所以乘以 JS 數字會產生精確的 48 位結果。將兩個這樣的值加在一起可能會產生一個 49 位的值，但這仍然 < 2 53，因此是精確的。因為我們要乘以 2 24我們只需要保留這個和的低 24 位。這很好，因為當我們將其與 24 位掩碼進行 AND (&) 時，JS 將僅保留低位 32 位。最后，我們將結果與另一個 48 位值0 ?b 0相加。結果可能會超過 2 48，如果超過，我們將減去 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;
}
由于@Mark Dickinson 的觀察，這可以通過將一個除法消除 2 24來改善。盡管 IEEE 754 binary64 浮點數可以精確表示 -2 53和 2 53之間的所有整數，但這些并不是唯一可以精確表示的整數。特別是在指定的 IEEE 754 指數范圍內，48 或 49 位整數乘以 2 的冪也可以精確表示。因此我們可以替換這五行
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 a0 = a & mask24;
let b0 = b & mask24;
let t1 = ((((a - a0) * b0 a0 * (b - b0)) / two_to_the_24th) & mask24) * two_to_the_24th;
因為這兩個(a - a0)和(b - b0)是2的倍數24因此必須的這些產品與b0和a0，因此也必須這些產品的總和。換句話說，(a - a0)和(b - b0)都只有 24位有效位，因此乘積只有 48 位有效位，并且它們的和只有 49 位有效位。
現在，這比使用 Bigints 更快嗎？在一項實驗中，Chrome 96.0.4664.55 (Official Build) (x86_64)它幾乎比你的 BigInt 版本快 6 倍u48_mul。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/374617.html
標籤：javascript 数学 浮点 位操作
上一篇：在給定距離的直線右側找到一個點