range error - or "How to take the factorial of a huge number"

[Jim Witte]

.Oh God,

   Just thinking off the top of my head, I'm thinking recusion overflow 
(unless the RunRev compiler automatically CPS's recursive function 
automatically, which I doubt)  Try this script (written off the top of 
my head

function factorial (n)
	return factAPS(n, 1)	-- start the accumulator at 1
end factorial

function factAPS (n, a)
	if (n=1) then
		return a	-- we stop multiplying the accumlator at n=1 because a*1=a
	else
		put a*n into a	-- update the accumulator
		factAPS(n-1, a)
	end if
end factAPS

   This is factorial in acculator-passing-style, which is closely 
related to continuation-passing-style, but I can't do the CPS in my 
head, and I think it would just build up a great long list of numbers 
instead (the list-representation of the continuation).  If MetaCard is 
coded right, the factAPS call at the end should be turned into a jump 
(since nothing, like a *, is "waiting" for it's result).  This will 
avoid a recursion stack, and most likely speed up the code a GREAT deal 
(though that depends on the specifics of how MetaCard's bytecode 
interpreter works).

   If MetaCard supports a goto statement, the above could (possibly) be 
further optimized to this:

function factorial (n)
	put n into gn
	put 1 into ga

label factAPS:
	if (gn=1) then			-- line 1
		return ga
	else
		put ga*gn into ga
		put gn-1 into gn	-- line 2
		goto factAPS
end factorial

   This is functionally *exactly* the same code as above, except that I 
explicitly registerized it (with the variables gn and ga), and made the 
goto explicit.  But it is still guaranteed to terminate because gn is 
always decreasing (line 2), and the return statement is invoked when gn 
gets down to 1 (line 1).  This might be just a hair quicker that the 
first function, depending on how MetaCard optimizes things (if it does, 
it will do this transformation automatically - indeed, just as I did.  
If it were really good, it would take the OP's factorial function, and 
then turn it into the two code samples above - automatically.)

   Another possibility (a little less accurate though) for calculating 
really big factorials is to use Sterling's formula and the gamma 
function.  Look at

http://mathworld.wolfram.com/StirlingsApproximation.html

for a technical (read, integral calculus, although all that is is a 
nifty name for an infinite sum) description.

The function would be:

on factorialApprox (n)
	return sqrt( 2*pi) * (n^ (N+1/2)) * exp( -n );
end factorialApprox

in conventional math notation, that's

n! ~
  
-------------- next part --------------

or sqrt(2 pi) n^(n+1/2) e^(-n)

if the gif didn't come through

(Parts copyright MathWorld, ? 1999 CRC Press LLC, ? 1999-2004 Wolfram 
Research, Inc.)

Jim

> When I attempt to calculate the factorial of numbers > 169 using the 
> following function:
>
> function factorial theNumber
>   if theNumber <= 1 then return 1
>   else return theNumber * factorial(theNumber -1)
> end factorial
>
> I get the following error.  Anybody seen this before?
>
> executing at 11:46:47 PM
>
> Type	Operators *: range error (overflow)
> Object	Bed Adequacy
> Line	else return theNumber * factorial(theNumber -1)
> Hint	factorial
>
> Is there a work around for this?
>
> OSX 10.2.8, Rev 2.1.2, 512 MB of RAM
>
> Thanks
>
> Steve
>
> Stephen R. Messimer, PA
> 208 1st Ave. South	
> Escanaba, MI 49829
> http://www.messimercomputing.com
> --
> Build Computer-Based Training modules FAST with preceptorTools? -- 
> version 1.0.5 available Now!
>
> _______________________________________________
> use-revolution mailing list
> use-revolution at lists.runrev.com
> http://lists.runrev.com/mailman/listinfo/use-revolution
>