Ben - 4 months ago 63

C 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`

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

Answer

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