Long Multiply C

Question

I'm trying to implement the long multiply method (grade school method) in C. I need to write my program in base 2^32. I'm not sure how to even start. I have the algorithm that I want to use here:

for (i = 0; i < n; i++) {
   carry = 0;
   for (j = 0; j < n; j++) {
      product = a[i] * b[j] + result[i + j] + carry;
      result[i + j] = p % base;
      carry = floor(product / base);
   }
   result[i + n] = carry;
}

Any hints are appreciated. I just can't come up with a good idea.

Answer 1

The main "trick" is to find a way to multiple two 32-bit numbers and get either a 64-bit number or two 32-bit numbers which are the high- and low-halves. The high-half is the carry, and the low-half is the result (mode 2^32). On x86 machines there is an assembly language instruction that does exactly that, but to do it in straight C/C++ you will need to cast the multiplicands to some 64-bit type before multiplying, and then use shifts and masks to separate the high- and low-halves.