^{n}C

_{r}function, so I decided to code its cousin

^{n}P

_{r}.

I'd realized a nice optimization in Ariya's code. The general definition of

*is given by*

^{n}C_{r}^{n}C_{r}= n! / ((n-r)! r!)

n, r ∈ N_{0}, r ≤ n(applies all bellow)

But we can indeed reduce very much the number of integer multiplications with the derivation

r ∈ {0, n} ⇒^{n}C_{r}= 1

r = 1 ⇒^{n}C_{r}= n

r ∈ ]0, n/2] \ {1} ⇒^{n}C_{r}= (r+1)_{n}/ (n-r)!

r ∈ ]n/2, n[ \ {1} ⇒^{n}C_{r}= (n-r+1)_{n}/ r!

Note that

*(r+1)*, for instance, is a modern factorial notation equivalent to

_{n}*(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

*. The general definition of*

^{n}P_{r}*is given by*

^{n}P_{r}^{n}P_{r}= n! / (n-r)!

And again we can do some magic

r = 0 ⇒^{n}P_{r}= 1

r = 1 ⇒^{n}P_{r}= n

r = n ⇒^{n}P_{r}= n!

r ∈ ]1, n[ ⇒^{n}P_{r}= (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:

Post a Comment