[Maxima] SERIOUS simpsum bug

Martin RUBEY rubey@labri.fr
Sat, 23 Nov 2002 20:11:24 +0100 (CET)


I finally got around to debug the simpsum bug I encountered some time ago.  
I found strange stuff, for example:

(C1) 'sum(1+f(k),k,1,2),simpsum;

(D1) 				      2

The reason for this can be found in combin.lisp:

(C1) trace(?sumsum,?sum,?fbino,?fsgeo);

(D1)                      [SUMSUM, SUM, FBINO, FSGEO]
(C2) trace_options(?sum,lisp_print);

(D2)                             [LISP_PRINT]
(C3)  'SUM(1+f(k),k,1,2),simpsum;

1 Enter ?SUMSUM [f(k) + 1, k, 1, 2]

 (1 ENTER SUM (((MPLUS SIMP) 1 ((|$f| SIMP) |$k|)) 1))
  (2 ENTER SUM (1 1))
  (2 EXIT SUM (2))
  (2 ENTER SUM (((|$f| SIMP) |$k|) 1))
  (2 EXIT SUM NIL)
 (1 EXIT SUM (1 ((|$f| SIMP) |$k|)))
1 Exit  ?SUMSUM FALSE
(D3)                                   2
(C4)

so it seems that sum((|$f| SIMP) |$k|) 1)) returns nil, because it does
not know how to deal with f(k)...

Unfortunately, I do not know how to debug the lisp source efficiently. Do 
I really have to do make in src? I did not manage to simply load all files 
as in gcl-depends into gcl... Also, I do not understand the code below 
very well. It seems to me that all the results sum finds are stuffed into 
a list (which is also called sum ?) and sumsum then adds them up. Is this 
correct? If this is the case, I really would have to watch the value of 
sum...

There is a second issue I found: in the line after (*), there is an
obvious check for linearity. However, it does break sum(f(k)+2*g(k)) only
into sum(f(k)) and sum(2*g(k)), not into sum(f(k)) and 2*sum(g(k)) which
does make some difference - for example, when g(k) is a binomial
coefficient, then the sum calls fsgeo, not fbino...

------------------ snip of combin.lisp -----------------------

(defun sum (e y)
  (cond ((null e))
	((free e *var*)
	 (adsum (m* y e (m+ hi 1 (m- lo)))))
	((poly? e *var*)
	 (adsum (m* y (fpolysum e))))
	((eq (caar e) '%binomial) (fbino e y))
;;;; (*) check for linearity:
	((eq (caar e) 'mplus)
	 (mapc #'(lambda (q) (sum q y)) (cdr e)))
	((and (or (mtimesp e) (mexptp e) (mplusp e))
	      (fsgeo e y)))
	(t
	 nil
	 #-cl
	 (let (*a *n)
	     (cond ((prog2 (m2 e '((mtimes) ((coefftt) (var* (set) *a 
freevar))
					    ((coefftt) (var* (set) *n 
true)))
			       nil)
			   (not (equal *a 1)))
		    (sum *n (list '(mtimes) y *a)))
		   ((and (not (atom
			       (setq *n
				     ($ratdisrep
				      (let (genvar (varlist (cons *var* 
nil)))
					(ratrep* *n))))))
			 (not (equal *n e))
			 (not (eq (caar *n) 'mtimes)))
		    (sum *n (list '(mtimes) y *a)))
		   (t (adusum (list '(mtimes) e y))))))))

----------------end snip of combin.lisp -----------------------

Finally, I'd like to ask why simpsum does not call the Gosper algorithm
(nusum)? I guess that simpsum is only called on demand, when the user
REALLY wants to have a simple answer and believes that there is one? And
as far as I know, Zeilberger (and for multiple sums Wegschaider) is at the
moment the most powerful algorithm.

So, put in another way: does it make sense to maintain the simpsum code if 
there are more powerful algorithms available? 


On Fri, 18 Oct 2002, Martin RUBEY wrote:

> Hi!
> 
> Unfortunately I have found a bug in simpsum (it seems):
> 
> (C1) 'SUM(BINOMIAL(2,2-k)-BINOMIAL(2,1-k),k,1,2),simpsum;
> 
> (D1) 				       3
> 
> ***************** wrong **********************
> 
> (C2) 'SUM(BINOMIAL(2,2-k)-BINOMIAL(2,1-k),k,1,2),sum;
> 
> (D2) 				       2
> 
> ***************** correct ********************
> 
> ***************** however : ******************
> 
> (C3) 'SUM(BINOMIAL(x,2-k)-BINOMIAL(x,1-k),k,1,2),simpsum;
> 
> (D3) 				       x
> 
> (C4) 'SUM(BINOMIAL(x,2-k)-BINOMIAL(x,1-k),k,1,2),sum;
> 
> (D4) 				       x
> (C5) bug_report();
> 
> 
> The Maxima bug database is available at
>     http://sourceforge.net/tracker/?atid=104933&group_id=4933&func=browse
> Submit bug reports by following the 'Submit New' link on that page.
> Please include the following build information with your bug report:
> -------------------------------------------------------------
> 
> Maxima version: 5.9.0rc1
> Maxima build date: 11:40 9/3/2002
> host type: i686-pc-linux-gnu
> lisp-implementation-type: Kyoto Common Lisp
> lisp-implementation-version: GCL-2-5.0
> 
> -------------------------------------------------------------
> 
> Martin
> 
> _______________________________________________
> Maxima mailing list
> Maxima@www.math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>