0
$\begingroup$

I am writing code to evaluate the following expression: $$ \frac{(a+b+c)!}{a! b! c!} $$ where $a$, $b$ and $c$ are on the range of $10$ to $500$. The result is going to be a floating point number. I could use a big number package, but the code will run slowly. I am using 64-bit floating point numbers.

I claim by doing as much of the computation in integer (maybe 64 bit) I will minimize the floating point round off error. Therefore, I claim that if put the integers to be multiplied together in an array, cancel common denominators, and then do the final computation in floating point I will minimize round off error.

Do I have this right?

$\endgroup$
  • 2
    $\begingroup$ "but the code will run slowly" How fast do you need? You might be surprised. $\endgroup$ – Veedrac Jul 12 at 9:35
  • 1
    $\begingroup$ But you shouldn't worry about floating point errors, they're plenty accurate. Rather worry about overflow. $\endgroup$ – Veedrac Jul 12 at 9:56
0
$\begingroup$

You don't need to use integers for any data. Just find the largest of three numbers x=max(a,b,c) and reduce both parts by x!. Then compute in doubles. For numbers as small as 500 both 32-bit ints and 32/64 bit doubles will be precise.

EDIT: Since 64-bit FP isn't enough to deal with 1500!, you can perform computations on (decimal) logarithms of multipliers.

$\endgroup$
  • $\begingroup$ @Bulat I am thinking your solution will have more round off error than my solution. Please comment. $\endgroup$ – Bob Jul 11 at 22:22
  • $\begingroup$ @Apass.Jack The idea is to do the cancellation of common factors with integer arithmetic and then do the final multiplies and divides in floating point. $\endgroup$ – Bob Jul 11 at 22:28
  • $\begingroup$ @Apass.Jack I said "For numbers as small as 500 both 32-bit ints..." $\endgroup$ – Bulat Jul 11 at 22:42
  • $\begingroup$ @Bob All that I said is that your solution doesn't have any use of 64-bit integers. Source numbers are easily fit in 32-bit ints, and multiplications should be done in FP64 anyway. $\endgroup$ – Bulat Jul 11 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.