Multiplication algorithm for abritrary precision (bignum) integers.
- by nn
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
