c - 任意精度(bignum)整数的乘法算法

Question

我正在为家庭作业项目编写一个小型 bignum 库。我要实现 Karatsuba 乘法，但在此之前我想编写一个朴素的乘法例程。

我正在遵循 Paul Zimmerman 撰写的题为“现代计算机算术”的指南，即 freely available online .

第 4 页描述了一种名为 BasecaseMultiply 的算法，该算法执行小学乘法。

我理解步骤2、3，其中B^j 是数字移位1, j 次。 但我不明白第 1 步和第 3 步，我们有 A*b_j。如果尚未定义 bignum 乘法，该乘法将如何执行？

这个算法中的“*”操作会不会就是重复加法呢？

这是我到目前为止写的部分。我对它们进行了单元测试，因此它们在大多数情况下看起来都是正确的:

我使用的 bignum 结构如下:

#define BIGNUM_DIGITS 2048
typedef uint32_t u_hw; // halfword
typedef uint64_t u_w; // word

typedef struct {
    unsigned int sign; // 0 or 1
    unsigned int n_digits;
    u_hw digits[BIGNUM_DIGITS];
} bn;

当前可用的例程:

bn *bn_add(bn *a, bn *b); // returns a+b as a newly allocated bn
void bn_lshift(bn *b, int d); // shifts d digits to the left, retains sign
int bn_cmp(bn *a, bn *b); // returns 1 if a>b, 0 if a=b, -1 if a<b

Answer 1

我前段时间写了一个乘法算法，我在顶部有这个评论。如果你有两个相同大小的数字 x 和 y(相同的 n_digits)，那么你将像这样相乘得到 n，这将有两倍的数字。如果两个输入的 n_digits 不同，算法的部分复杂性来自于计算出哪些位不相乘。

从右边开始，n0 是 x0*y0，您可以避免溢出。现在 n1 是 x1*y0 和 y1*x0 的总和，之前的溢出量已按您的数字大小移动。如果您在 64 位数学中使用 32 位数字，这意味着 n0 = low32(x0*y0) 并且您携带 high32(x0*y0) 作为溢出。您可以看到，如果您实际使用 32 位数字，则不能在不超过 64 位的情况下将中心列相加，因此您可能使用 30 或 31 位数字。

如果每个数字有 30 位，这意味着您可以将两个 8 位数字相乘。首先编写此算法以接受两个 n_digits 最多为 8 的小缓冲区，并使用 native 数学进行算术运算。然后再次实现它，采用任意大小的 n_digits 并使用第一个版本，以及您的 shift 和 add 方法，一次乘以 8x8 数字 block 。

/*
    X*Y = N

                          x0     y3
                            \   /  
                             \ /   
                              X    
                      x1     /|\     y2
                        \   / | \   /  
                         \ /  |  \ /   
                          X   |   X    
                  x2     /|\  |  /|\     y1
                    \   / | \ | / | \   /  
                     \ /  |  \|/  |  \ /   
                      X   |   X   |   X    
              x3     /|\  |  /|\  |  /|\     y0
                \   / | \ | / | \ | / | \   /
                 \ /  |  \|/  |  \|/  |  \ /
                  V   |   X   |   X   |   V
                  |\  |  /|\  |  /|\  |  /|
                  | \ | / | \ | / | \ | / |
                  |  \|/  |  \|/  |  \|/  |
                  |   V   |   X   |   V   |
                  |   |\  |  /|\  |  /|   |
                  |   | \ | / | \ | / |   |
                  |   |  \|/  |  \|/  |   |
                  |   |   V   |   V   |   |
                  |   |   |\  |  /|   |   |
                  |   |   | \ | / |   |   |
                  |   |   |  \|/  |   |   |
                  |   |   |   V   |   |   |
                  |   |   |   |   |   |   |
              n7  n6  n5  n4  n3  n2  n1  n0
*/