如何理解无除法实现2^32-1模运算的等效伪代码原理

推导逻辑 #

首先我们先明确前提：0 ≤ a < b²，所以可以把a按b进制拆分为两位：
a = q * b + r，其中商q = a // b，余数r = a % b，且满足0 ≤ q < b、0 ≤ r < b。

我们要计算的目标是a mod (b-1)和a // (b-1)，这里可以利用模运算的核心性质：

b ≡ 1 mod (b-1)，因此b的任意正整数次幂模b-1都等于1

基于这个性质可以直接得到同余关系：
a = q*b + r ≡ q*1 + r = q + r mod (b-1)

接下来我们对应伪代码逐行验证：

1. 第一行c = (a // b) % b：因为a < b²，a//b就是拆分得到的q，本身就小于b，所以这行等价于c = q。
2. 第二行x = (a + c) % b：代入a = q*b + r、c=q，可得a + c = q*b + r + q，模b后q*b项直接消去，得到x = (q + r) % b。

接下来分两种情况讨论：

情况1：q + r < b

此时x = q + r，显然x = q + r ≥ q = c，所以if (x < c)条件不触发。

• 最终x = q + r，因为q + r < b且限定a mod (b-1) ≠ 0，所以x就是a mod (b-1)
• 最终c = q，代入a = q*(b-1) + (q + r)，因为q + r ≤ b-1，所以商就是q，和a // (b-1)一致。

情况2：q + r ≥ b

此时x = (q + r) - b，显然x = q + (r - b) < q = c，if条件触发，x和c各加1：

• 最终x = (q + r - b) + 1 = q + r - (b - 1)，因为q + r < 2b，所以x < (2b) - (b-1) = b+1，又因为a mod (b-1) ≠ 0，所以x正好是a mod (b-1)
• 最终c = q + 1，代入a = q*(b-1) + (q + r) = q*(b-1) + (b-1) + (q + r - (b-1)) = (q+1)*(b-1) + x，所以商就是q+1，和a // (b-1)一致。

这类简化方案的推导思路 #

这类优化本质上是利用模数的特殊结构：

• 只要模数是b^k - 1的形式，就可以利用b ≡ 1 mod (b-1)的性质，将模运算转化为b进制下的数位求和操作
• 当输入的数值范围限定在[0, b^{2k})时，数位求和最多只会产生1次进位，不需要循环，一次运算就能得到结果
• 你遇到的2^32 -1就是b=2^32、k=1的特殊情况，刚好匹配CMWC算法中a < 2^64 = b²的输入范围，所以可以用无循环实现。

内容的提问来源于stack exchange，提问作者Curious