Factorial algorithms (also: HI everybody!!)

Hi there! I've spent most of the past year over at popular science's forum and never knew this one was here, even though I receive the exosci mail!

Well, I'm not entirely certain that my question is definitely relevant to this forum, but it's probably more likely to be read by someone with a specific interest in math than the general interest I imagine I'd encounter over in the astronomy forum (even though it's a cosmology conundrum which spurred this question in my mind). Sorry it's so long, but here goes:

Question:

When one calculates n! is there a method to do so quickly without crunching all intermediate n-x factors? For example, when summing all numbers 1+2+3+...n one can either add all numbers from 1 to n or one can apply a simple formula to find the answer without too much effort; can/has this be done for n!?

Specific examples: 10+9+8+7+6+5+4+3+2+1=(100+1)(100/2)=101*50=5050
10*9*8*7*6*5*4*3*2*1= (no exact shortcut) =3628800

I've run across the Stirling approximation formulae, but they're just insufficiently approximate (predictably enough). Granted the inaccuracy drops off to infinitesimally small amounts by ratio of the whole correct answer to the whole incorrect answer (say, 1% or 2% for n~100), but when comparing the logarithms, there's still an inaccuracy of several percent for extremely large numbers (1% or 2% of the correct log for n~1E+100). However, as a caviat, I must say that I've run across several different versions of it where the steps are not defined well enough to discern whether step a applies to part a or to parts a,b and c (as a generalisation).

I've also run across Simpson's Rule, but I must have gone at this one too many times because I can't see how it applies to this at all (at least not in any way to make matters easier and more concise) to Stirling's approximation.. The Gamma function offers nothing more than n-1! and that's not really any kind of help, it's like explaining first causes by invoking zeroeth causes.


My attempts to date (each obviously a doomed attempt):


Multiplication is really just shorthand addition, so I ran up a table (ok, several actually) with columns showing n (from 1 to 10), n!, n^2, n^n, n^n-1, a breakdown on each line showing n! as (n-1!)+(n-1!)+... n-many times, and formulae for each n! as a function of n.

I've looked at the series of numbers as both rising and falling factorials, I've tried pyramidal charts of the nature of having a 1 listed on each of the the first two lines, 2 2's on the third line, 3 6's on the fourth, etc. in such a way that any given tier of the pyramid added all together is equal to n-1/nth's of n! (essentially, each cell entry is then equal to 1 n-1th of n).

I then tried to solve for n! as a function of the sum of the first number on each tier (i.e.: 1,1,2,6,24,120...) but that's pointless: it's just the same as solving n! as a function of n-1!... that's all good and well for a c++ recursion, but pretty useless for a handwritten easily remembered and performed (preferably mentally performable) algorithm.

I've tried it as a variety of Archimidean spiral, but that petered out rapidly.

Treating it as an n-dimensional cube with sides of unequal length still seems promising, but that's proved fruitless so far. The cube's n! unit volume is similar to n!=[(n^2)+(n-1^2)+...]+[(n+1)(n/2)] but that yields ludicrously low answers. Please note that I assert similarity, not identity.

It's basically the rising recursive: (n^2)+n = x, repeat as [((n^2)+n)^2]+((n^2)+n) = (x^2)+x = y, {[[((n^2)+n)^2]+((n^2)+n)]^2]+[[((n^2)+n)^2]+((n^2)+n)]]} = [((x^2)+x)^2]+((x^2)+x) = (y^2)+y = z .... which is then reiterated ad nauseum; that's a dead end too.

I wrote a spreadsheet program as well as one in basic, and flow charts of both the programs and of the normal pen and paper methods of finding n! in the hopes of spotting a flaw in my reasoning, or some bizarre verbal imaging pattern rather than the mathematical progressions that I've been approaching it through... no dice.

At one point I even looked at it as a question in accounting where the interest is compound and directly proportional to the year(s) since the deposit.


The best luck I've had so far has been with the general formula of n[(n+(n-1)+...)^2] derived from n!=n+[n*(n-1)]+{n[n(n-1)]}. I know the original sequence there was wrong, but it had yielded the most nearly correct answers so far for larger values of n! (for example it shows 8! as 10,376 (rather than 64320) and 10! as 255,025,000 (rather than 3,628,800); too low and then too high).



------------------

Please Register or Log in to view the hidden image!

-R.