[Nickle] nickle slow for large factorials

[Michel Alexandre Salim]

This occurs on both Fedora 12 and 13, x86_64:

https://bugzilla.redhat.com/show_bug.cgi?id=560750

- 666666! takes very long to compute and hundreds of MB of RAM
- implementing fac as a tail-recursive function has the same result:

$ nickle
> int fack (int n, int a) {
+   if (n==0) return a;
+   return fack(n-1, a*n);
+ }
> fack (5, 1)
120
> fack (666666, 1)

// kill after about 20 seconds

^CUnhandled exception signal (2)
<stdin>:3:     return fack (n - 1, a * n);
    fack (478575, ^C^C)
<stdin>:6:     fack (666666, 1);

It looks like Nickle's handling of bignums is inefficient -- has there
been thoughts about using GMP for large numbers? The tail recursion
itself is fine, even for mutually recursive functions:

> bool evenp (int n) {
+   if (n==0) return true;
+   return oddp (n-1);
+ }
->     return oddp (n - 1);
<stdin>:13: No visible symbol "oddp" in scope
> bool oddp (int n);
> bool evenp (int n) {
+   if (n==0) return true;
+   return oddp (n-1);
+ }
> bool oddp (int n) {
+   if (n==0) return false;
+   return evenp (n-1);
+ }
> evenp(10)
true
> evenp(11)
false
> evenp(666666)
true

Thanks,

-- 
Michel Alexandre Salim
Fedora Project Contributor: http://fedoraproject.org/

Email:  salimma at fedoraproject.org  | GPG key ID: 78884778
Jabber: hircus at jabber.ccc.de       | IRC: hircus at irc.freenode.net

()  ascii ribbon campaign - against html e-mail
/\  www.asciiribbon.org   - against proprietary attachments