高精度(大整数)

What · 是什么

高精度（bignum / arbitrary-precision arithmetic）：对超出内建整型位宽的大整数进行四则运算。C++ 需要手写（用 string/数组存储，从低位开始按竖式运算，或压位存 4~9 位一组）；Python 内建 int 是任意精度，直接支持任意大小的 + - * // % ** 与位运算，底层已做 Karatsuba/Toom/FFT 级优化，竞赛中几乎不用手写，但需了解 Python 大数的复杂度特性（乘法大数用 Karatsuba，更大用 Toom/FFT，比朴素 O(n^2) 快很多）。PyPy 的 int 同样是任意精度但内部实现不同，大数乘法性能与 CPython 有差异。核心知识：数组竖式算法、压位、快速乘法（Karatsuba、FFT/NTT）。

Why · 为什么

How · 实现

伪代码

# 竖式加法（压位，base=B），a,b 为低位在前数组
def add(a, b):
    c, carry, i = [], 0, 0
    while i < len(a) or i < len(b) or carry:
        v = carry
        if i < len(a): v += a[i]
        if i < len(b): v += b[i]
        c.append(v % B); carry = v // B; i += 1
    return c

# 竖式乘法 O(n*m)
def mul(a, b):
    c = [0] * (len(a) + len(b))
    for i, x in enumerate(a):
        carry = 0
        for j in range(len(b)):
            cur = c[i+j] + x*b[j] + carry
            c[i+j] = cur % B; carry = cur // B
        c[i+len(b)] += carry
    while len(c) > 1 and c[-1] == 0: c.pop()
    return c

Python 实现

BASE = 10000  # 压位基底：每格存 4 位十进制


def str_to_blocks(s):
    s = s.lstrip('0') or '0'
    blocks = []
    for i in range(len(s), 0, -4):
        blocks.append(int(s[max(0, i - 4):i]))
    return blocks


def blocks_to_str(b):
    if not b:
        return '0'
    res = str(b[-1])
    for x in reversed(b[:-1]):
        res += f'{x:04d}'
    return res


def add(a, b):
    i = carry = 0
    c = []
    while i < len(a) or i < len(b) or carry:
        v = carry
        if i < len(a):
            v += a[i]
        if i < len(b):
            v += b[i]
        c.append(v % BASE)
        carry = v // BASE
        i += 1
    return c


def sub(a, b):  # 要求 a >= b
    i = borrow = 0
    c = []
    while i < len(a) or borrow:
        v = a[i] - borrow - (b[i] if i < len(b) else 0)
        borrow = 0
        if v < 0:
            v += BASE
            borrow = 1
        c.append(v)
        i += 1
    while len(c) > 1 and c[-1] == 0:
        c.pop()
    return c


def mul(a, b):
    c = [0] * (len(a) + len(b))
    for i, x in enumerate(a):
        carry = 0
        for j in range(len(b)):
            cur = c[i + j] + x * b[j] + carry
            c[i + j] = cur % BASE
            carry = cur // BASE
        c[i + len(b)] += carry
    while len(c) > 1 and c[-1] == 0:
        c.pop()
    return c


def main():
    # 与内建 int 对拍验证压位四则
    import random
    random.seed(42)
    for _ in range(200):
        x = random.randint(0, 10**30)
        y = random.randint(0, 10**30)
        assert int(blocks_to_str(add(str_to_blocks(str(x)), str_to_blocks(str(y))))) == x + y
        if x >= y:
            assert int(blocks_to_str(sub(str_to_blocks(str(x)), str_to_blocks(str(y))))) == x - y
        assert int(blocks_to_str(mul(str_to_blocks(str(x)), str_to_blocks(str(y))))) == x * y
    # Python 内建大整数直接可用（竞赛常用）
    a = 10**500
    assert (a * a) == 10**1000
    assert len(str(2**1000)) == 302
    print("big-integer OK")


if __name__ == "__main__":
    main()

易错点

• Python 中 int(1e20) 是把 float 转 int，1e20 已超 float 精确表示范围，大数请用字符串/十进制字面量
• // 与 % 对负数语义是向下取整，需商向零取整的场合要自己调整
• C++ 手写高精度：反转存储（低位在前）后所有运算从 a[0] 开始；忘除前导零会输出多 0 或格式错误
• 压位输出必须用 %0{d} 补零（万进制补 4 位），否则 '1 0023' 会输出 '123'
• Python 做 10^5 位级大数乘法仍可能超时，需用 NTT/FFT（如 Python 的 numpy 或手写 NTT）
• 2^1000 之类超大数求十进制位数用 math.log10 会有浮点误差，安全做法是 len(str(x)) 或取整公式

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/bignum/
• CP-Algorithms✓ https://cp-algorithms.com/algebra/big-integer.html
• web✓ https://docs.python.org/3/library/stdtypes.html#numeric-types-int-float-complex