multiplication of large numbers, how to catch overflow

Question

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 what the use any large-number library since I have constraints on the way I store the numbers.

Thanks

Answer 1

Detection:

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

Edit: Fixed division by 0 (thanks Mark!)

Carry:

uint64_t carry = hi(a) * hi(b) + hi(hi(a) * lo(b)) + hi(lo(a) * hi(b));

where

hi(x) = x >> 32;
lo(x) = ((1 << 32) - 1) & x;

Acknowledgement: Idea gleaned from the implementation of java.math.BigDecimal

Answer 2

A version that also works when a == 0:

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

Answer 3

The idea is to use following fact which is true for integral operation:

a*b > c if and only if a > c/b

/ is integral division here.

The pseudocode to check against overflow for positive numbers follows:

if (a > max_int64 / b) then "overflow" else "ok".

To handle zeroes and negative numbers you should add more checks.

C code for non-negative a and b follows:

if (b > 0 && a > 18446744073709551615 / b) {
     // overflow handling
}; else {
    c = a * b;
}

Note:

18446744073709551615 == (1<<64)-1

To calculate carry we can use approach to split number into two 32-digits and multiply them as we do this on the paper. We need to split numbers to avoid overflow.

Code follows:

// split input numbers into 32-bit digits
uint64_t a0 = a & ((1LL<<32)-1);
uint64_t a1 = a >> 32;
uint64_t b0 = b & ((1LL<<32)-1);
uint64_t b1 = b >> 32;


// The following 3 lines of code is to calculate the carry of d1
// (d1 - 32-bit second digit of result, and it can be calculated as d1=d11+d12),
// but to avoid overflow.
// Actually rewriting the following 2 lines:
// uint64_t d1 = (a0 * b0 >> 32) + a1 * b0 + a0 * b1;
// uint64_t c1 = d1 >> 32;
uint64_t d11 = a1 * b0 + (a0 * b0 >> 32); 
uint64_t d12 = a0 * b1;
uint64_t c1 = (d11 > 18446744073709551615 - d12) ? 1 : 0;

uint64_t d2 = a1 * b1 + c1;
uint64_t carry = d2; // needed carry stored here