• Advertisement
Sign in to follow this  

MulDiv: a*b/c for 64bit integers

This topic is 3480 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I'm looking for a way to calculate a*b/c for large 64bit integers without suffering from overflow and truncation. (It's implemented in C#, so when I talk about "long", I mean 64 bit integers) So here's my train of thought. First the obvious choices: a*b/c will overflow if a*b > long.MaxValue a/c*b will return the wrong value, the quotient a/c is truncated if c does not divide a properly Therefore I tried to decompose the calculation a bit:
public static long MulDiv(long a, long b, long c) {
  var whole = a/c*b;
  var fraction = (a%c)*b/c;
  return whole + fraction;
}
This approach is not really bad, but it still fails if (a%c)*b > long.MaxValue. Especially it's only useful if a%c is notably smaller than c. I tried to make the product (a%c)*b smaller by splitting fraction into two parts:
public static long MulDiv(long a, long b, long c) {
  var whole = a/c*b;
  var fraction1 = (a%c)*(b/c);
  var fraction2 = (a%c)*(b%c)/c;
  return whole + fraction1 + fraction2;
}
But again this is only an improvement if b%c is small. I know that it is impossible to stay in the 64 domain for every possible combination of 64 bit values. But assume that the result is always within the 64bit domain, is there a algorithm that can calculate a*b/c efficiently without any intermediate result outside of 64bits? Regards, Andre Edit: I appears that I can relax the requirements a bit: for my application it is enough if b and c are 32 bit ints. In this case this should always work as long as a/c < int.MaxValue:
public static long MulDiv(long a, int b, int c){
  var whole = a / c * b;
  var fraction = (a % c) * b / c;
  return whole + fraction;
}
Both a%c and b will be within 32 bit domains, so their product will stay within 64 bits. Still I'm interested in a solution for all three arguments being 64 bit values. [Edited by - VizOne on July 9, 2008 6:24:53 AM]

Share this post


Link to post
Share on other sites
Advertisement
The multiplication instruction in the CPU usually outputs to two registers, so you get the full result. In x86, the 128-bit result of multiplying to 64-bit integers is stored in rdx:rax. It's too bad that most compilers only give you access to the lower 64 bits of the result. If your compiler doesn't provide an intrinsic to retrieve the higher 64 bits, you can try to use inline assembly. If that's not possible, you can interpret your numbers as 2-digit numbers in base 2^32 and multiply them as we learned in school.

You may want to read this document: http://images.apple.com/acg/pdf/20060614_64bit_multiprec.pdf

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement