优化Knuth长除法算法中的移位操作——Bignum模运算性能提升

核心思路 #

当前operator%=实现中，每次循环仅对r右移1位，在RSA等场景下，第一次减法后*this的有效位数会大幅下降，后续大量右移操作完全无效。我们可以通过计算r需要批量右移的位数x，直接跳过这些无效循环，提升运算效率。

批量右移位数x的计算方法 #

当*this < r时，通过两者的有效位数差值快速确定最大可右移的位数：

1. 获取当前*this的有效位数：bits_this = this->SignificantBits()
2. 获取当前r的有效位数：bits_r = r.SignificantBits()
3. 计算理论最大右移位数：x = bits_r - bits_this
   • 若x <= 0：说明两者有效位数相同或r更小，只能右移1位（避免跳过可能的减法操作）
   • 若x > n：受限于循环边界n >= 0，取x = n（确保右移后n - x >= 0）
   • 最终x = max(1, min(x, n))，保证至少右移1位，且不超出循环范围

修改后的代码实现 #

#include <algorithm> // 用于std::max和std::min

uint32_t Bignum::SignificantBits() const
{
    return (v.size() == 0) ? 0 : (32 * v.size() - __builtin_clz(v[0]));
}

Bignum& Bignum::operator%=(const Bignum &rhs)
{
    // 假设*this > rhs，边界/退化情况已处理
    int n = SignificantBits() - rhs.SignificantBits();
    Bignum r(rhs);
    r <<= n;

    while (n >= 0)
    {
        if (*this >= r)
        {
            *this -= r;
        }

        if (n == 0)
        {
            break;
        }

        uint32_t bits_this = this->SignificantBits();
        uint32_t bits_r = r.SignificantBits();
        int x = bits_r - bits_this;

        // 确保x合法：至少右移1位，且不超过当前n
        x = std::max(1, std::min(x, n));
        n -= x;
        r >>= x;
    }

    return *this;
}

效果说明 #

在RSA场景下，第一次减法后*this的有效位数下降约15位，此时bits_r - bits_this ≈15，代码会一次性将r右移15位，直接跳过15次无效循环，大幅减少>>=操作的执行次数，提升模运算效率。

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