#MoonBit BigInteger

#特性

#核类型与构造

• 任意精度整数 BigInteger，小端序 Array[UInt] 存储，独立符号位
• 构造方式：from_int, from_uint, from_int64, from_string, from_string_radix, from_bytes_be, from_bytes_le
• 转换出去：to_string, to_string_radix, to_hex/from_hex, to_binary/from_binary, to_octal/from_octal, to_int64, to_uint64, to_bytes_be, to_bytes_le

#算术运算（trait 操作符）

• 加 +、减 -、乘 *、除 /、取余 %（截断除法，余数符号与被除数相同）
• 左移 <<、右移 >>
• 比较 < <= > >= == !=（实现 Eq 与 Compare trait）
• 幂 pow、模幂 pow_mod（二进制快速幂）、平方根 sqrt（牛顿迭代，向下取整）

#位运算（基于无符号幅度）

• bit_and, bit_or, bit_xor — 按位与/或/异或
• bit_not — 二进制补码取反，返回 -(self+1)
• set_bit(pos), clear_bit(pos), toggle_bit(pos)
• count_ones() — popcount
• trailing_zeros() — 末尾连续 0 的个数
• get_bit(pos), bit_length()

#数论函数

• gcd, lcm — 欧几里得算法
• extended_gcd(a, b) -> (g, x, y) — Bezout 系数（gcd 总是非负，对负数输入正确处理符号）
• mod_inverse(modulus) — 模逆元，不存在时抛出 ModularArithmeticError
• is_prime(k) — Miller-Rabin 素性测试；对 n < 3.3×10²⁴ 使用确定性 witnesses，更大者追加 k 轮随机测试
• next_prime(), prev_prime()
• jacobi_symbol(a, n) — Jacobi 符号
• crt(remainders) — 中国剩余定理（要求模数两两互素，否则抛出 ModularArithmeticError）

#排列组合与特殊数

• factorial(n), fibonacci(n)
• combination(n, k), permutation(n, k), permutation_with_repetition(n, k)
• random_range(min, max, seed) — 非加密安全 LCG，用于测试与模拟

#辅助方法

• is_zero, is_positive, is_negative, is_odd, is_even
• abs, negate, sign, min(other), max(other), clamp(low, high), copy()

#安装

moon update
moon add amor2025/biginteger

{
  "import": [
    "amor2025/biginteger/lib"
  ]
}

#使用示例

#构造与字符串转换

let a = BigInteger::from_int(123)
let b = BigInteger::from_string("123456789012345678901234567890")
let neg = BigInteger::from_int64(-9223372036854775808L)

// 往返转换
assert_true(b.to_string() == "123456789012345678901234567890")

#算术运算

let a = BigInteger::from_string("123456789012345678901234567890")
let b = BigInteger::from_string("987654321098765432109876543210")

let sum = a + b
let product = a * b
let quotient = a / b
let remainder = a % b

#进制转换

let n = BigInteger::from_int(255)

assert_true(n.to_hex() == "ff")
assert_true(n.to_binary() == "11111111")
assert_true(n.to_octal() == "377")
assert_true(n.to_string_radix(36) == "73")

// 解析回来
assert_true(BigInteger::from_hex("deadbeef").to_string() == "3735928559")
assert_true(BigInteger::from_string_radix("zz", 36) == BigInteger::from_int(1295))

#字节数组转换

let n = BigInteger::from_int(0x12345678)
let bytes_be = n.to_bytes_be()  // [0x12, 0x34, 0x56, 0x78]
let bytes_le = n.to_bytes_le()  // [0x78, 0x56, 0x34, 0x12]

// 往返转换
assert_true(BigInteger::from_bytes_be(bytes_be) == n)

#位运算

let a = BigInteger::from_int(0b11001010)
let b = BigInteger::from_int(0b10110101)

assert_true(a.bit_and(b) == BigInteger::from_int(0b10000000))
assert_true(a.bit_or(b)  == BigInteger::from_int(0b11111111))
assert_true(a.bit_xor(b) == BigInteger::from_int(0b01111111))

// 二进制补码取反：~n = -(n+1)
assert_true(BigInteger::from_int(5).bit_not() == BigInteger::from_int(-6))

// 位操作
let c = BigInteger::from_int(0)
assert_true(c.set_bit(3) == BigInteger::from_int(8))
assert_true(BigInteger::from_int(255).count_ones() == 8)

#数论函数

// 素性测试 — 对 n < 3.3×10²⁴ 结果确定
assert_true(BigInteger::from_int(7919).is_prime(10))
assert_true(!BigInteger::from_int(7917).is_prime(10))

// 找邻近素数
assert_true(BigInteger::from_int(10).next_prime() == BigInteger::from_int(11))
assert_true(BigInteger::from_int(13).prev_prime() == BigInteger::from_int(11))

// 模逆元
let inv = BigInteger::from_int(3).mod_inverse(BigInteger::from_int(11))
// 3 * 4 = 12 ≡ 1 (mod 11)
assert_true(inv == BigInteger::from_int(4))

// 中国剩余定理
// x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = 23
let remainders = [
  (BigInteger::from_int(2), BigInteger::from_int(3)),
  (BigInteger::from_int(3), BigInteger::from_int(5)),
  (BigInteger::from_int(2), BigInteger::from_int(7))
]
assert_true(BigInteger::crt(remainders) == BigInteger::from_int(23))

#错误处理

• ParseError(String) — 字符串解析失败时抛出
• ModularArithmeticError(String) — 模运算约束不满足时抛出

// 使用 try/catch 处理解析错误
let result = try {
  Some(BigInteger::from_string("not_a_number"))
} catch {
  ParseError(_) => None
}

// mod_inverse 不存在时抛出 ModularArithmeticError
let _ = try {
  BigInteger::from_int(4).mod_inverse(BigInteger::from_int(8))
  false
} catch {
  ModularArithmeticError(_) => true  // gcd(4,8) != 1
}

• 除以零
• 负数的平方根
• 负指数的幂运算
• to_int64 / to_uint64 溢出或符号不匹配

#测试

moon test

• 基础测试（20）：构造、字符串转换、比较、算术、位运算、数论
• 正确性测试（8）：Int::min_value 边界、负数除法、sqrt 边界、确定性素性测试、扩展 GCD、模逆元、排列
• 功能测试（10）：位运算、进制转换、字节数组转换、邻近素数、Jacobi 符号、CRT
• 属性测试（12）：交换律、结合律、分配律、零元/一元律、符号律、除法一致性、gcd*lcm 关系、pow_mod 一致性
• 错误处理测试（10）：ParseError 路径、ModularArithmeticError 路径、有效输入正常工作
• Karatsuba 测试（9）：平方、非对称大小、大数乘积、逐次加法对照、负数、双负数、幂运算、bit_length、mod_inverse

#实现细节

#数据结构

• digits : Array[UInt] — 小端序存储（低位在前），每个元素为 32 位无符号整数
• negative : Bool — 符号位，零值规定为 false
• 自动 normalize 去除高位前导零

#算法

• 乘法：阈值调度 — 小数用长乘法 O(n·m)，大数（≥30 limbs）用 Karatsuba O(n^log₂3 ≈ n^1.585)
• 除法：基于二分查找商位的 long division，复杂度 O(32·n²)
• 幂运算：二进制快速幂 O(log e) 次乘法
• 模幂：Montgomery-style 二进制模幂
• 平方根：牛顿迭代，初始猜测 1 << ceil(bit_length/2) 保证 ≥ √n
• 素性测试：确定性 Miller-Rabin（n < 3.3×10²⁴ 用 12 个固定 witnesses，更大者追加随机轮）
• 字符串解析：9 位一组分块处理，每块用 UInt64 累加，避免逐位乘加
• 字符串输出：分块除以 10⁹，使用单 limb 快速除法 fast_div_small（O(n) 每次），每块补齐 9 位前导零

#许可证