#5621 trigreduce runs away on a trigonometric quotient whose coefficient is %i or sqrt(2)

[David Scherfgen]

By Claude:

trigreduce takes more than 100 times longer and returns a result about 40 times larger on a small rational trigonometric expression when one of its coefficients is %i or a root of a number such as sqrt(2), compared with the same expression with a symbol or %pi in that place. On slightly larger inputs it exhausts the heap. Maxima 5.50post, master 3f6fc653d, SBCL 2.6.8:

(%i1) display2d:false
(%i2) D:%i*sin(x)+cos(x)+1
(%i3) N:%i*sin(x)+cos(x)-1
(%i4) e:((cos(x)*N)/D^2-cos(x)/D)/N
(%i5) showtime:true
Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes.
(%i6) slength(string(trigreduce(e)))
Evaluation took 4.5938 seconds (4.6520 elapsed) using 1990.093 MB.
(%o6) 70986
(%i7) slength(string(trigreduce(subst(%i = c,e))))
Evaluation took 0.0329 seconds (0.0400 elapsed) using 14.961 MB.
(%o7) 1723
(%i8) slength(string(trigreduce(subst(%i = %pi,e))))
Evaluation took 0.0289 seconds (0.0280 elapsed) using 15.058 MB.
(%o8) 1927
(%i9) slength(string(trigreduce(subst(%i = sqrt(2),e))))
Evaluation took 5.5060 seconds (5.6080 elapsed) using 2552.549 MB.
(%o9) 108592
(%i10) slength(string(trigreduce(ratsimp(e))))
Evaluation took 0.0020 seconds (0.0000 elapsed) using 1023.594 KB.
(%o10) 322

The 70986-character result is correct (it agrees with e numerically), but e is just -2*cos(x)/(D^2*N): the size and the cost are the problem. Nothing about the expression forces them, since the result for a symbol c with %i substituted afterwards is a valid answer, and trigreduce(ratsimp(e)) gives 322 characters in 2 ms.

It gets worse with one more level of nesting:

D : %i*sin(x)+cos(x)+1$
N : %i*sin(x)+cos(x)-1$
R : (%i*cos(x)-sin(x))/D-(D*((%i*cos(x)-sin(x))*N/D^2-(%i*cos(x)-sin(x))/D))/N$
trigreduce(R);
trigreduce(x*R);

R with %i replaced by	time (whole process)	result, characters
c	0.7 s	1439
%pi	0.6 s	1621
2	0.6 s	1338
%i	17.1 s	187161
sqrt(2)	25.8 s	1466574
2^(1/3)	Heap exhausted, game over. after 4.5 s

trigreduce(x*R) exhausts the default 1 GiB heap after 33 s.

The coefficients that blow up are exactly those whose powers simplify to numbers (%i^2, sqrt(2)^2, (2^(1/3))^3); a symbol and %pi do not. Counting calls to SP1TIMES in src/trgred.lisp for e: 2002 with c or %pi, 207807 with %i, 216686 with sqrt(2).

Possibly related: #5128 and #5207, where the cost grows exponentially with nesting depth. Here the nesting is shallow, and the same expression with a symbol in place of %i is fast.