1

I have a very specific algorithm that requires doing a lot of calculations of (a * b) / c in Java, where:

  • a and b are 64-bit longs
  • a*b may overflow into 128 bits (not always, but at least reasonably common)
  • c is a 64-bit long
  • The result (a * b) / c should fit in a 64-bit long (we need to detect if it overflows, but the result doesn't matter in this case)

Is there an efficient algorithm to do this kind of fused multiply and divide? I naturally tried using BigInteger which works fine but is unacceptably slow (this needs to be high performance code).

Luther Kroe
  • 21
  • 3
  • 1
    What you want to do if `a*b` overflow ? – thibsc Aug 22 '20 at 03:06
  • I think that is actually (a * b) / (c * c), right :-) ? I looked at some equivalent formulae but they don't seem to help or give very imprecise results given integer maths, e.g. (a / c) or (b / c) is often zero. – Luther Kroe Aug 22 '20 at 03:09
  • @thibsc good question. if `a*b` overflows 64 bits, the division still needs to work correctly, i.e. we need to be able to divide the 128-bit result by the 64-bit `c`. I don't think it can possibly overflow 128 bits? – Luther Kroe Aug 22 '20 at 03:11
  • So I don't understand why you said *"we need to detect if it overflows, but the result doesn't matter in this case"*, if you want to do the division in the case of `a*b` overflows. Maybe you can add some example of what you really want in each case – thibsc Aug 22 '20 at 03:16
  • and here are some solutions in C++ which can be easily converted to Java: [Most accurate way to do a combined multiply-and-divide operation in 64-bit?](https://stackoverflow.com/q/8733178/995714), [How to multiply a 64 bit integer by a fraction in C++ while minimizing error?](https://stackoverflow.com/q/25182577/995714) – phuclv Aug 22 '20 at 06:13

1 Answers1

0

Booth's multiplication algorithm

Jay Teli
  • 530
  • 1
  • 11
  • 19