Hi,

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

I'm following a guide written by Paul Zimmerman titled "Modern Computer Arithmetic" which is freely available online.

On page 4, there is a description of an algorithm titled BasecaseMultiply which performs gradeschool multiplication.

I understand step 2, 3, where B^j is a digit shift of 1, j times. But I don't understand step 1 and 3, where we have A*b_j. How is this multiplication meant to be carried out if the bignum multiplication hasn't been defined yet?

Would the operation "*" in this algorithm just be the repeated addition method?

Here is the parts I have written thus far. I have unit tested them so they appear to be correct for the most part:

The structure I use for my bignum 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 routines:

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