sign of expressions with exponents crashes

[rtoy]

Imported from SourceForge on 2024-07-03 15:47:48 Created by robert_dodier on 2016-04-27 20:02:47 Original: https://sourceforge.net/p/maxima/bugs/3147

---

From the mailing list circa 2016-04-26.

This example causes a stack overflow in PDISREP2EXPAND:

assume(t>0)$
sign(2^(500005*t)-2^(500001*t));

The following command runs fine:

assume(t>0)$
sign(2^(500000*t)-2^(500003*t));

The next one is surprisingly slow. I'm guessing it is related to the preceding one, but possibly it is a separate bug.

assume(t>0)$
sign(2^(40005*t)-2^(40001*t));

[rtoy]

Imported from SourceForge on 2024-07-03 15:47:50 Created by tomasriker on 2016-04-28 14:23:47 Original: https://sourceforge.net/p/maxima/bugs/3147/#2a3c

---

I found this to be caused by factoring in sign. When preventing factoring by changing factor-if-small in compar.lisp to simply return the input unchanged, there is no crash and we get a correct answer.

During the computation, the expression 1-2^(500001*t) is factored. Since 500001 has only two factors, 3 and 166667, this would result in an extremely long answer that makes the stack explode.

However, completely removing the factoring is not a good idea, either. Instead, I propose the following: First, try to determine the sign without factoring. If that answer is pos or neg (the "strongest" answers), then give that answer. Otherwise, try factoring.

[rtoy]

Imported from SourceForge on 2024-07-03 15:47:53 Created by tomasriker on 2016-04-29 09:03:20 Original: https://sourceforge.net/p/maxima/bugs/3147/#fef6

---

As Richard Fateman proposed on the mailing list, looking at the maximum degree should be a better heuristic to be used in factor-if-small than just looking at the conssize of the expression.

I implemented the following max-degree function, since hipow won't work for something like 2^(1000*t) (hipow(2^(1000*t), 2^t) returns 0).

Please review, as I'm still an absolute LISP beginner:

;; Finds the maximum degree of any rational variable appearing in x.
(defun max-degree (x)
  ;; Convert x to CRE form, suppressing info messages.
  ;; For some reason, genvar and varlist have to be bound,
  ;; or some tests will fail.
  (let ($ratprint genvar varlist)
    (setq x (ratrep* x)))
  ;; Deep-copy x because we'll destructively modify it.
  (setq x (copy-tree x))
  (let ((current-max-degree 0))
    ;; Process the content of x, always looking at its first element.
    (setq x (cdr x))
    (loop while (and (not (null x)) (listp x)) do
      (cond
        ;; If the first element is a list, "unpack" it.
        ((listp (car x))
          (setq x (nconc (car x) (cdr x))))
        ;; If it's a symbol, then it denotes a rational variable,
        ;; and the next element will be its exponent.
        ((symbolp (car x))
          (setq current-max-degree (max current-max-degree (cadr x)) x (cdr x)))
        ;; Otherwise, proceed with the next element.
        (t (setq x (cdr x)))))
    current-max-degree))

The factor-if-small function adjusted to use both conssize and max-degree:

(defun factor-if-small (x)
  (if (and (<= (conssize x) 50) (<= (max-degree x) 100))
    (let ($ratprint)
      (factor x))
    x))

This fixes the factoring stack overflow bug that this issue is about.

Patch attached!

Attachments:

• https://sourceforge.net/p/maxima/bugs/_discuss/thread/6bd76eca/fef6/attachment/fix.patch

[rtoy]

Imported from SourceForge on 2024-07-03 15:47:57 Created by peterpall on 2017-03-24 05:29:04 Original: https://sourceforge.net/p/maxima/bugs/3147/#8f19

---

The patch no more applies cleanly => Updated it.

Attachments:

• https://sourceforge.net/p/maxima/bugs/_discuss/thread/6bd76eca/8f19/attachment/0001-Don-t-crash-when-comparing-functions-with-high-expon.patch

[rtoy]

Imported from SourceForge on 2024-07-03 15:48:00 Created by peterpall on 2017-03-24 05:44:25 Original: https://sourceforge.net/p/maxima/bugs/3147/#93c5

---

Seems like the patch does solve many problems - but not all: In

max(2.103-7.053*%e^(-4.0681*10^5*t), 2.0325-6.9825*%e^(-4.9238*10^5*t));

there is no absolutely big exponent and in

werte:[
        U=5,
        R1=1000,R2=1000
    ];
    max(0,(179310*%e^(0.1179551675337146*(V/n-160)))/14093336137-U/(R2+R1))*h;
    subst(werte,%);

the out-of-memory isn't caused by a big exponent.

As determining the sign of an expression is generally affected by the halting problem I don't know if this kind of thing is to be expected, though.

[rtoy]

Imported from SourceForge on 2024-07-03 15:48:04 Created by peterpall on 2017-03-24 07:43:34 Original: https://sourceforge.net/p/maxima/bugs/3147/#1f96

---

As a second thought perhaps the information if factoring will result in something big only this only will be possible to detect during factoring:

exp(10e6*t)

has an argument that is only big if t is big enough. But during factoring the expression will be converted to:

exp(10e6)*exp(t)

which (when trying to factor it further) will use up all available memory. Perhaps a better approach would be to actually start factoring and to give up if it is obvious that the result will be insanely big.

Found another side-effect of the proposed patch: It seems to prevent factoring in a few places that are hit by the testbench:

Running tests in rtest_sign: ********************** Problem 5 (line 14) ***************
Input:
max(2.0325-6.9825*%e^((-492380.0)*t),2.103-7.053*%e^((-406810.0)*t))
Result:
error-catch
This differed from the expected result:
max(2.0325-6.9825*%e^((-492380.0)*t),2.103-7.053*%e^((-406810.0)*t))
********************** Problem 21 (line 65) ***************
Input:
sign(x)
Result:
pnz
... Which was correct, but was expected to be wrong due to a known bug in
 Maxima.
********************** Problem 25 (line 77) ***************
Input:
sign(x^2+x)
Result:
pnz
... Which was correct, but was expected to be wrong due to a known bug in
 Maxima.
********************** Problem 26 (line 80) ***************
Input:
sign(x^2+x+42)
Result:
pnz
This differed from the expected result:
pos
********************** Problem 35 (line 107) ***************
Input:
sign(x^2+2*x*y+y^2+1)
Result:
pnz
This differed from the expected result:
pos
********************** Problem 40 (line 122) ***************
Input:
sign((-sqrt(2))*(x+y)^2-%phi*(z-x)^2-%pi)
Result:
neg
... Which was correct, but was expected to be wrong due to a known bug in
 Maxima.
********************** Problem 45 (line 140) ***************
Input:
sign(1+x/(1+x^2))
Result:
pnz
This differed from the expected result:
pos
********************** Problem 65 (line 204) ***************
Input:
sign(-(x^(1/4)+1))
Result:
neg
... Which was correct, but was expected to be wrong due to a known bug in
 Maxima.
********************** Problem 70 (line 221) ***************
Input:
sign(cosh(x)-1)
Result:
pnz
This differed from the expected result:
pz
********************** Problem 72 (line 227) ***************
Input:
sign(tanh(x))
Result:
pnz
... Which was correct, but was expected to be wrong due to a known bug in
 Maxima.
********************** Problem 77 (line 244) ***************
Input:
sign(acos(x))
Result:
pnz
This differed from the expected result:
pz
********************** Problem 79 (line 250) ***************
Input:
sign(atan(x))
Result:
pnz
... Which was correct, but was expected to be wrong due to a known bug in
 Maxima.
********************** Problem 84 (line 265) ***************
Input:
sign(acosh(x))
Result:
pnz
This differed from the expected result:
pz
355/362 tests passed (not counting 7 expected errors)
The following 7 problems failed: (5 26 35 45 70 77 84)
Running tests in rtest_algebraic: 45/45 tests passed
Running tests in rtest_gamma: 761/761 tests passed
Running tests in rtest_expintegral: 210/210 tests passed
Running tests in rtest_signum: 59/59 tests passed
Running tests in rtest_lambert_w: 57/57 tests passed
Running tests in rtest_elliptic: 179/179 tests passed (not counting 2 expected errors)
Running tests in rtest_integrate: 812/812 tests passed
Running tests in rtest_integrate_special: 53/53 tests passed
Running tests in rtest_sqrt: 313/313 tests passed (not counting 1 expected errors)
Running tests in rtest_carg: 55/55 tests passed (not counting 2 expected errors)
Running tests in rtest_log: 129/129 tests passed
Running tests in rtest_power: 72/72 tests passed (not counting 5 expected errors)
Running tests in rtestdefstruct: 32/32 tests passed
Running tests in rtest_limit: 214/214 tests passed
Running tests in rtest_powerseries: 67/67 tests passed
Running tests in rtest_laplace: 98/98 tests passed (not counting 11 expected errors)
Running tests in rtest_plotoptions: 5/5 tests passed
Running tests in rtest_algsys: 55/55 tests passed
Error summary:
Errors found in /usr/local/share/maxima/branch_5_39_base_137_g3987a2f/tests/rtest_sign.mac, problems:
(5 26 35 45 70 77 84)
7 tests failed out of 11,170 total tests.
Real time: 812.9275f0 sec.
Run time: 811.82434f0 sec.
Space: 37583730368 Bytes
GC: 6843, GC time: 69.6257f0 sec.
(%o0)   
done

[rtoy]

Imported from SourceForge on 2024-07-03 15:48:08 Created by tomasriker on 2018-04-19 04:50:00 Original: https://sourceforge.net/p/maxima/bugs/3147/#e1db

---

Fixed by commit [78a894].

[rtoy]

Imported from SourceForge on 2024-07-03 15:48:11 Created by tomasriker on 2018-04-19 04:50:33 Original: https://sourceforge.net/p/maxima/bugs/3147/#ebe5

---

• status: open --> closed