数学算法
数学算法首先要区分精确答案、概率结论与数值近似。整数最大公约数可以精确计算;Miller-Rabin 返回的是在特定条件下的“可能为素数”;浮点求根返回满足某个停止标准的近似值。把三者都写成“计算成功”,会掩盖不同的结果合同。
例如两项周期任务分别每 48、18 分钟执行一次,若从同一时刻启动,下一次共同触发在 144 分钟后。最大公约数为 6,最小公倍数为 48/6×18=144。这里周期为正且相位相同;若启动时间不同,还需要求解同余关系,不能只求最小公倍数。
整数、零值与计算入口
Python 标准库 math.gcd、math.lcm、math.comb、math.perm 提供精确整数入口。用它们可把注意力放在输入与业务模型,避免在零值、负号和中间溢出上重复出错。
python
from math import gcd, lcm, comb, perm
assert gcd(48, 18) == 6
assert lcm(48, 18) == 144
assert gcd(-48, 18) == 6
assert gcd(0, 0) == 0
assert lcm(0, 0) == 0
assert comb(10, 3) == 120
assert perm(10, 3) == 720
print(lcm(48, 18))辗转相除依据 gcd(a,b)=gcd(b,a mod b),反复把非零余数作为下一轮除数,直到余数为 0,最终取非负结果。最大公约数计算的除法轮数为 O(log min(|a|,|b|)),但大整数除法不是固定时间,零值也应单独约定。
计算最小公倍数时,可先除公约数再乘,减少固定宽度整数的中间溢出风险;两数都为零时必须先返回 0,不能执行 abs(a*b)//gcd(a,b)。Python 整数没有固定宽度溢出,也不代表数值无限大时没有时间和内存成本。
模幂:指数减半,保持同余不变量
计算 3**13 % 17 不必先构造完整的幂。维护 result、base 和剩余指数 e,每次看 e 的最低位:为 1 就把 base 乘入 result,然后 base 平方、e 整除 2。整个过程保持 result × base**e 与原目标模 m 同余。
以下 Python 3 完整程序限定整数底数、非负整数指数、正整数模数;拒绝布尔值。指数为 0、模数为 1 时结果是 1 % 1 = 0,不能无条件返回 1。本例约定 0 的 0 次方按整数幂合同取 1,再做取模。
python
def modular_power(base, exponent, modulus):
if type(base) is not int:
raise ValueError("底数必须是整数")
if type(exponent) is not int or exponent < 0:
raise ValueError("指数必须是非负整数")
if type(modulus) is not int or modulus <= 0:
raise ValueError("模数必须是正整数")
result = 1 % modulus
base %= modulus
while exponent:
if exponent & 1:
result = result * base % modulus
base = base * base % modulus
exponent //= 2
return result
def modular_inverse(value, modulus):
if type(value) is not int or type(modulus) is not int or modulus <= 1:
raise ValueError("逆元要求整数与大于1的模数")
return pow(value, -1, modulus)
assert modular_power(3, 13, 17) == 12
assert modular_power(0, 0, 1) == 0
assert modular_power(-3, 3, 7) == 1
assert modular_inverse(3, 11) == 4
assert 3 * modular_inverse(3, 11) % 11 == 1
print(modular_power(3, 13, 17))循环次数为 O(log e),每轮执行有限次模乘;实际位复杂度取决于模数长度及乘除法实现,不能把一次大整数模乘当作恒定机器指令。工程中优先使用内置 pow(base, exponent, modulus),无需手写循环。
逆元 a⁻¹ 满足 a×a⁻¹ mod m = 1,仅在 gcd(a,m)=1 时存在。示例调用标准库 pow(a,-1,m),不存在时抛 ValueError;例如 6 与 9 不互素,不能返回一个伪结果。费马小定理的 a**(p-2) mod p 还要求 p 为素数、a 不被 p 整除,不能推广到任意模数。
上述实现用于理解整数运算,不是密码系统。它没有承诺恒定时间、密钥管理或安全填充;真实加密签名应使用成熟密码库及协议,不能把小素数的裸 RSA 演示作为应用加密方案。
素数与组合计数的边界
| 模型 | 机制 | 输入与结论限制 |
|---|---|---|
| 试除判断素数 | 排除 2 之后,只检查到整数平方根 | n<2 不是素数;使用整数平方根,避免大整数转浮点丢精度 |
| 埃氏筛 | 从素数 p 的 p² 起标记倍数 | 生成到 N 的表约需 O(N)空间,时间 O(N log log N) |
| 分段筛 | 用不超过 √high 的素数标记区间 | 先验证区间、处理 0/1,内存与段宽相关,不是与 high 无关 |
| Miller-Rabin | 检查若干底数是否为合数见证 | 对奇合数,独立均匀选底数的 k 轮误判上界为 4⁻ᵏ,非“误差恰为4⁻ᵏ” |
| 排列 P(n,r) | 选择 r 个不同对象且区分顺序 | n、r 非负整数;通常 r>n 返回0;对象可重复时模型不同 |
| 组合 C(n,r) | 选择 r 个不同对象不区分顺序 | 编号对象与重复值是否视作相同必须明确 |
| Catalan 数 | 按根位置拆分合法递归结构 | n对合法括号、n个不同键的BST形状等均需对应模型,负n非法 |
Miller-Rabin 的底数取样前提决定概率界;固定一套底数只有在明确整数范围及已证明的底数集合下,才能称为该范围内确定性测试。轮数为 0 不应自动视为素数,普通伪随机生成器也不适合生成密码密钥。
组合计数可远超 64 位范围。计算“结果再取模”与“把除法直接改成模除法”不同;分母在模数下可能不可逆。业务中有库存上限、互斥或重复对象时,也不一定能套 comb(n,r),可转向动态规划或回溯。
随机模拟:可复现不等于精确
抽样模拟建议使用独立的 random.Random(seed),避免设置全局种子影响其他组件;安全令牌使用 secrets 等安全随机入口。分布参数也有边界:泊松 λ=0 应恒为0,几何分布 p=1 应恒为1,二项分布需 n为非负整数且 p∈[0,1]。
直接连乘均匀随机数的泊松采样适用于较小 λ,λ很大时 exp(-λ) 下溢且计算成本增大,应使用成熟分布实现。不能只在 λ=3 的样例能运行,就称为任意参数生成器。
蒙特卡罗积分在 [a,b] 均匀抽样,把函数值平均再乘区间长度。样本量必须为正,输出是随机估计;常见有限方差条件下,标准误差按 O(1/√N) 缩小,误差缩小十倍通常需要约百倍样本。固定种子便于复现,不能消除偏差、相关性或置信区间的问题。
π估计、积分和概率模拟应同时说明样本量、估计值与误差口径。零命中不能随意返回0作为π的估计;这表示该估计公式无法得到有效结果。布丰投针的常见公式还有针长不超过平行线间距等前提。
数值计算:明确停止理由
二分求根要求函数在区间连续,端点异号或端点本身为根。每轮保留仍包住根的半区间,区间宽度给出位置误差的控制;若只比较函数值接近0,函数缩放可能让它很小却离根很远。
实现应缓存端点值,先处理端点根,再检查有限值、容差、最大迭代次数与中点无法继续移动的情况。用 func(a)*func(b) 判断符号还可能溢出或下溢,直接比较符号更明确。迭代耗尽需返回未收敛状态或异常,不能把最后一次结果无条件称为根。
牛顿法用局部切线更新,初值、导数接近0和函数性质都会影响收敛;步长很小也可能是数值停滞。工程中可评估 scipy.optimize.root_scalar 等带收敛信息的入口,并结合残差、位置容差与业务范围验收。
数值积分的梯形与 Simpson 方法依赖平滑性和步长。复合 Simpson 通常要求正偶数分段;自适应算法必须有递归/评估次数上限与未收敛报告,不能任意递归到浮点不再细分。奇异点、强振荡和不连续区间需要分段或专门方法,单次相邻网格差值不是对所有函数的严格误差保证。
线性代数与几何的工程判断
求 Ax=b 时优先解线性方程组,不先显式求逆再乘。使用 NumPy/SciPy 等成熟实现,校验方阵、维度、有限值和奇异性;残差小只说明方程满足得好,病态矩阵仍可能使解对输入扰动敏感。行列式接近0也不能用一个固定绝对阈值适配所有尺度。
高斯消元需要主元选择和零/近零主元处理;无解与无穷多解应区分,不能略过零主元后在回代中除零。矩阵对象还应拒绝不规则行,明确是否复制输入,避免外部修改悄悄改变计算。
几何算法中,共线、重复点和精度影响方向判断。Graham扫描按极角排序时还需处理同角点距离及去重;最近点对的两份排序必须按同一批点身份划分,不能只按中点x坐标拆分。相关分解机制见分治算法,实际几何处理优先使用成熟库。
验证方法
整数算法用代数恒等式与标准库对照:gcd应整除输入,逆元需乘回1,模幂与pow一致。覆盖零、负数、模数1、零指数、无逆元及大整数,检查异常合同。
数值算法则记录输入尺度、容差、残差、迭代次数和停止原因,用已知解析解或高精度基准对照,并加入奇异、不连续、不收敛案例。随机算法还需独立重复实验,不能把一次固定种子样例当作统计正确性证明。
