JavaScript 中的大数（BigInt）运算：实现加减乘除的自定义算法与性能考量
各位编程爱好者、专家们，大家好。今天我们将深入探讨 JavaScript 中的大数运算，特别是如何理解和实现其背后的自定义算法，并考量这些实现的性能。尽管 JavaScript 已经内置了 BigInt 类型来原生支持任意精度整数运算，但理解其底层原理，甚至能够自己实现一套大数运算系统，对于提升我们的编程功力、解决特定场景下的问题，乃至更好地利用原生 BigInt 都是非常有益的。
1. JavaScript 中 Number 类型的局限与 BigInt 的诞生
在 ECMAScript 2020 引入 BigInt 之前，JavaScript 只有一种数值类型：Number。Number 类型是基于 IEEE 754 标准的双精度浮点数，它能够表示的整数范围是有限的。具体来说，Number 类型能精确表示的整数范围是从 -(2^53 - 1) 到 2^53 - 1，即 Number.MIN_SAFE_INTEGER 到 Number.MAX_SAFE_INTEGER。这个范围大约是 +/- 9 * 10^15。
超出这个“安全”范围的整数，在使用 Number 类型表示时就会丢失精度。例如，9007199254740992 + 1 结果依然是 9007199254740992，因为 9007199254740993 无法被精确表示。这在处理加密货币、大型数据库 ID、高精度科学计算等场景时是不可接受的。
为了解决这一痛点，BigInt 应运而生。BigInt 是一种新的内置类型，它允许我们表示任意精度的整数。它的引入，使得 JavaScript 能够像其他支持大数运算的语言（如 Python）一样，原生处理超越 Number 类型安全范围的整数。
BigInt 的基本用法
创建 BigInt 值有两种主要方式：
- 在整数后面添加
n后缀：123n,0n,9007199254740992n。 - 调用
BigInt()构造函数：BigInt("123"),BigInt(123). 注意，如果传入Number类型的值，该值必须在Number.MAX_SAFE_INTEGER范围内，否则会抛出错误。传入字符串则没有此限制。
// Number 类型的限制
console.log(9007199254740992 + 1); // 9007199254740992 (精度丢失)
console.log(Number.MAX_SAFE_INTEGER); // 9007199254740991
// BigInt 的精确表示
const largeNum = 9007199254740991n;
console.log(largeNum + 1n); // 9007199254740992n (精确)
const anotherLargeNum = BigInt("123456789012345678901234567890");
console.log(anotherLargeNum); // 123456789012345678901234567890n2. 原生 BigInt 的算术运算
BigInt 支持所有标准的算术运算符：加 (+)、减 (-)、乘 (*)、除 (/)、取模 (%)、幂 (**)，以及位运算符。需要注意的是，BigInt 运算必须与 BigInt 类型的值进行，不能与 Number 类型混合运算，否则会抛出 TypeError。
let a = 100n;
let b = 20n;
console.log(a + b); // 120n
console.log(a - b); // 80n
console.log(a * b); // 2000n
console.log(a / b); // 5n (注意：BigInt 除法会截断小数部分，只保留整数，行为类似于 Math.floor() 对于正数，Math.ceil() 对于负数)
console.log(a % b); // 0n
let c = 10n;
let d = 3n;
console.log(c / d); // 3n
console.log(c % d); // 1n
// 幂运算
console.log(2n ** 10n); // 1024n
// 混合类型运算会报错
// console.log(10n + 5); // TypeError: Cannot mix BigInt and other types, use explicit conversions原生 BigInt 运算的性能通常非常高，因为它们是 JavaScript 引擎底层用 C/C++ 实现的，并且经过了高度优化。它们利用了高效的任意精度算术库，如 GMP (GNU Multiple Precision Arithmetic Library) 或类似的定制实现。在绝大多数实际应用中，我们都应该优先使用原生的 BigInt。
3. 为何需要自定义大数运算算法？
既然 JavaScript 已经提供了原生的 BigInt，为什么我们还要探讨自定义实现呢？这主要基于以下几个原因：
- 深入理解底层原理： 学习如何手动实现大数运算，能让我们对数字如何在计算机中表示和操作有更深刻的理解。这对于理解计算机科学基础、算法设计以及其他语言中的大数库都非常有帮助。
- 兼容性与 Polyfill： 在一些老旧的 JavaScript 环境中（例如不支持
BigInt的浏览器或 Node.js 版本），自定义实现可以作为一种 polyfill，提供类似的功能。尽管现在BigInt的支持度已经非常广泛，但在特定嵌入式环境或遗留系统中仍可能遇到。 - 特定优化需求： 某些高级算法或密码学应用可能需要对大数运算进行非常具体的优化，例如需要定制的模运算、位操作，或者探索比内置算法更快的特定场景算法（虽然这极少见，因为内置实现通常是高度优化的）。
- 教育与研究： 作为一种学习和研究工具，手动实现大数运算可以帮助我们探索不同的算法（如 Karatsuba 乘法、Newton-Raphson 除法等），比较它们的性能特性。
为了实现自定义的大数运算，我们需要一种方式来表示任意大的整数。最常见的方法是将大数存储为一系列“数字”或“肢体（limb）”的数组，每个数字都代表大数在某个特定基数下的一个位。
4. 大数的内部表示：基数与数组
在我们的自定义实现中，我们将把一个大整数表示为一个对象，其中包含：
sign: 一个布尔值，true表示负数，false表示正数或零。digits: 一个数字数组，存储大数在某个基数下的各个“位”或“肢体”。为了方便运算，我们通常将数组的第一个元素作为最低有效位（LSB），最后一个元素作为最高有效位（MSB）。
选择合适的基数 (Base)
选择一个合适的基数 BASE 至关重要。
- 如果
BASE太小（例如10），数组会很长，导致循环次数增多，运算效率降低。 - 如果
BASE太大，单个“位”的值可能会超出 JavaScriptNumber类型的安全范围，或者在中间乘法运算时产生溢出。
我们知道 Number.MAX_SAFE_INTEGER 大约是 9 * 10^15。为了在进行两个“肢体”相乘时，结果仍然能安全地存储在 Number 类型中，我们通常选择一个 BASE，使得 BASE * BASE 不超过 Number.MAX_SAFE_INTEGER。
一个常用的选择是 BASE = 10^7 (即 10,000,000)。
BASE * BASE = (10^7)^2 = 10^14，这远小于9 * 10^15，因此两个10^7 - 1范围内的数相乘，结果可以安全地存储在Number中。- 每个
digits数组元素最大值为BASE - 1，即9,999,999。
这样，我们的 BigInt 类结构将大致如下：
const BASE = 10_000_000; // 每个“肢体”的基数
const LOG_BASE = 7; // log10(BASE)
class MyBigInt {
constructor(value) {
this.sign = false; // false for positive/zero, true for negative
this.digits = []; // Array of numbers, least significant limb first
if (typeof value === 'number') {
if (value === 0) {
this.digits = [0];
} else if (value < 0) {
this.sign = true;
value = -value;
}
while (value > 0) {
this.digits.push(value % BASE);
value = Math.floor(value / BASE);
}
} else if (typeof value === 'string') {
if (value.startsWith('-')) {
this.sign = true;
value = value.substring(1);
}
if (value === '0') {
this.digits = [0];
this.sign = false; // Ensure 0 is always positive
} else {
// Parse string into base-BASE limbs
let tempDigits = [];
let i = value.length;
while (i > 0) {
let start = Math.max(0, i - LOG_BASE);
let chunk = value.substring(start, i);
tempDigits.push(parseInt(chunk, 10));
i = start;
}
this.digits = tempDigits;
}
} else if (value instanceof MyBigInt) {
this.sign = value.sign;
this.digits = [...value.digits]; // Deep copy
} else {
throw new Error("Invalid constructor argument for MyBigInt");
}
this._normalize(); // Remove leading zeros
}
// Helper to remove leading zeros (e.g., [0, 1, 2] should be [1, 2])
_normalize() {
while (this.digits.length > 1 && this.digits[this.digits.length - 1] === 0) {
this.digits.pop();
}
// If it's just [0], make sure sign is false
if (this.digits.length === 1 && this.digits[0] === 0) {
this.sign = false;
}
}
// Convert to string for display
toString() {
if (this.digits.length === 0 || (this.digits.length === 1 && this.digits[0] === 0)) {
return "0";
}
let s = this.digits[this.digits.length - 1].toString();
for (let i = this.digits.length - 2; i >= 0; i--) {
s += this.digits[i].toString().padStart(LOG_BASE, '0');
}
return this.sign ? '-' + s : s;
}
// Basic comparison of magnitudes (absolute values)
// Returns 0 if |a| == |b|, 1 if |a| > |b|, -1 if |a| < |b|
static _compareMagnitude(a, b) {
if (a.digits.length !== b.digits.length) {
return a.digits.length > b.digits.length ? 1 : -1;
}
for (let i = a.digits.length - 1; i >= 0; i--) {
if (a.digits[i] !== b.digits[i]) {
return a.digits[i] > b.digits[i] ? 1 : -1;
}
}
return 0; // Magnitudes are equal
}
// Check if the number is zero
isZero() {
return this.digits.length === 1 && this.digits[0] === 0;
}
}现在我们有了 MyBigInt 的基本框架，接下来我们将实现核心的算术运算。
5. 自定义加法运算 (add)
大数加法通常采用“竖式计算”或“小学加法”的算法。从最低有效位开始，逐位相加，并处理进位。
算法步骤：
- 处理符号：
- 如果两个数符号相同（同正或同负），则将它们的绝对值相加，结果的符号与它们相同。
- 如果两个数符号不同（一正一负），则实际上是绝对值相减。例如
A + (-B)相当于A - B；(-A) + B相当于B - A。这种情况下，我们将调用减法函数。
- （假设同符号，进行绝对值相加） 初始化一个
carry（进位）为 0。 - 创建一个新的
digits数组用于存放结果。 - 遍历两个数的
digits数组，从索引 0（最低有效位）开始，直到较长数组的末尾。- 在每次迭代中，获取当前位的数字（如果某个数已经没有该位，则视为 0）。
- 将两个数字和
carry相加：sum = digitA + digitB + carry。 - 结果当前位的数字是
sum % BASE。 - 更新
carry = Math.floor(sum / BASE)。 - 将结果当前位的数字添加到新的
digits数组中。
- 如果循环结束后
carry仍然大于 0，则将其作为一个新的最高有效位添加到结果数组中。 - 创建一个新的
MyBigInt对象，使用结果digits数组和确定的符号。
时间复杂度： O(N)，其中 N 是两个数中位数较多的那个的位数。
class MyBigInt {
// ... (previous code)
static add(a, b) {
// Handle signs: a + (-b) = a - b, (-a) + b = b - a
if (a.sign !== b.sign) {
let tempB = new MyBigInt(b);
tempB.sign = !tempB.sign; // Change sign of b
return MyBigInt.subtract(a, tempB);
}
const resultDigits = [];
let carry = 0;
const maxLength = Math.max(a.digits.length, b.digits.length);
for (let i = 0; i < maxLength; i++) {
const digitA = a.digits[i] || 0;
const digitB = b.digits[i] || 0;
const sum = digitA + digitB + carry;
resultDigits.push(sum % BASE);
carry = Math.floor(sum / BASE);
}
if (carry > 0) {
resultDigits.push(carry);
}
const result = new MyBigInt(0); // Dummy initialization
result.digits = resultDigits;
result.sign = a.sign; // Result has the same sign as operands
result._normalize();
return result;
}
}6. 自定义减法运算 (subtract)
大数减法同样采用“竖式计算”。它比加法稍微复杂，因为需要判断哪个数的绝对值更大，以及处理借位。
算法步骤：
- 处理符号：
- 如果
A - (-B)，等价于A + B。 - 如果
(-A) - B，等价于-(A + B)。 - 如果
(-A) - (-B)，等价于B - A。 - 如果
A - B(同为正)，则需要比较|A|和|B|的大小。- 如果
|A| < |B|，则结果为-(|B| - |A|)。 - 如果
|A| >= |B|，则结果为|A| - |B|。
- 如果
- 如果
- （假设
A和B都是正数，且|A| >= |B|，进行绝对值相减） 初始化borrow（借位）为 0。 - 创建一个新的
digits数组用于存放结果。 - 遍历两个数的
digits数组，从索引 0（最低有效位）开始，直到a.digits.length。- 获取当前位的数字：
digitA = a.digits[i] || 0，digitB = b.digits[i] || 0。 - 计算当前位的差值：
diff = digitA - digitB - borrow。 - 如果
diff < 0，需要借位：diff += BASE，borrow = 1。 - 否则，
borrow = 0。 - 将
diff添加到新的digits数组中。
- 获取当前位的数字：
- 创建一个新的
MyBigInt对象，使用结果digits数组和确定的符号。
时间复杂度： O(N)，其中 N 是两个数中位数较多的那个的位数。
class MyBigInt {
// ... (previous code)
static subtract(a, b) {
// Handle signs:
// A - (-B) = A + B
if (!a.sign && b.sign) {
let tempB = new MyBigInt(b);
tempB.sign = false; // Make b positive
return MyBigInt.add(a, tempB);
}
// (-A) - B = -(A + B)
if (a.sign && !b.sign) {
let tempA = new MyBigInt(a);
tempA.sign = false; // Make a positive
let sumAbs = MyBigInt.add(tempA, b);
sumAbs.sign = true; // Result is negative
return sumAbs;
}
// (-A) - (-B) = B - A
if (a.sign && b.sign) {
let tempA = new MyBigInt(a); tempA.sign = false;
let tempB = new MyBigInt(b); tempB.sign = false;
return MyBigInt.subtract(tempB, tempA);
}
// Now both are positive (a.sign === false && b.sign === false),
// we need to calculate |a| - |b|
// Determine which magnitude is larger
const cmp = MyBigInt._compareMagnitude(a, b);
let resultSign = false;
let num1 = a;
let num2 = b;
if (cmp === 0) { // Magnitudes are equal, result is 0
return new MyBigInt(0);
} else if (cmp < 0) { // |a| < |b|, result is -( |b| - |a| )
resultSign = true;
num1 = b; // Swap to ensure num1 >= num2
num2 = a;
}
// If cmp > 0, |a| > |b|, resultSign remains false, num1 and num2 are already a and b
const resultDigits = [];
let borrow = 0;
for (let i = 0; i < num1.digits.length; i++) {
const digit1 = num1.digits[i] || 0;
const digit2 = num2.digits[i] || 0; // num2 might be shorter
let diff = digit1 - digit2 - borrow;
if (diff < 0) {
diff += BASE;
borrow = 1;
} else {
borrow = 0;
}
resultDigits.push(diff);
}
const result = new MyBigInt(0);
result.digits = resultDigits;
result.sign = resultSign;
result._normalize();
return result;
}
}7. 自定义乘法运算 (multiply)
大数乘法有两种主要算法：传统的“竖式乘法”（也称作学校乘法）和更高效的“Karatsuba 算法”。我们将首先实现学校乘法，因为它更直观。
7.1 学校乘法 (Schoolbook Multiplication)
这是我们小学学过的乘法方法，它涉及到将一个数的每一位与另一个数的每一位相乘，然后将所有的部分积相加。
算法步骤：
- 处理符号：如果两个数符号不同，结果为负；否则结果为正。
- 创建一个结果
digits数组，其长度最大为a.digits.length + b.digits.length，并用 0 填充。 - 遍历
a的每一个位a_i(从i = 0到a.digits.length - 1)。 - 在内层循环中，遍历
b的每一个位b_j(从j = 0到b.digits.length - 1)。- 计算
product = a_i * b_j + resultDigits[i + j] + carry。 resultDigits[i + j]是当前位置上的累积和。resultDigits[i + j] = product % BASE。carry = Math.floor(product / BASE)。
- 计算
- 如果内层循环结束后
carry > 0，则将其加到resultDigits[i + b.digits.length]上。 - 创建一个新的
MyBigInt对象，使用结果digits数组和确定的符号。
时间复杂度： O(N*M)，其中 N 和 M 是两个数的位数。如果 N 和 M 相近，则为 O(N^2)。
class MyBigInt {
// ... (previous code)
static multiply(a, b) {
if (a.isZero() || b.isZero()) {
return new MyBigInt(0);
}
// Determine result sign
const resultSign = a.sign !== b.sign;
// Take absolute values for multiplication
const absA = new MyBigInt(a); absA.sign = false;
const absB = new MyBigInt(b); absB.sign = false;
const resultDigits = new Array(absA.digits.length + absB.digits.length).fill(0);
for (let i = 0; i < absA.digits.length; i++) {
let carry = 0;
const digitA = absA.digits[i];
for (let j = 0; j < absB.digits.length; j++) {
const digitB = absB.digits[j];
const product = digitA * digitB + resultDigits[i + j] + carry;
resultDigits[i + j] = product % BASE;
carry = Math.floor(product / BASE);
}
if (carry > 0) {
resultDigits[i + absB.digits.length] += carry;
}
}
const result = new MyBigInt(0);
result.digits = resultDigits;
result.sign = resultSign;
result._normalize();
return result;
}
}7.2 Karatsuba 乘法 (Karatsuba Multiplication)
当数字非常大时，Karatsuba 算法比学校乘法更高效。它是一种分治算法，将两个 N 位数的乘法分解成三次 N/2 位数的乘法，而不是学校乘法的四次。
假设我们要计算 X * Y，其中 X = X1 * B^(N/2) + X0 且 Y = Y1 * B^(N/2) + Y0。
则 X * Y = (X1 * B^(N/2) + X0) * (Y1 * B^(N/2) + Y0)
X * Y = X1*Y1 * B^N + (X1*Y0 + X0*Y1) * B^(N/2) + X0*Y0
Karatsuba 的巧妙之处在于，它通过以下方式计算中间项 (X1*Y0 + X0*Y1)：
Z1 = X1 * Y1
Z0 = X0 * Y0
Z2 = (X1 + X0) * (Y1 + Y0) - Z1 - Z0
其中 Z2 就是 X1*Y0 + X0*Y1。
这样，我们将四个 N/2 位数乘法（X1*Y1, X1*Y0, X0*Y1, X0*Y0）减少到了三个（Z1, Z0, (X1+X0)*(Y1+Y0)）。
时间复杂度： O(N^(log2 3))，约 O(N^1.58)。当 N 足够大时，这比 O(N^2) 要快得多。
通常，对于较小的 N，学校乘法更快，因为 Karatsuba 引入了额外的加法、减法和递归开销。实际实现中，会有一个阈值，当数字位数小于该阈值时，使用学校乘法；大于阈值时，使用 Karatsuba 算法。
Karatsuba 算法的完整实现较为复杂，需要额外的辅助函数来分割和组合 MyBigInt 对象。在这里，我们主要理解其概念和性能优势，并将其作为大数乘法的优化方向。
8. 自定义除法运算 (divide)
大数除法通常采用“长除法”算法。这是所有基本运算中最复杂的。它涉及到多次的乘法、减法和比较操作。
算法步骤概述：
- 处理符号：如果两个数符号不同，结果为负；否则结果为正。
- 处理除数为零的情况：抛出错误。
- 处理被除数小于除数的情况：商为 0，余数为被除数。
- 将问题转化为
|A| / |B|。 - （假设
A和B都是正数，且|A| >= |B|）- 长除法通过迭代地估算商的每一位来工作。它从被除数的最高位开始，每次尝试找出能乘以除数且不超过当前部分被除数的最大数字。
- 为了更有效地估算，通常需要预处理除数，使其最高位不为零（通过乘以一个因子来标准化）。
- 在每一轮中，从当前剩余被除数中截取与除数位数相同或多一位的部分。
- 估算商的当前位：
q = floor(current_dividend_part / divisor)。这个估算可以通过一些启发式方法（例如只看最高位）或二分查找来优化。 - 计算
product = q * divisor。 - 从
current_dividend_part中减去product。 - 将
q添加到商的结果中，并将减法结果作为新的部分被除数，继续下一轮。
- 最终得到商和余数。
时间复杂度： 估算商的每一位需要进行一次乘法和一次减法。如果使用学校乘法，每次迭代的成本是 O(ML)，其中 M 是除数的位数，L 是商的位数。总共需要进行 N/L 次迭代（如果商是 N/L 位）。因此，总复杂度大约是 O(NM)。如果商的位数也与被除数位数 N 相同，则为 O(N^2)。
由于长除法的实现非常冗长和复杂，涉及到大量的辅助函数（如比较、单肢体乘法、单肢体减法），这里我们将提供一个简化版的概念性代码，不包含所有优化和边缘情况处理。
class MyBigInt {
// ... (previous code)
// Helper: is current MyBigInt equal to zero?
isZero() {
return this.digits.length === 1 && this.digits[0] === 0;
}
// Helper: Get absolute value
abs() {
const result = new MyBigInt(this);
result.sign = false;
return result;
}
// Helper: Shift left by 'count' limbs (effectively multiplying by BASE^count)
static _shiftLeft(bigInt, count) {
if (bigInt.isZero()) return new MyBigInt(0);
const newDigits = [...bigInt.digits];
for (let i = 0; i < count; i++) {
newDigits.unshift(0);
}
const result = new MyBigInt(0);
result.digits = newDigits;
result.sign = bigInt.sign;
return result;
}
// Helper: Multiply by a single limb (number)
static _multiplyByLimb(bigInt, limb) {
if (limb === 0) return new MyBigInt(0);
if (limb === 1) return new MyBigInt(bigInt);
let carry = 0;
const resultDigits = [];
for (let i = 0; i < bigInt.digits.length; i++) {
const product = bigInt.digits[i] * limb + carry;
resultDigits.push(product % BASE);
carry = Math.floor(product / BASE);
}
if (carry > 0) {
resultDigits.push(carry);
}
const result = new MyBigInt(0);
result.digits = resultDigits;
result.sign = bigInt.sign;
result._normalize();
return result;
}
// Division (simplified long division, returns { quotient, remainder })
static divide(a, b) {
if (b.isZero()) {
throw new Error("Division by zero");
}
if (a.isZero()) {
return { quotient: new MyBigInt(0), remainder: new MyBigInt(0) };
}
const absA = a.abs();
const absB = b.abs();
const cmp = MyBigInt._compareMagnitude(absA, absB);
if (cmp < 0) { // |a| < |b|
return { quotient: new MyBigInt(0), remainder: newBigInt(a) };
}
if (cmp === 0) { // |a| == |b|
const quotient = new MyBigInt(1);
quotient.sign = (a.sign !== b.sign);
return { quotient: quotient, remainder: new MyBigInt(0) };
}
// Now |a| > |b|
const quotientDigits = new Array(absA.digits.length - absB.digits.length + 1).fill(0);
let currentRemainder = new MyBigInt(absA); // Working copy of the dividend
// Perform long division
for (let i = absA.digits.length - absB.digits.length; i >= 0; i--) {
// Take a slice of currentRemainder that's roughly the size of absB
// For simplicity, we'll try to estimate directly
// Find the biggest multiple of absB that fits into currentRemainder
// (shifted appropriately)
let high = BASE - 1; // Max possible digit for the quotient limb
let low = 0;
let q = 0; // The quotient digit for this position
// Binary search for the quotient digit
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (mid === 0) { // Avoid multiplying by 0 and getting stuck
low = 1;
continue;
}
// Calculate mid * absB, shifted to the current position
let product = MyBigInt._multiplyByLimb(absB, mid);
let shiftedProduct = MyBigInt._shiftLeft(product, i); // Shift for current position
if (MyBigInt._compareMagnitude(shiftedProduct, currentRemainder) <= 0) {
q = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
quotientDigits[i] = q;
// Subtract q * absB (shifted) from currentRemainder
let product = MyBigInt._multiplyByLimb(absB, q);
let shiftedProduct = MyBigInt._shiftLeft(product, i);
currentRemainder = MyBigInt.subtract(currentRemainder, shiftedProduct);
currentRemainder._normalize(); // Ensure it's clean
}
const finalQuotient = new MyBigInt(0);
finalQuotient.digits = quotientDigits;
finalQuotient.sign = (a.sign !== b.sign);
finalQuotient._normalize();
const finalRemainder = new MyBigInt(currentRemainder);
finalRemainder.sign = a.sign; // Remainder takes sign of dividend
finalRemainder._normalize();
return { quotient: finalQuotient, remainder: finalRemainder };
}
}注意： 上述 divide 方法是一个相对简化的实现，为了清晰展示长除法的核心思想。在实际生产级的大数库中，除法算法会更加复杂和优化，例如会进行预归一化（Normalisation）步骤来确保除数最高位足够大，以提高商位估算的准确性，避免多次试错。此外，也会采用更高效的 _multiplyByLimb 和 subtract 操作。
9. 性能考量与优化
自定义大数运算的性能是一个复杂的话题，受到多种因素的影响：
9.1 基数（BASE）的选择
- 影响：
BASE越大，digits数组的长度就越短，这意味着在相同数字大小下，循环迭代次数更少，数组操作（如访问、插入、删除）的开销也更小。 - 限制：
BASE不能无限大。我们选择BASE = 10^7是因为(BASE-1) * (BASE-1)仍然可以安全地存储在Number.MAX_SAFE_INTEGER范围内。如果BASE过大，导致中间乘积溢出Number类型，我们就需要在这些中间计算中使用BigInt(如果可用) 或更复杂的逻辑来处理，这将使自定义实现的意义减弱，或增加实现难度。 - 二进制基数： 在实际的
BigInt库中，通常会选择2^N作为基数，例如2^26或2^30。这是因为位运算（&,|,>>,<<）在计算机中执行效率极高，可以更自然地处理进位和借位，而无需进行昂贵的除法和取模运算。例如，sum % BASE可以用sum & (BASE - 1)实现（如果BASE是 2 的幂），Math.floor(sum / BASE)可以用sum >> LOG_BASE实现。
9.2 算法复杂度
| 运算类型 | 算法 | 时间复杂度 (N 位数) | 备注 |
|---|---|---|---|
| 加法 | 学校加法 | O(N) | 直观，高效 |
| 减法 | 学校减法 | O(N) | 直观，高效 |
| 乘法 | 学校乘法 | O(N^2) | 简单，对小 N 效率尚可 |
| 乘法 | Karatsuba 算法 | O(N^1.58) | 分治，对大 N 显著优于 O(N^2) |
| 乘法 | Toom-Cook 算法 | O(N^1.46) | 比 Karatsuba 更复杂，对更大的 N 更优 |
| 乘法 | Schönhage-Strassen | O(N log N log log N) | 基于 FFT，理论上最快，但常数因子大，只适用于超大数 |
| 除法 | 长除法 | O(N^2) | 最复杂，涉及多次乘法和减法 |
对于我们的自定义实现，我们主要关注了 O(N) 的加减法和 O(N^2) 的学校乘法和长除法。对于需要处理极其巨大的数字的场景，考虑实现 Karatsuba 或更高级的算法是必要的。
9.3 JavaScript 引擎的优化
- JIT 编译： 现代 JavaScript 引擎（如 V8）具有即时（JIT）编译器，可以优化热点代码路径。然而，对于我们自定义的
MyBigInt对象，由于其内部是动态数组，并且涉及频繁的数组操作和对象创建，JIT 编译器可能无法像优化原生类型那样进行深度优化。 - 内存分配与垃圾回收： 每次进行加减乘除运算时，我们都会创建新的
MyBigInt对象和新的digits数组。频繁的对象创建会导致频繁的垃圾回收（GC），这会引入性能暂停，尤其是在处理大量运算时。- 优化方向： 考虑使用可变（mutable）的
MyBigInt对象，允许原地修改数字，而不是每次都返回新对象。但这会增加编程复杂性，并可能违反函数式编程的某些好处。或者，通过对象池复用MyBigInt实例和digits数组。
- 优化方向： 考虑使用可变（mutable）的
9.4 原生 BigInt vs. 自定义实现
在大多数情况下，原生 BigInt 的性能将远远优于任何纯 JavaScript 实现。
- 底层实现： 原生
BigInt是用 C/C++ 实现的，直接操作内存，避免了 JavaScript 对象的额外开销。 - 算法选择： 它们通常会根据数字的大小动态选择最合适的算法（例如，小整数用学校乘法，大整数用 Karatsuba 或 Toom-Cook）。
- 硬件加速： 某些底层操作可能利用 CPU 的特定指令集进行硬件加速。
因此，除非有非常特殊的兼容性或研究需求，否则在生产环境中应始终优先使用原生的 BigInt。自定义实现更多是作为一种学习和理解的工具。
10. MyBigInt 类的完整结构与使用示例
为了更好地封装，我们将所有静态方法都放到 MyBigInt 类中，并通过实例方法调用它们。
const BASE = 10_000_000; // Each "limb" represents a number up to BASE-1
const LOG_BASE = 7; // log10(BASE)
class MyBigInt {
constructor(value) {
this.sign = false; // false for positive/zero, true for negative
this.digits = []; // Array of numbers, least significant limb first
if (typeof value === 'number') {
if (value === 0) {
this.digits = [0];
} else if (value < 0) {
this.sign = true;
value = -value;
}
while (value > 0) {
this.digits.push(value % BASE);
value = Math.floor(value / BASE);
}
} else if (typeof value === 'string') {
if (value.startsWith('-')) {
this.sign = true;
value = value.substring(1);
}
if (value === '0') {
this.digits = [0];
this.sign = false;
} else {
let tempDigits = [];
let i = value.length;
while (i > 0) {
let start = Math.max(0, i - LOG_BASE);
let chunk = value.substring(start, i);
tempDigits.push(parseInt(chunk, 10));
i = start;
}
this.digits = tempDigits.reverse(); // Store LSB first
}
} else if (value instanceof MyBigInt) {
this.sign = value.sign;
this.digits = [...value.digits]; // Deep copy
} else {
throw new Error("Invalid constructor argument for MyBigInt");
}
this._normalize();
}
_normalize() {
while (this.digits.length > 1 && this.digits[this.digits.length - 1] === 0) {
this.digits.pop();
}
if (this.digits.length === 1 && this.digits[0] === 0) {
this.sign = false;
}
}
toString() {
if (this.digits.length === 0 || (this.digits.length === 1 && this.digits[0] === 0)) {
return "0";
}
let s = this.digits[this.digits.length - 1].toString();
for (let i = this.digits.length - 2; i >= 0; i--) {
s += this.digits[i].toString().padStart(LOG_BASE, '0');
}
return this.sign ? '-' + s : s;
}
isZero() {
return this.digits.length === 1 && this.digits[0] === 0;
}
abs() {
const result = new MyBigInt(this);
result.sign = false;
return result;
}
// Helper: Compare magnitudes |a| and |b|
static _compareMagnitude(a, b) {
if (a.digits.length !== b.digits.length) {
return a.digits.length > b.digits.length ? 1 : -1;
}
for (let i = a.digits.length - 1; i >= 0; i--) {
if (a.digits[i] !== b.digits[i]) {
return a.digits[i] > b.digits[i] ? 1 : -1;
}
}
return 0;
}
// Instance methods for convenience
add(other) { return MyBigInt.add(this, other); }
subtract(other) { return MyBigInt.subtract(this, other); }
multiply(other) { return MyBigInt.multiply(this, other); }
divide(other) { return MyBigInt.divide(this, other).quotient; }
remainder(other) { return MyBigInt.divide(this, other).remainder; }
// --- Static Arithmetic Methods (as defined previously) ---
static add(a, b) { /* ... same implementation as above ... */ }
static subtract(a, b) { /* ... same implementation as above ... */ }
static multiply(a, b) { /* ... same implementation as above ... */ }
static _shiftLeft(bigInt, count) { /* ... same implementation as above ... */ }
static _multiplyByLimb(bigInt, limb) { /* ... same implementation as above ... */ }
static divide(a, b) { /* ... same implementation as above ... */ }
}
// Example Usage:
const num1 = new MyBigInt("12345678901234567890");
const num2 = new MyBigInt("9876543210987654321");
console.log(`Num1: ${num1.toString()}`);
console.log(`Num2: ${num2.toString()}`);
// Addition
const sum = num1.add(num2);
console.log(`Sum: ${sum.toString()}`); // Should be 22222222222222222211
// Subtraction
const diff = num1.subtract(num2);
console.log(`Difference: ${diff.toString()}`); // Should be 24691357903456790169
// Subtraction with negative result
const diff2 = num2.subtract(num1);
console.log(`Difference (negative): ${diff2.toString()}`); // Should be -24691357903456790169
// Multiplication
const product = num1.multiply(num2);
console.log(`Product: ${product.toString()}`); // Should be 1219326311370217950943501596656705210
// Division
const quotientResult = MyBigInt.divide(num1, num2);
const remainderResult = MyBigInt.divide(num1, num2).remainder;
console.log(`Quotient: ${quotientResult.toString()}`); // Should be 1
console.log(`Remainder: ${remainderResult.toString()}`); // Should be 24691357903456790169
// Test with native BigInt for comparison
const nativeNum1 = 12345678901234567890n;
const nativeNum2 = 9876543210987654321n;
console.log("--- Native BigInt Comparison ---");
console.log(`Native Sum: ${nativeNum1 + nativeNum2}`);
console.log(`Native Difference: ${nativeNum1 - nativeNum2}`);
console.log(`Native Product: ${nativeNum1 * nativeNum2}`);
console.log(`Native Quotient: ${nativeNum1 / nativeNum2}`);
console.log(`Native Remainder: ${nativeNum1 % nativeNum2}`);这段代码展示了如何构建一个基本的 MyBigInt 类，实现了大数的加、减、乘、除运算，并考量了性能相关的基数选择。理解这些自定义算法不仅能加深我们对数字运算原理的理解，也能帮助我们更好地 appreciate 原生 BigInt 带来的便利和高效。尽管手写实现难以匹敌原生 BigInt 的性能，但它提供了一个宝贵的学习机会，让我们能够深入探索任意精度算术的奥秘。