[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
>