Multiplication algorithm for integers abritrary precision (bignum)

Question

I am writing a small bignum library for a homework project. I have to implement Karatsuba multiplication, but before that I would like to write a naive multiplication program.

I am following a manual written by Paul Zimmermann entitled Modern Computer Arithmetic, which is freely available on the Internet .

Page 4 provides a description of an algorithm called BasecaseMultiply that performs multiplication by classes.

I understand step 2, 3, where B ^ j is the shift of digits by 1, j times. But I do not understand steps 1 and 3, where we have A * b_j. How should this multiplication be performed if binomial multiplication is not yet defined?

Will the operation "*" in this algorithm be just a re-add method?

Here are the parts that I have written so far. I have a module that tested them so that they look correct for the most part:

The structure that I use for my bonus is as follows:

#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;

Currently Available Procedures:

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

I wrote a multiplication algorithm some time ago, and I have this comment at the top. If you have two numbers x and y of the same size (the same n_digits), you would multiply so as to get n, which would be twice as many digits. Part of the complexity of the algorithm comes from developing which bits will not be multiplied if n_digits is not the same for both inputs.

, n0 x0 * y0, . n1 ​​- x1 * y0 y1 * x0, . 32- 64- , , n0 = low32 (x0 * y0), high32 (x0 * y0) . , 32- , , 64 , , , 30 31 .

30 , , . , n_digits 8 . , n_digits shift add, 8x8 .

/*
    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
*/

Answer 2

A * b_j, . :

bn *R = ZERO;
for(int i = 0; i < n; i++) {
  bn S = {0, 2};
  S.digits[0] = a[i] * b_j;
  S.digits[1] = (((u_w)a[i]) * b_j) >> 32;  // order depends on endianness
  bn_lshift(S, i);
  R = bn_add(R, S);
}

, .