Dear All,   
      
   Here is a little trick to speed up polynomial exponentiation.   
   I am using a non-whole approach combined with binary exponentiation.   
   Not much words need to be spread for binary exponentiation.   
      
   On the other hand the non-whole approach followed here is very   
   simple. The problem is to square a polynomial   
      
      p(x) = a0 + a1*x + ... an*x^n   
      
   The coefficients can be again polynomials or constant values.   
   Now it can happen that some of the coefficients are constant zero.   
   In the extrem case only an is non-zero, and we have:   
      
      p(x) = an*x^n   
      
   We can quickly compute the square as:   
      
      p(x)^2 = an^2*x^(2*n)   
      
   In the non-extrem case, the polynomial can be split into two   
   polynomials p1(x) and p2(x) that are not constant zero, because   
   it is the non-extrem case, and we have:   
      
      p(x) = p1(x) + p2(x)   
      
   We can quickly compute the square as:   
      
      p(x)^2 = p1(x)^2 + 2*p1(x)*p2(x) + p2(x)^2   
      
   What is the effort for this new square. Observe that we recurse   
   into squaring subproblems p1(x)^2 and p2(x)^2. The whole square   
   approach has effort of the order:   
      
      n^2   
      
   the here presented non-whole square has the following   
   recurrence relation for the effort E(n):   
      
      E(n) 	= E(n/2) + E(n/2) + n/2 * n/2		   
      
                   = 2*E(n/2) + n2/4   
      
   		= Σi=1k 2i-1*n2/4i			   
      
                   = n2 Σi=1k 2-i-1   
      
   		< n2/2   
      
   So the non-whole approach should be twice as fast. Lets see what   
   we empircally get in our Prolog prototype:   
      
   Performance in the Whole Approach   
      
   ?- P is 1000+V+W+X+Y, time(_ is P^20).   
   % Up 16,529 ms, GC 2,262 ms, Thread Cpu 14,281 ms (Current 07/10/17 12:20:51)   
   P is 1000+V+W+X+Y   
      
   Performance in the Non-Whole Approach   
      
   ?- P is 1000+V+W+X+Y, time(_ is P^20).   
   % Up 7,236 ms, GC 400 ms, Thread Cpu 6,828 ms (Current 07/10/17 12:39:29)   
   P is 1000+V+W+X+Y   
      
   You see I can let Professor Richard Fateman work for me.    
   But the reference I used was this here, for the terminology,   
   but the idea was borrowed from my radical datatype:   
      
   The Computation of Powers ofSymbolic Polynomials   
   ELLIS HOROWITZ, SARTAJ SAHNI, SIAM Vol 4 No 1, June 1975   
   https://www.researchgate.net/publication/220617540_The_Computati   
   n_of_Powers_of_Symbolic_Polynomials   
      
   I have already pushed the code to GitHub. Since Prolog   
   is very nice for fast prototyping, it took me not that   
   much time to implement the improvement:   
      
   https://github.com/jburse/jekejeke-devel/commit/3fc13373658a0c5a   
   f7f8439ed60c0f6dd29f4dc#diff-fb018ac08cd1486a53e839c0f41611cdL204   
      
   On GitHub you can also view the history (delta of all   
   the pushes), I don't know whether SourceForge can do that,    
   if I remember well it does not have such a feature.   
      
   So let me continue in my quest to beat maxima.   
      
   Best Regards   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)