CPythonmath.integer模块全解析整数精确数学运算comb、perm、factorial、gcd、lcm、isqrt【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpythonmath.integer是 CPython 提供的整数专用数学子模块Python 3.15 起加入将原先散落在math模块中的面向整数参数数学函数收敛到独立命名空间所有结果精确计算且一律返回int。本文从官方文档Doc/library/math.integer.rst出发结合 Modules/mathintegermodule.c 与 Lib/test/test_math_integer.py 的源码实现系统讲解六个函数的数学语义、参数协议、边界行为与底层算法。读完后你将能正确使用这些函数处理大整数组合计数、数论计算与整数开方并理解它们为何对浮点数报错、如何规避实现相关的大数上限。模块定位为什么需要整数专用的math.integermath模块长期以来同时承载两类数学函数面向浮点数的如sqrt、sin、exp与面向整数的如comb、factorial、gcd。math.integer在 Python 3.15 被引入文档标注versionadded:: 3.15其设计意图非常明确This module provides access to the mathematical functions defined for integer arguments.这些函数接受整数以及任何实现了__index__方法的对象对象会先通过__index__被转换为整数再参与运算所有返回值均被精确计算且类型为int。值得强调的是它并不是一个新发明的功能集而是把 CPython 中现有的整数数学运算重新归位到语义更清晰的命名空间。从 Modules/mathmodule.c 的模块初始化代码math_exec可以看出二者的关系底层真正实现位于以_math_integer名字编译的内建扩展在 Modules/Setup.stdlib.in 中通过MODULE__MATH_INTEGER_TRUE_math_integer mathintegermodule.c注册模块加载时math会导入_math_integer把comb、factorial、gcd、isqrt、lcm、perm同时暴露到顶层math命名空间保证向后兼容把同一模块对象注册到sys.modules[math.integer]并挂载为math的属性integer。因此math.factorial与math.integer.factorial指向的是同一个底层 C 函数行为完全一致math.integer只是它们更正式的归属地。快速上手三种等价访问方式由于math在初始化时已把math.integer注册进sys.modules并挂为自身属性以下三种写法等价# 方式一直接导入子模块推荐 import math.integer as mi mi.comb(10, 3) # 120 # 方式二通过 math 的属性访问 import math math.integer.perm(5, 2) # 20 math.integer.factorial(5) # 120 # 方式三顶层 math 命名空间中的同名函数向后兼容 math.comb(10, 3) # 120 math.gcd(48, 180) # 12需要注意子模块机制的一个细节import math.integer会先触发math的初始化而math的初始化过程本身又会加载math.integer并写入sys.modules因此二者总能互相引用成功。从 mathintegermodule.c 的math_integer_exec还能看到模块在初始化时会修正自身的__name__为math.integer并确保每个公开函数的__module__属性也被修正为math.integer——这正是 Lib/test/test_math_integer.py 中MiscTests所断言的内容。获取方式与适用前提该模块属于 CPython 标准库的内置实现无需额外安装首次引入于 Python 3.15按当前仓库 Doc/library/math.integer.rst 的版本标注低于该版本的解释器请回退使用math.comb、math.factorial、math.gcd、math.lcm、math.isqrt、math.perm等既有入口当前仓库 checkout 的版本头为 3.16.0a0见 Include/patchlevel.h即位于主分支的开发快照模块行为以本文所述为准。六个函数数学语义、公式与示例comb(n, k, /)—— 组合数二项式系数返回从n个不同元素中无序、不重复地选取k个元素的方式总数当k n时comb(n, k) n! / (k! * (n - k)!)当k n时返回0由于等价于多项式展开(1 x)ⁿ中第k项的系数故又称二项式系数任一参数为负数时抛出ValueError。import math.integer as mi mi.comb(10, 3) # 120 mi.comb(10, 0) # 1空集 mi.comb(10, 10) # 1全选 mi.comb(10, 11) # 0k n mi.comb(100, 50) # 100891344545564193334812497256精确的大整数对称性comb(n, k) comb(n, n - k)在数学上成立测试文件中也专门做了验证test_math_integer.py。perm(n, kNone, /)—— 排列数返回从n个不同元素中有序、不重复地选取k个元素的方式总数当k n时perm(n, k) n! / (n - k)!当k n时返回0若省略k或显式传None则k默认为n函数返回n!任一参数为负数时抛出ValueError。import math.integer as mi mi.perm(5, 2) # 20 5! / 3! mi.perm(10, 3) # 720 mi.perm(5) # 120 5!k 缺省时为 n! mi.perm(5, None) # 120与上等价 mi.perm(5, 6) # 0k n排列恒等式perm(n, k) perm(n-1, k-1) * k perm(n-1, k)与perm(n, k) n! / (n-k)!都被测试用于交叉验证test_math_integer.py。factorial(n, /)—— 阶乘返回非负整数n的阶乘import math.integer as mi mi.factorial(0) # 1 mi.factorial(5) # 120 mi.factorial(20) # 2432902008176640000 mi.factorial(100) # 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000负整数抛出ValueError错误信息为factorial() not defined for negative values非整数浮点、Decimal、Fraction、字符串抛出TypeError实现上限在当前 CPython 实现中参数需能放入 C 的long超大会抛出OverflowError如factorial(10**100)。测试注释明确说明这是实现细节其他实现可能设置不同的上限见 test_math_integer.py。gcd(*integers)—— 最大公约数返回所有参数的最大公约数接受可变数量的参数只要存在一个非零参数返回值就是能整除所有参数的最大正整数若所有参数全为0返回0不传任何参数时返回0。import math.integer as mi mi.gcd(48, 180) # 12 mi.gcd(120, 84, 30) # 6 mi.gcd(0, 0) # 0 mi.gcd() # 0 mi.gcd(-23, 15) # 1负数参数按绝对值参与运算负数会参与符号处理但不影响结果的非负性。从 mathintegermodule.c 的实现看单参数调用gcd(n)会返回该参数的绝对值如gcd(-12)得12这是源码行为文档未单独强调。lcm(*integers)—— 最小公倍数返回所有参数的最小公倍数若所有参数非零返回值是能被所有参数整除的最小正整数若任一参数为0返回0不传任何参数时返回1。import math.integer as mi mi.lcm(4, 6) # 12 mi.lcm(120, 84, 102) # 14280 mi.lcm(4, 0, 6) # 0含 0 即整体为 0 mi.lcm() # 1 mi.lcm(-23, 15) # 345负数按绝对值处理单参数调用lcm(n)同样返回其绝对值。测试用性质lcm(a, b) a*b/gcd(a, b)进行了大量大数验证test_math_integer.py。isqrt(n, /)—— 整数平方根返回非负整数n的整数平方根即精确平方根向下取整的结果等价于满足a² ≤ n的最大整数aimport math.integer as mi mi.isqrt(16) # 4 mi.isqrt(17) # 417 的平方根约 4.12向下取整为 4 mi.isqrt(15) # 3 mi.isqrt(0) # 0 mi.isqrt(10**100) # 大整数开方同样精确若某些应用需要精确平方根的上取整即满足n ≤ a²的最小整数a文档给出了便捷公式对正n用a 1 isqrt(n - 1)计算import math.integer as mi def isqrt_ceil(n): 返回满足 n a*a 的最小整数 an 0 return 1 mi.isqrt(n - 1) isqrt_ceil(16) # 4因为 16 恰为完全平方 isqrt_ceil(17) # 5因为 4*416 17 255*5负数输入会抛出ValueError错误信息为isqrt() argument must be nonnegative浮点数等非整数抛TypeError。测试通过s*s value (s1)*(s1)的不等式性质对从3**9999、10**5001到2**sizesize达2**32级别的海量样本做了正确性验证test_math_integer.py。参数协议只接受int与实现__index__的对象math.integer的所有函数都遵循同一条类型规则浮点数、Decimal、Fraction、字符串一律不接受因为它们不提供把自身无损转换为整数的__index__协议。import math.integer as mi from decimal import Decimal from fractions import Fraction mi.factorial(5.0) # TypeError: float object cannot be interpreted as an integer mi.gcd(120.0, 84) # TypeError mi.lcm(120, Decimal(84)) # TypeError mi.isqrt(16) # TypeError mi.factorial(5) # TypeError接受的对象包括普通int与boolbool是int的子类factorial(True)即factorial(1)得1comb(True, False)即comb(1, 0)得1int的子类如自定义的IntSubclass调用前会先无损转换为精确的int任何实现了__index__方法的对象如numpy的整数标量、自定义下标类型调用时先通过__index__得到整数再参与运算。测试中定义了一个巧妙的MyIndexable仅实现__index__和一个BadIntSubclass把所有算术与比较运算符都覆写为返回 42 的破坏性实现来验证核心契约实现必须用__index__把参数转换为精确int绝不能误用被覆写的算术运算符。例如isqrt(BadIntSubclass(10**20))仍必须返回10**10而非 42test_math_integer.py、test_math_integer.py。返回值类型一定是精确的int而非传入的int子类。错误与边界语义速查表下表汇总了六个函数的完整边界行为依据文档与 mathintegermodule.c 的实现及测试函数空参调用含 0 的边界负参数非整数参数k n超大参数当前 CPython 实现comb(n, k, /)参数缺失 →TypeErrorcomb(n, 0) 1ValueErrorTypeError返回0中间量超 Clong long→OverflowErrorperm(n, kNone, /)参数缺失 →TypeErrorperm(n, 0) 1perm(0, 0) 1ValueErrorTypeError返回0k超LLONG_MAX→OverflowErrorfactorial(n, /)参数缺失 →TypeErrorfactorial(0) 1ValueErrorTypeError—超 Clong上限 →OverflowErrorgcd(*integers)返回0gcd(0, 0) 0gcd(n, 0) abs(n)正常结果恒为非负TypeError—无特殊上限大整数直接精确计算lcm(*integers)返回1任一为 0 → 返回0正常结果恒为非负TypeError—无特殊上限isqrt(n, /)参数缺失 →TypeErrorisqrt(0) 0ValueErrorTypeError—无特殊上限超大整数开方是主要用途之一需要提醒上表中OverflowError一栏属于当前 CPython 源码实现的工程约束为了走 C 标量快速路径而对输入规模设限测试注释亦写明其他实现可能设定不同上限跨实现开发时应避免依赖这一行为。源码深潜CPython 如何精确高效地完成这些计算所有函数都宣称结果精确其背后是大量针对大整数的工程优化。实现全部位于 Modules/mathintegermodule.c约 1297 行方法表见文件末尾的 math_integer_methods。函数签名的解析由 Argument Clinic 生成代码位于 Modules/clinic/mathintegermodule.c.h。factorial二分拆分binary split 2-进赋值分解factorial的朴素乘法在输入很大时是二次复杂度的CPython 采用 Peter Luschny 的 binary split 思路mathintegermodule.c把n!写成odd_part * 2**two_valuation的形式即拆成奇数部分与2 的幂次two_valuation n//2 n//4 n//8 ...可化简为n - popcount(n)n的二进制中1的个数奇数部分factorial_odd_part(n)通过公式∏ᵢ∏_{0j≤n/2ⁱ, j 为奇数} j分层相乘其中相邻奇数区间用递归的factorial_partial_product计算大数乘法充分复用底层的高效乘法Karatsuba 等最后result odd_part two_valuation一次左移收尾。小输入直接查表SmallFactorials[]预存了0!到20!64 位平台mathintegermodule.c 中x 20时一次查表返回避免任何乘法。gcd/lcm变参折叠与短路快路径gcd的实现mathintegermodule.c包含三个值得注意的点两个参数且都是精确int时直接调用内部_PyLong_GCD避免多余的对象转换迭代累加过程中一旦当前结果已经是1后续参数不再真正做 GCD仅做类型检查后直接跳过gcd(1, 任意值)结果必然为 1每个参数通过PyNumber_Index转换因而天然支持__index__类型并拒绝浮点数。lcm借助恒等式lcm(a, b) abs(a // gcd(a, b) * b)实现见 long_lcm任一参数为 0 时立即返回 0迭代中一旦结果为 0 也走短路快路径。isqrt自适应精度的纯整数牛顿迭代isqrt是全模块算法注释最详尽的部分mathintegermodule.c采用自适应精度的纯整数牛顿迭代还附有完整正确性证明概要其正确性另有用 Lean 形式化验证的证明。要点对n 2**64的输入走几乎无分支的快速路径先用 192 项的 16 位近似开方查表_approximate_isqrt_tabmathintegermodule.c得到起点再用两次定点除法修正到误差 1 以内最后用u - (u*u m)一次纠偏对n 2**64的大整数先用 C 整数算术完成前五次迭代再切换到PyLong大整数完成剩余迭代每次迭代把当前区间折半逼近循环次数事先已知约为floor(log2(log2(n)))收尾时比较a*a与n决定答案是a还是a-1mathintegermodule.c比较特意走PyLong_Type的类型级比较以规避 int 子类覆写运算符的干扰。comb/perm查表快路径 分治递归排列组合的实现mathintegermodule.c是性能工程的重点结果可放入 64 位时借助三张预计算表reduced_factorial_odd_part、inverted_factorial_odd_part、factorial_trailing_zeros见 mathintegermodule.c通过两次 64 位乘法模运算直接拼出comb_odd_part shift更大但仍可控时用递推C(n,k) C(n,k-1) * (n-k1) / k一次计算大数路径采用分治递归C(n,k) C(n,j) * C(n-j, k-j) // C(k,j)其中j k//2让乘法集中在规模相近的大整数上最大化 Karatsuba 乘法收益comb会先利用对称性取k min(k, n-k)来缩小递归规模mathintegermodule.c。双命名空间设计与自由线程兼容从模块定义mathintegermodule.c可以看出该模块对现代解释器特性的适配static PyModuleDef_Slot math_integer_slots[] { _Py_ABI_SLOT, {Py_mod_exec, math_integer_exec}, {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED}, {Py_mod_gil, Py_MOD_GIL_NOT_USED}, {0, NULL} };从源码结构可以推断该模块声明了子解释器兼容per-interpreter GIL 支持与自由线程free-threadingGIL_NOT_USED兼容属于无状态纯函数模块天然线程安全。测试方面test_math_integer.py 把IntMathTests定义为对math.integer的测试基类随后 MathTests 直接继承它并把被测对象切换成math模块——一套用例同时回归两个命名空间验证二者底层实现一致。测试与正确性验证手段一览Lib/test/test_math_integer.py共 421 行为每个函数的正确性提供了多种独立验证手段值得作为你使用时的行为参考验证手段覆盖点定义恒等式comb(n,k) n!/(k!(n-k)!)、perm(n,k) n!/(n-k)!用factorial交叉验证comb/permn 达 499Pascal 恒等式C(n,k) C(n-1,k-1) C(n-1,k)P(n,k) P(n-1,k-1)·k P(n-1,k)递推结构一致性对称性comb(n,k) comb(n,n-k)参数约减正确性纯 Python 参考实现py_factorial与 C 实现的 factorial 逐点对拍不等式s*s n (s1)*(s1)isqrt语义定义bigmemtest传入2**32规模位长的整数isqrt大整数路径与内存边界BadIntSubclass运算符全部被覆写为返回 42确认实现经__index__无损转换、不触碰子类算术负值、浮点、Decimal、Fraction、字符串的异常断言类型协议与错误语义典型应用场景以下应用与文档语义及实现事实直接对应可作为实战参考组合计数与概率统计comb(n, k)直接给出无序选取数perm(n, k)给出有序排列数例如计算抽奖组合数、棋盘路径数、多项式展开系数文档明确指出comb等价于(1x)ⁿ展开的第k项系数。数论与分数化简gcd/lcm支持变参可一次求出多整数的最大公约数/最小公倍数用于大整数分数约分、周期问题如多进程调度周期取lcm。lcm(a, b) abs(a*b) // gcd(a, b)的关系可用于互相校验。大整数开方与判定isqrt可判定完全平方数isqrt(n)**2 n配合文档给出的上取整公式1 isqrt(n - 1)可处理密钥学/密码学中常见的需要大于等于某个平方数的下一整数这类需求也常作为无需浮点误差的近似开方手段。阶乘类组合公式factorial可直接支撑nPr/nCr之外的双阶乘、级数求和等推导返回值精确且为int不存在浮点精度损失。参考资源官方 API 文档Doc/library/math.integer.rst底层 C 实现Modules/mathintegermodule.cArgument Clinic 生成头文件Modules/clinic/mathintegermodule.c.hmath模块挂载math.integer的初始化代码Modules/mathmodule.c构建注册_math_integer扩展Modules/Setup.stdlib.in完整测试套件Lib/test/test_math_integer.py【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpython创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
