[Nickle] Fwd: nickle slow for large factorials

[Keith Packard]

On Mon, 05 Jul 2010 08:32:25 -0400, Keith Packard <keithp at keithp.com> wrote:
> On Mon, 5 Jul 2010 10:01:21 +0200, Michel Alexandre Salim <michael.silvanus at gmail.com> wrote:
> 
> > I forgot to mention that this is in fact what I implemented, and htop
> > still reports memory consumption in the hundreds of megabytes, and !
> > does so too. I wonder if nickle's numerical system is leaking memory?
> 
> I suspect the nickle compiler just didn't figure out that you were doing
> tail recursion; in particular, it doesn't figure it out if you're using
> ?: instead of if/then/else. Did you send me a copy of the code before? I
> can't find it now.

Oh, there it is -- yes, nickle detects that as tail recursive and
correctly limits memory usage, although it doesn't limit it very
hard. You'll note that the memory usage goes up and down during the
computation as it is allocating lots of temporary values (it doesn't try
to re-use storage).

It's not the bignum computations that are slow here; nickle has
reasonably fast compute code. Of course, the trivial factorial
implementation can't take advantage of the karatsuba multiplication
function which only works with terms of comparable size, so it's just
doing grade-school multiplication.

-- 
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/fcc4c151/attachment.pgp>