Well, not quite. But once in a while I get tired of hearing yet another elementary lesson in computer programming which demonstrates recursion by the famous happy function, the factorial:
Given a non-negative integer x:
if x<2 then x!=1
else x*(x-1)!
So people write
int fact(int x)
{
if(x<2)return 1;
else return x*fact(x-1);
}
Of course, real programmers never write that. They have a healthy respect for recursion. Also, they know that one can give an explicit form of the recursive definition:
x! = PI i (as i varies from 1 up to x)
However, as I
wrote some time ago on the old ACS blogg, we know that computers are not very good at
mathematics, especially simple mathematics like addition or multiplication. Though as we know, they are exceedingly fast, if you do not expect too much of them! They are machines, not brains. But we must appreciate such things - our cars or our computers or even our food - as they are, not as what we wish they might be. Fantasy is only possible for realists.
And so, in order to help you stay grounded in the real world, and keep from taxing your machinery, I hereby provide you with all the factorials you will need, at least until some future generation of machines come out with larger integers. (Yes, I am well aware that one can write code to handle arbitrarily large numbers, but that's not relevant here.)
As much as I despise "C" (which I always felt was a grade), I use it often, and there are many dialects which have been degraded from it. So I present my offering to you in "C"...
/*
We assume BIGINTEGERTYPE is a sixty-four bit integer type.
This array contains all the factorials from 0! to 20!, which is the largest that can be stored in a 64-bit variable.
Also note that 12! = 479001600 is the last that fits in 32 bits.
*/
BIGINTEGERTYPE fact64[]=
{1,1,2,6,24,
120,720,5040,40320,
362880,3628800,39916800,479001600,
/* these are larger than 4294967295 which is 2-to-the-32 minus one...*/
6227020800,87178291200,1307674368000,
20922789888000,355687428096000,6402373705728000,
121645100408832000,2432902008176640000};
There you are! Have fun, and please don't hurt yourself playing with those huge numbers. Observe lab safety techniques, and be nice to your lab mates.
Yes, just in case you were wondering:
1. the biggest factorial that fits into a 32-bit integer is 12!
2. the biggest factorial that fits into a 64-bit integer is 20!
Some other fun things, especially if you have bothered to pay attention in other classes:
1. 2
20 is 1048576, just over a million. So, when you play Twenty Questions, you are able to "sort" among over million items (assuming certain binary properties, etc).
2. Since (2
64) is 18 446 744 073 709 551 616,
a handy way to remember an approximation is "three coulombs".
That is, since a coulomb is 6*10
18, 2
64 is three times that, or 18*10
183. 20! is a third of a coulomb, that is 2*10
18.
4. 24! is just over a mole (that is 6*10
23)
5. pi seconds is (approximately) a nano-century.
6. the ratio of
(inch to mile)
is approximately the same as
(astronomical unit to light-year)