Catch and compute overflow during multiplication of two large integers

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 results 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.

Answer 1

1. Detecting the overflow:

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

Edit: Fixed division by 0 (thanks Mark!)

2. 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 ((1ULL << 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).