Knuth 算法 D 中的非标准化

Question

我正在尝试用 Rust 实现 Knuth 的“计算机编程艺术，第 2 卷”中的算法 D，尽管我很难理解如何实现非规范化的最后一步。我的自然数是一个类，其中每个数字都是 u64 的向量，基数为

u64::MAX

。加法、减法和乘法已经实现。

Knuth 算法 D 是一种欧几里得除法算法，它采用两个自然数

x

和

y

并返回

(q,r)

，其中

q = x / y

（整数除法）和

r = x % y

，余数。该算法依赖于一种近似方法，该方法仅在

y

的第一个数字大于

b/2

时才起作用，其中

b

是表示数字的基数。由于并非所有数字都是这种形式，因此它例如，使用“归一化技巧”（如果我们以 10 为基数），而不是执行

200 / 23

，我们计算归一化器

d

并执行

(200 * d) / (23 * d)

，以便

23 * d

的第一个数字大于

 b/2

。

因此，当我们使用近似方法时，我们最终会得到所需的 q，但余数会乘以因子

d

。所以最后一步就是将

r

除以

d

，这样我们就可以得到我们想要的

q

和

r

。我的问题是，我对我们应该如何执行最后一步感到有点困惑，因为它需要除法，而它所属的方法正在尝试实现除法。

（也许有帮助？）： 计算

d

的方法就是将

b-1

的整数下限除以 y 的第一位数字。然而，Knuth 建议，只要 y 的第一位数字大于

d

，就可以将

d *

设为 2 的幂。我认为他提出这个建议是为了我们可以为最后一步进行二进制移位，而不是除法。尽管我认为我无法做到这一点，因为我的数字表示为

b / 2

值的向量，而不是二进制。有什么建议吗？

Answer 1

u64

作为2的幂。您只需要换班：

d

。 然后，您可以移动大整数，而不是乘法和除法。 以下是移位大整数的示例代码：shift = count_leading_zeroes(divisor[divisor.size() - 1])

例如，为简单起见，我们将基数设为 256，并查看两个相邻的“数字”：

// For base = 2^64 and 0 <= shift <= 64
void shift_right_inplace(bint_t& a, int shift) {
    for (int i = 0; i < a.data.size(); i++) {
        const uint64_t self = a.data[i] >> shift;
        const uint64_t prev = i == a.data.size() - 1 ? 0 : a.data[i + 1] << (64 - shift);
        a.data[i] = self | prev;
    }
    if (a.data.back() == 0) {
        a.data.pop_back();
    }
}

和

abcdefgh

。您想将其右移 3。第一个字节左边没有邻居，所以你只需移动它：

klmnopqr

。对于第二个字节，您将其移位 (

000abcde

) 并从前一个字节中取出其余部分 (

000klmno

，它实际上是

abcdefgh >> 3 = 000abcde | fgh

)。