Algorithm to multiply 64-bit numbers using 32-bit unsigned integers

2
votes

I have 64-bit numbers (63 bits + sign bit), represented as two's complement numbers, stored in two unsigned 32-bit integers.

struct Long
{
    uint32 high;
    uint32 low;
}

How can I implement a multiplication algorithm, using just 32-bit numbers, and check that the result fits in 63-bits? I want to return an error code indicating overflow if the result doesn't fit.

2
c++calgorithmmultiplication
Most compilers have a long long type which is 64 bits and should work with multiplication. - Pubby
I need the algorithm, assuming there isn't 64 bit support. - José
Wikipedia describes the algorithms that computers use: en.wikipedia.org/wiki/Multiplication_algorithm - Simon C
See also en.wikipedia.org/wiki/Binary_multiplier - Artefacto
It's funny you should ask this, I've been implementing exactly this algorithm today. I am using in-line assembler (in g++ for Intel IA-32), which may not be appropriate for you -- what are your OS and compiler? - TonyK

2 Answers

5
votes

Generally you need 2*n bits to store the product of two n bit numbers (largest result is (2^n)^2 = 2^(2*n)), so my best idea is to split up the number into four 16-bit parts, multiply them one by one and add them together. 16 multiplications all in all, but error checking is trivial.

1
votes

Have a look at the 'longlong.h' header file in the GNU MP library. I believe that a version of this header is also in the GNU C source. The macro: smul_ppmm is defined in terms of the unsigned double-word product: umul_ppmm. This gives you 32x32=>64 bit multiplication, which you might be able to use to implement 64x64=>128 bit multiplication.