Knuth Arithmetic Algorithm

大整数的四则运算的经典算法：

1. n位整数的加法或者减法，给出一个n位整数的答案和一个进位
2. n位整数和m位整数的乘法，给出一个（m+n）位的答案
3. （m+n）位整数除以n位整数，给出（m+1）位的商和n位的余数

记(Un-1Un-2…U0)b是为b进制下，每个位为Ui，i >= 0 &&i <= n-1的大整数。

加法算法

给定非负整数(Un-1Un-2…U0)b和(Vn-1Vn-2…V0)b，算法结果为一个b的进制整数和(WnWn-1…W0)b，这里Wn是进位，总是等于0或者1.

算法流程：

A1. 初始化。置j <- 0, k <- 0, 变量j将跑遍各个数字的位置, 而k记住在每个步骤的进位。
A2. 置Wj <- (Uj + Vj + k ) mod b，k <- (Uj + Vj + k) / b （整数除法）
A3. j <- j + 1，若j < n, 则跳转到A2，否则置Wn <- k.

减法算法

给定非负整数(Un-1Un-2…U0)b >= (Vn-1Vn-2…V0)b, 这个算法形成它们非负b进制的差(Wn-1Wn-2…W0)b.

算法流程：

S1. 初始化. 置 j <- 0, k <- 0
S2. 置Wj <- (Uj - Vj + k) mod b, k <- (Uj - Vj + k) / b, (整数除法).
S3. j <- j + 1, 如果j < n, 则跳转到S2, 否则算法终止.

乘法算法

给定非负整数(Um-1Um-2…U0)b和(Vn-1Vn-2…V0)b, 算法形成它们的b进制乘积(Wm+n-1….W1W0)b.

算法流程：

M1. 初始化, 置Wm-1, Wm-2, ..., W0为0，j <- 0.
M2. 如果Vj = 0, 那么置Wj+m = 0, 并跳转M6
M3. 置 i <- 0, k <- 0
M4. 置 tmp <- Ui * Vj + Wi+j + k, 然后置 Wi+j <- t mod b, k <- t / b (整数除法)
M5. i <- i + 1, 如果i < m, 则跳转M4
M6. j <- j + 1, 如果j < n, 则跳转M2, 否则算法终止.

除法运算

考虑长除法，每一个步骤是(n+1)位被除数u除以n位除数v的除法，每一步之后的余数r小于v，随后的步骤中使用r*b+(被除数的下一位)作为新的u. 那么
问题就简化到对一个非负整数u = (UnUn-1…U0)b和v = (Vn-1Vn-2…V0), 求一个算法以确定q = 下取整(u/v).
这里直接给出定理，证明可以参见《计算机编程艺术》第二卷4.3.1节。
记q’ = min(下取整[(Unb + Un-1) / Vn-1], b - 1).

定理1

q’ >= q

定理2

如果Vn-1 >= 下取整(b/2), 那么q’ - 2 <= q <= q’

定理3

令r’ = (Unb + Un-1 - q’ Vn-1), 假设Vn-1 > 0, 那么如果q’Vn-2 > b r’ + Un-2, 那么 q < q’

定理4

如果q’Vn-2 <= br’ + Un-2, 那么q’ = q或者q = q’ - 1

于是我们有以下算法：
给定非负整数u = (Um+n…U1U0)b和v = (Vn-1..V1V0)b，其中Vn-1 != 0且n > 1. 构造b进制的商为(qmqm-1…q0)b和余数, (rn-1…r1r0)b.

算法流程：

D1. 规格化. 置d <- [b / (Vn-1 + 1)], 然后置u = u * d, v = v * d, 这样做事为了让Vn-1 >= b/2.
D2. 初始化. 置j <- m.
D3. 置q' <- (Uj+n * b + Uj+n-1) / Vn-1, 并令r' = Uj+n * b + Uj+n-1 - q'*Vn-1, 测试q' = b 或者q'Vn-2 > b * r' + Un-2, 如果是，
那么q' <- q' - 1, r' <- r' + Vn-1, 如果r' < b, 则重复上述测试。
D4. 以(Uj+nUj+n-1...Uj)b - q' * (Vn-1Vn-2...V0)b代替(Uj+nUj+n-1...Uj)
D5. qj <- q', 如果D4的结果为负，那么跳转到D6，否则到D7
D6. qj <- qj - 1, 把(0Vn-1Vn-2...V0)b加到(Uj+nUj+n-1...Uj)上
D7. j <- j - 1, 如果j >= 0, 跳转到D3.
D8. (qm...q1q0)即所求的商，余数则可以剩下的(Un-1...U1U0)b除以d得到