Thursday, May 24, 2007


So now SpeedCrunch has got combinatorics support. Ariya had already implemented the famous nCr function, so I decided to code its cousin nPr.
I'd realized a nice optimization in Ariya's code. The general definition of nCr is given by
nCr = n! / ((n-r)! r!)
n, r ∈ N0 , r ≤ n (applies all bellow)

But we can indeed reduce very much the number of integer multiplications with the derivation
r ∈ {0, n} ⇒ nCr = 1
r = 1 ⇒ nCr = n
r ∈ ]0, n/2] \ {1} ⇒ nCr = (r+1)n / (n-r)!
r ∈ ]n/2, n[ \ {1} ⇒ nCr = (n-r+1)n / r!

Note that (r+1)n, for instance, is a modern factorial notation equivalent to (n)(n-1)...(r+1). I didn't know about this myself until now. This fasts computation a lot, else the very same calculations would be uselessly repeated.
In the very same way, I found a nice simplification for nPr. The general definition of nPr is given by
nPr = n! / (n-r)!

And again we can do some magic
r = 0 ⇒ nPr = 1
r = 1 ⇒ nPr = n
r = n ⇒ nPr = n!
r ∈ ]1, n[ ⇒ nPr = (n-r+1)n

I spent some minutes getting to this conclusion and then I read it somewhere right after. First I felt a bit frustrated, then I smiled. It's funny to develop this program, it's funny to play maths.

I then realized my old Casio FX-880P can compute up to 69! and SpeedCrunch currently up to 96!, that's good enough (150-digit long integer). Nevertheless, when the user tries to calculate factorials, combinations or permutations with huge parameters the program freezes (even by the calc-as-you-type feature). Maybe it's really a good idea to define an upper limit for those functions input.

No comments: