[Nickle] Fwd: nickle slow for large factorials
Keith Packard
keithp at keithp.com
Sun Jul 4 21:23:56 PDT 2010
On Mon, 5 Jul 2010 02:48:37 +0200, Michel Alexandre Salim <michael.silvanus at gmail.com> wrote:
> Ah, thanks. Any reason why the memory consumption is so high even the
> tail-recursive implementation? Memory usage should be not much worse
> than whatever it takes to represent 666666! in memory.
You can't do trivial tail recursion in the factorial function -- you
have to perform additional computation after each recursive function:
int fact(n) = n > 1 ? n*fact(n-1) : 1;
The killer here is the n* -- without that, you have a simple tail
recursive function. Refactor this into a pure tail call:
int fact2(n,m) {
if (n <= 1)
return m;
return fact2(n-1,n*m);
}
int fact(n) { return fact2(n,1); }
and now you get the tail call behaviour.
You'll note that the internal factorial implementation isn't recursive,
and so avoids consuming huge amounts of memory;
I'm testing a couple of faster factorial functions as described here:
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
I've got both the Split and PrimeSwing algorithms implemented and they
seem to work reasonably well; your test value (666666) runs in about a
minute using the most obvious nickle translation of either function. I'm
testing with some larger values; 6666666 appears to take somewhat longer
than I'm willing to wait this evening.
GMP doesn't appear to use anything much fancier than the most obvious
factorial algorithm, simply re-ordering the multiplies to try and get
some balance into the terms so that the Karatsuba multiplication code
runs more efficiently.
--
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: </pipermail/nickle/attachments/20100705/7be940c1/attachment.pgp>
More information about the Nickle
mailing list