#914 ratsimp(exp(constant)) very slow

closed
nobody
Lisp Core (471)
5
2006-05-15
2006-05-02
No

ratsimp, when applied to

%e^((sqrt(852469675641479773175661572149741)
-15762598695796738)/2251799813685248);

is very slow. But can ratsimp simplify the argument
to exp quickly.

This expression happended towards the end of a
matrixexp calculation. I've tried variations of this
expression (delete hunks of various numbers) --
sometimes ratsimp
is very fast, other times it seems to hang.

(%i18) build_info();
Maxima version: 5.9.3
Maxima build date: 0:52 3/20/2006
host type: i686-pc-mingw32
lisp-implementation-type: GNU Common Lisp (GCL)
lisp-implementation-version: GCL 2.6.7

Barton

Discussion

  • Barton Willis

    Barton Willis - 2006-05-06

    Logged In: YES
    user_id=895922

    A simpler example:

    ratsimp(exp((1932473987149817)/589347638476187146))

    Barton

     
  • Robert Dodier

    Robert Dodier - 2006-05-07
    • labels: --> Lisp Core
     
  • Robert Dodier

    Robert Dodier - 2006-05-07

    Logged In: YES
    user_id=501686

    Not sure what's going on here, but maybe the problem is in
    the factoring code.

    Maxima 5.9.3 / clisp 2.34:
    ratsimp (%e^((sqrt(852469675641479773175661572149741)
    -15762598695796738)/2251799813685248));
    => fast

    Maxima 5.9.3 / clisp 2.38 (after factor code was revised):
    => slow, and it complains
    "WARNING: could not find factors of composite:
    852469675641479773175661572149741"

     
  • Raymond Toy

    Raymond Toy - 2006-05-08

    Logged In: YES
    user_id=28849

    Interesting. Barton's simplified ratsimp example causes 2
    errors with CMUCL because pcetimes1 does f+ with a bignum
    and palgsimp does f< with a bignum. Replacing these with +
    and < fixes the issue.

    However, the ratsimp example causes a warning from cmucl
    because it wants to compute 1^1932473987149817. This is a
    cmucl problem, but depending on how smart the Lisp is, it
    might actually try to compute that power.

    Finally, for the complicated ratsimp(exp((sqrt ...)))
    example, I think the real issue is that maxima is trying to
    simplify the sqrt. If you just enter

    sqrt(852469675641479773175661572149741);

    there's a delay before maxima prints out the warning about
    not finding the factors.

    Also, factor(852469675641479773175661572149741) spends some
    time and returns 2 factors: 34130646845983 24976663333933005427.

    Not sure why there's a warning at all.

    So I think it used to be fast because sqrt(852...) factor or
    somebody gave up early and returned sqrt(852...). ifactor
    works harder before giving up.

     
  • Andrej Vodopivec

    Logged In: YES
    user_id=1179910

    The problem is not with the factoring code. Barton is
    reporting long times with version 5.9.3 (gcl+win) before
    ifactor was moved to src and it is not just a delay because
    of factoring - I interrupted the execution after a couple of
    minutes.

    Anyway I will remove the warning that factoring failed. I
    could also make the code give up sooner. The way things were
    set up before the factorization was more like testing for
    small factors rather than trying for complete factorization.

    Andrej

     
  • Andrej Vodopivec

    Logged In: YES
    user_id=1179910

    Some more examples:

    (%i1) display2d:false$
    (%i2) build_info()$
    Maxima version: 5.9.3
    Maxima build date: 0:52 3/20/2006
    host type: i686-pc-mingw32
    lisp-implementation-type: GNU Common Lisp (GCL)
    lisp-implementation-version: GCL 2.6.7

    %i3 is OK but %i4 takes a long time - the same for all
    higher denominators and other bases.

    (%i3) 2^(1/1111111111);
    (%o3) 2^(1/1111111111)
    (%i4) 2^(1/11111111111);
    Maxima encountered a Lisp error:

    Console interrupt.

    Automatically continuing.
    To reenable the Lisp debugger set *debugger-hook* to nil.

    Again %i5 is OK and %i6 has an extra (a+1)^9 factor. Similar
    with other examples with bigger denominators in exponent.
    The numerator in the exponent must be bigger than one to
    trigger this bug.

    (%i5) a^(10/1111111111);
    (%o5) a^(10/1111111111)
    (%i6) ratsimp(%);
    (%o6) a^(10/1111111111)
    (%i7) a^(10/11111111111);
    (%o7) a^(10/11111111111)
    (%i8) ratsimp(%);
    (%o8)
    a^(10/11111111111)*(a^9+9*a^8+36*a^7+84*a^6+126*a^5+126*a^4+84*a^3+36*a^2+9*a+1)

    Andrej

     
  • Raymond Toy

    Raymond Toy - 2006-05-10

    Logged In: YES
    user_id=28849

    Neat.

    I think I found the issue. In src/rat3d.lisp, in the
    function iroot, there's the line

    (cond ((f< (haulong a) n) (list 1 (sub1 a)))

    That f< seems to be the problem because n is not a fixnum.
    Replacing f< with plain < solves both the 2^(1/111...) and
    a^(10/111....) issue.

    Someone should look at all of the uses of f<, f+, etc. in
    rat3*.lisp and replace them with <, +, etc., as needed.

     
  • Andrej Vodopivec

    Logged In: YES
    user_id=1179910

    Actually just this does not fix a^(10/11..) issue - if you
    call ratsimp on it it still fails.

    To solve this and get Bartons example done fast I had to
    change f< to < in palgsimp and f- to - in pasimp1 in rat3a.lisp.

    Andrej

     
  • Raymond Toy

    Raymond Toy - 2006-05-10

    Logged In: YES
    user_id=28849

    Oh. I had already made that change in my sources because
    cmucl complained about it.

    Now if we could only check in the fix!

     
  • Raymond Toy

    Raymond Toy - 2006-05-13

    Logged In: YES
    user_id=28849

    All of the tests listed herein are fixed. But the original
    report about exp(sqrt(foo)...) is still slow. That does
    appear to be an issue with factor (ifactor).

     
  • Andrej Vodopivec

    Logged In: YES
    user_id=1179910

    I updated ifactor.lisp - maxima now returns the answer
    without delays and warnings.

    Andrej

     
  • Raymond Toy

    Raymond Toy - 2006-05-15

    Logged In: YES
    user_id=28849

    Very good! Let's close this.

     
  • Raymond Toy

    Raymond Toy - 2006-05-15
    • status: open --> closed
     

Log in to post a comment.