《算法的乐趣》第五十四节

本节讲解大整数的除法、乘方及常用算法。除法采用试商优化，通过高位组成的64位整数试商并累加，反复减去除数的若干倍，被除数小于除数时即得余数，除法与取模为同一过程……

本节讲解大整数的除法、乘方及常用算法。除法采用试商优化，通过高位组成的64位整数试商并累加，反复减去除数的若干倍，被除数小于除数时即得余数，除法与取模为同一过程；带符号数的商同号为正、异号为负，余数与被除数同号。乘方采用平方-乘降幂法，依据指数的二进制位处理：位为1时累乘临时变量，为0时只对临时变量平方，可将n次乘法减少到约log₂n次；奇次幂符号随底数，偶次幂恒为正。随后介绍大数与字符串的互转，以及最大公约数与最小公倍数的求法：辗转相除法依据GCD(a,b)=GCD(b,a mod b)，Stein算法只用加减和移位以避开低效的大数除法，辗转相减法在两数相差大时收敛慢；最小公倍数可用“两数乘积除以最大公约数”，但乘积需双倍存储空间，也可用自加并整除测试，但两数悬殊时循环漫长。最后引出线性不定方程与贝祖定理，说明扩展欧几里得算法由朴素欧几里得定理的辗转关系推导，用于求解ax+by=gcd(a,b)及模的逆元。