Annoyed! or, time for some fun
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. 220 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 (264) 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*1018, 264 is three times that, or 18*1018
3. 20! is a third of a coulomb, that is 2*1018.
4. 24! is just over a mole (that is 6*1023)
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)
posted by Dr. Thursday @ 5/03/2011 10:38:00 AM
4 comments
4 Comments:
I'm trying to discover a good reason for wanting all those integer factorials... I suppose factorial appears as a formal denominator in every taylor series, but there it's usually preferable to guess how many terms you'll need first, and start at the end:
((...((f[n]*x/n + f[n-1])*x/(n-1)+f[n-2])...)*x/2+f[1])*x+f[0]
or, perhaps,
//----
#ifndef MAX_PREC
#include "taylor-precision-rules.h"
#endif
/* approximates a taylor polynomial of degree 'precision or 'MAX_PREC, whichever looks easier, given an array of derivatives at zero.
Not very smart, but better than some */
double taylor(double *f,double x,int precision){
int looping = min(precision,MAX_PREC);
int n;
double estimate = f[looping];
for (n = looping;n>0;1){
estimate = (estimate * x / n) + f[--n];
}
return estimate;
}
//----
and furthermore, we don't need the precise integral value of any factorial to get a useful number from this calculation. And this procedure is still reasonable when x is large enough that you'd want more than twenty terms.
"a good reasons for wanting all those integer facotials"
A very good question indeed!
Generally you DON'T... but the way some teachers rave you'd think they were in common use. Maybe in college, but not in the real world.
I will tell another story about their use in a future post, very funny...
The point is to give a relatively simple example of how recursion works, so when you have to do _recursion_ in the real world you understand how to break up a problem. None of the example problems are actually efficient for the same reason you'll never encounter them in the real world: they brute-logic-force a relatively simple bit of insight. We use them in college so that the concept of brute-logic-forcing a thing can be learned, as it _is_ useful on relatively complex bits of computation.
That said, knowing when to use a shortcut that is logically equivalent to and computationally more efficient than the brute-logic-force method is also a valuable skill, and should be taught to programmers so that they don't just go guessing when they should make the computer logic a thing and when they should frame the problem in their own terms so the computer's job is simpler.
~a fellow programmer, finishing up his own college while working an actual internship and creating Java toys in his spare time... for what it's worth
P.S. You have, apparently, been challenged.
P.P.S. I was a chemist before I was a programmer. A mole is 6.02 * 10^23. Leave out that .02 and you'll never figure out precisely when Mole Day is!
P.P.P.S. Word Verification: "entest". Looks like a Middle English word which we have since dropped the "en" from, no?
Post a Comment
<< Home