#999 handling of large factorials

closed
nobody
Lisp Core (471)
5
2009-01-04
2006-10-05
No

evaluation of large factorials, such as 143311! leads
to a value stack overflow when evaluated in wxMaxima
0.7.0a, but not in the command line version of maxima:

Maxima encountered a Lisp error: Error in FORMAT [or a
callee]: Value stack overflow.Automatically
continuing.To reenable the Lisp debugger set
*debugger-hook* to nil.

The error is explicit enough to understand it is an
overflow... but when trying to evaluate even larger
factorials, such as 1433115!, windows simply reports a
standard program failure with no message from maxima
regardless of the interface you use.

version used:

Maxima version: 5.10.0
Maxima build date: 19:9 9/21/2006
host type: i686-pc-mingw32
lisp-implementation-type: GNU Common Lisp (GCL)
lisp-implementation-version: GCL 2.6.7

also using Windows XP profesionnal with SP2.

Discussion

  • Robert Dodier

    Robert Dodier - 2006-10-21

    Logged In: YES
    user_id=501686

    Interesting problem. If I had to guess I would say that GCL
    is not verifying whether some memory allocation has
    succeeded. Some additional data.

    (1) With Maxima 5.10.0cvs + GCL 2.6.7 + Linux, computations
    of a:143311!$ succeeds (3 s) and a2:1433115$ succeeds (76
    s). Note that display of a and a2 is suppressed by $.

    (2) (Again with GCL 2.6.7) Display of a and a2 fails,
    however. a; yields (after a short delay) some garbage
    (spaces and backslashes observed on some occasions and
    random characters on another) and a2; causes a segfault.

    (3) Maxima 5.10.0 + clisp 2.38 + Linux: 143311!; yields
    "overflow during multiplication of large numbers".

    (4) Maxima 5.10.0cvs + sbcl 0.9.16: a:143311!$ takes about
    100 s, and a2:1433115!$ didn't terminate within an hour.
    Display a; seems to take longer than I'm willing to wait.

     
  • Julien B. O.

    Julien B. O. - 2007-07-12

    Logged In: YES
    user_id=1610192
    Originator: YES

    I have done some new testing and maxima can indeed compute 143311!$ with the config described above (regardless of the interface). It can also display if it is computed first with a:143311!$ and then displayed with a;. this does works in the console and xMaxima, but not in wxMaxima. The latter gives a stack overflow. But please note than the display is MUCH longer than the actual calculation (about 30x-40x). Also, a2 can compute with 1433115!$ (about 14s) but maxima crashes on display (the standard windows failure thing). The behaviour is slightly different from what robert_dodier reported in (2).

     
  • Dieter Kaiser

    Dieter Kaiser - 2008-09-14

    As desribed on the mailing list we get unpredictable errors for integers greater than about 100,000 at least for GCL 2.6.8 and CLISP 2.46.

    We get system hangs, killed sessions, output with random chars,...

    A semiliar problem we get for half integral values. The calculation is done if the argument is less then $gammalim which has a default value of 1,000,000. This value is far too big. A value of 100,000 for $gammalim might work for most (all?) systems. Perhaps it is even better to choose a much smaller value like 1,000 or 10,000.

    To prevent the Maxima User to unintentional produce such errors I would like to suggest the following changes:

    1. Set $factlim to a default value of 100,000. (GCL 2.6.0 and CLISP
    works on the console - evaluating and printing,wxmaxima get a result
    but can not print it - value stack overflow)
    Perhaps much smaller. A value of 10,000 might be very sure.

    2. In simpgamma test against $factlim (not $gammalim) before calling
    simpfact. So $gammalim and $factlim are independend.

    3. Set the default value of $gammalim to 10,000. Perhaps 1,000.

    A user who has a more powerful compiler or system could extend the range by setting new values to $factlim and $gammalim. But he has to be warned in the documentation that Maxima could fail.

    Dieter Kaiser

     
  • Dieter Kaiser

    Dieter Kaiser - 2009-01-04

    The code of the factorial function has changed. factlim is set to 100,000. Maxima gets now the following results:

    (%i43) a:100000!$
    (%i44) bfloat(a);
    (%o44) 2.824229407960348b456573
    (%i45) 100001!; /* not evaluated */
    (%o45) 100001!
    (%i46) 143311!;
    (%o46) 143311!
    (%i47) bfloat(143311!); /* it is possible in bigfloat precision */
    (%o47) 2.3765589886716839901b676715

    Closing bug report as fixed.

     
  • Dieter Kaiser

    Dieter Kaiser - 2009-01-04
    • status: open --> closed
     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks