Ben - 3 months ago 24
C Question

# multiplication of large numbers, how to catch overflow

I am looking for an efficient (optionally standard, elegant and easy to implement) solution to multiply relatively large numbers,and store the result into one or several integers :

Let say I have two 64 bits integers declared like this :

``````uint64_t a = xxx, b = yyy;
``````

When I do
`a*b`
, how can I detect if the operation result in an overflow and in this case store the carry somewhere ?

Please note that I don't want to use any large-number library since I have constraints on the way I store the numbers.

Thanks

Detection:

``````x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
``````

Edit: Fixed division by 0 (thanks Mark!)

Computing the carry is quite involved. One approach is to split both operands into half-words, then apply long multiplication to the half-words:

``````uint64_t hi(uint64_t x) {
return x >> 32;
}

uint64_t lo(uint64_t x) {
return ((1L << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
// actually uint32_t would do, but the casting is annoying
uint64_t s0, s1, s2, s3;

uint64_t x = lo(a) * lo(b);
s0 = lo(x);

x = hi(a) * lo(b) + hi(x);
s1 = lo(x);
s2 = hi(x);

x = s1 + lo(a) * hi(b);
s1 = lo(x);

x = s2 + hi(a) * hi(b) + hi(x);
s2 = lo(x);
s3 = hi(x);

uint64_t result = s1 << 32 | s0;
uint64_t carry = s3 << 32 | s2;
}
``````

To see that none of the partial sums themselves can overflow, we consider the worst case:

``````        x = s2 + hi(a) * hi(b) + hi(x)
``````

Let B = 1 << 32. We then have

``````            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
<= B*B - 1
< B*B
``````

I believe this will work - at least it handles Sjlver's test case. Aside from that, it is untested (and might not even compile, as I don't have a C++ compiler at hand anymore).