[Nickle] Fwd: nickle slow for large factorials

[Keith Packard]

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>