Re^2: Operations with Extremely Large Numbers

[BrowserUk]

A further thought. If these calculations are in anyway time-critical.

In almost every formula I've ever encountered that uses huge factorials -- usually probability calculations of one form or another -- there are usually (at least) two factorial (or factorial derived) terms that eventually are divided one by the other so bringing the silly numbers back into the realms of rationality.

So you tend to have formulae something like:

r = n! / (n - m)!

Ostensibly, the calculation goes like this:

n = 1e9
m = 4

r = ( 1 * 2 * 3 ... 999999999 * 1000000000 ) 
  / ( 5 * 6 * 7 ... 999999999 * 1000000000 )

Which using arbitrary precision can take long time (and a large amount of memory) to calculate.

But with cursory inspection it is easy to see that the result is just 1/ ( 1* 2 * 3 * 4 ) == 1/24 == 0.041666666666666666666666666666667 .

If your application requires the calculation of large numbers of these types of formulae, and timeliness is of any consideration, it makes sense to avoid the huge numbers by deferring the actual math until you've performed some "cancelling out".

In most cases, the avoidance of arbitrary precision more than compensates for the extra effort and care required.

[jjw017]

Thanks BrowserUk. I literally bonked myself in the head after reading this. I'm going to try giving careful consideration to the overall formula to see if there's mathematical cancellations.

[jethro]

Small correction, 1e9! / (1e9-4)! would not be 1/(1*2*3*4) but 1/(999999997*999999998*999999999*1000000000)

And you are probably thinking about the binomial coefficient, which is n! / ( k! * (n-k)! )