This code used to cause an infinite loop that eventually killed Axiom.
The bug exists in the intef.spad, in ElementaryIntegration (INTEF),
in the routines lfextendedint and lflimitedint.
The input
integrate((z^a+1)^b,z)
triggers the bug because of line 2 of each function.
Line 2 of these functions used to read:
symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
The loop occurs when the call to union causes
a log(z)
%e
to get added to the list every time. This gives the argument to kmax
a log(z)
arg1= [z,%e ]
and the result being
a log(z)
%e
We keep coming back to process this term, which ends up
putting the same term back on the list and we loop.
Waldek's solution is to remove the union call.
If we look at the original problem we see:
integrate((z^a+1)^b,z)
z
++ a b
(1) | (%I + 1) d%I
++
Type: Union(Expression Integer,...)
and if we replace %I by z we get the original expression
z
++ a b
| (z + 1) dz
++
=========================================================================
diff --git a/changelog b/changelog
index d6c0bdd..9baab4b 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,7 @@
+20070915 tpd merge bug100 branch
+20070915 tpd src/input/Makefile add bug100.input regression test
+20070915 tpd src/input/bug100.input test integrate((z^a+1)^b,z) infinite loop
+20070915 wxh src/algebra/intef.spad fix integrate((z^a+1)^b,z) infinite loop
20070915 tpd src/algebra/carten minor edit for regression cleanup
20070914 wxh src/hyper/hyper fix bad bracing of )hd change
20070914 tpd src/algebra/fraction.spad remove double )spool command
diff --git a/src/algebra/intef.spad.pamphlet b/src/algebra/intef.spad.pamphlet
index 4dbbc26..955d284 100644
--- a/src/algebra/intef.spad.pamphlet
+++ b/src/algebra/intef.spad.pamphlet
@@ -227,9 +227,41 @@ ElementaryIntegration(R, F): Exports == Implementation
where
algint(f, t, y, differentiate(#1, differentiate(#1, x),
differentiate(t::F, x)::UP))
+@
+Bug \#100 is an infinite loop that eventually kills Axiom
+from the input
+\begin{verbatim}
+ integrate((z^a+1)^b,z)
+\end{verbatim}
+
+Line 2 of this function used to read:
+\begin{verbatim}
+ symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+\end{verbatim}
+
+The loop occurs when the call to union causes
+\begin{verbatim}
+ a log(z)
+ %e
+\end{verbatim}
+to get added to the list every time. This gives the argument to kmax
+\begin{verbatim}
+ a log(z)
+ arg1= [z,%e ]
+\end{verbatim}
+and the result being
+\begin{verbatim}
+ a log(z)
+ %e
+\end{verbatim}
+We keep coming back to process this term, which ends up
+putting the same term back on the list and we loop.
+Waldek's solution is to remove the union call.
+
+<<package INTEF ElementaryIntegration>>=
lfextendedint(f, x, g) ==
empty?(l := varselect(kernels f, x)) => [x::F * f, 0]
- symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+ symbolIfCan(k := kmax(l))
case SE =>
map(multivariate(#1, k), extendedint(univariate(f, k),
univariate(g, k)))
@@ -238,9 +270,16 @@ ElementaryIntegration(R, F): Exports == Implementation
where
has?(operator k, ALGOP) => alglfextint(f, k, l, x, g)
unkextint(f, x, g)
+@
+This is part of the fix for bug 100. Line 2 of this function used to read:
+\begin{verbatim}
+ symbolIfCan(k := kmax(l := union(l, vark(lu, x)))) case SE =>
+\end{verbatim}
+See the above discussion for why this causes an infinite loop.
+<<package INTEF ElementaryIntegration>>=
lflimitedint(f, x, lu) ==
empty?(l := varselect(kernels f, x)) => [x::F * f, empty()]
- symbolIfCan(k := kmax(l := union(l, vark(lu, x)))) case SE =>
+ symbolIfCan(k := kmax(l)) case SE =>
map(multivariate(#1, k), limitedint(univariate(f, k),
[univariate(u, k) for u in lu]))
is?(k, "exp"::SE) => explimint(f, x, k, lu)
diff --git a/src/input/Makefile.pamphlet b/src/input/Makefile.pamphlet
index 16a3b98..92c1dc5 100644
--- a/src/input/Makefile.pamphlet
+++ b/src/input/Makefile.pamphlet
@@ -287,7 +287,7 @@ REGRES= algaggr.regress algbrbf.regress algfacob.regress
alist.regress \
arrows.regress assign.regress atansqrt.regress \
asec.regress bags.regress bbtree.regress \
binary.regress bop.regress bstree.regress bouquet.regress \
- bug10069.regress \
+ bug100.regress bug10069.regress \
bugs.regress bug10312.regress bug6357.regress bug9057.regress \
calcprob.regress \
calculus2.regress calculus.regress cardinal.regress card.regress \
@@ -502,7 +502,8 @@ FILES= ${OUT}/algaggr.input ${OUT}/algbrbf.input
${OUT}/algfacob.input \
${OUT}/bags.input ${OUT}/bbtree.input ${OUT}/bern.input \
${OUT}/bernpoly.input ${OUT}/binary.input ${OUT}/bop.input \
${OUT}/bouquet.input ${OUT}/bstree.input ${OUT}/bug6357.input \
- ${OUT}/bug9057.input ${OUT}/bug10069.input ${OUT}/bug10312.input \
+ ${OUT}/bug9057.input ${OUT}/bug100.input \
+ ${OUT}/bug10069.input ${OUT}/bug10312.input \
${OUT}/calcprob.input ${OUT}/calculus.input \
${OUT}/cardinal.input ${OUT}/card.input ${OUT}/carten.input \
${OUT}/cclass.input ${OUT}/cdraw.input ${OUT}/char.input \
@@ -677,6 +678,7 @@ DOCFILES= \
${DOC}/bernpoly.input.dvi ${DOC}/binary.input.dvi \
${DOC}/bop.input.dvi ${DOC}/bouquet.input.dvi \
${DOC}/bstree.input.dvi ${DOC}/bug10069.input.dvi \
+ ${DOC}/bug100.input.dvi \
${DOC}/bug10312.input.dvi ${DOC}/bug6357.input.dvi \
${DOC}/bug9057.input.dvi ${DOC}/bugs.input.dvi \
${DOC}/c02aff.input.dvi ${DOC}/c02agf.input.dvi \
diff --git a/src/input/bug100.input.pamphlet b/src/input/bug100.input.pamphlet
new file mode 100644
index 0000000..799d339
--- /dev/null
+++ b/src/input/bug100.input.pamphlet
@@ -0,0 +1,80 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/input bug100.input}
+\author{Timothy Daly}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+@
+This code used to cause an infinite loop that eventually killed Axiom.
+The bug exists in the {\tt intef.spad}, in ElementaryIntegration (INTEF),
+in the routines {\tt lfextendedint} and {\tt lflimitedint}.
+
+The input
+\begin{verbatim}
+ integrate((z^a+1)^b,z)
+\end{verbatim}
+triggers the bug because of line 2 of each function.
+Line 2 of these functions used to read:
+\begin{verbatim}
+ symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+\end{verbatim}
+
+The loop occurs when the call to union causes
+\begin{verbatim}
+ a log(z)
+ %e
+\end{verbatim}
+to get added to the list every time. This gives the argument to kmax
+\begin{verbatim}
+ a log(z)
+ arg1= [z,%e ]
+\end{verbatim}
+and the result being
+\begin{verbatim}
+ a log(z)
+ %e
+\end{verbatim}
+We keep coming back to process this term, which ends up
+putting the same term back on the list and we loop.
+Waldek's solution is to remove the union call.
+
+<<*>>=
+)spool bug100.output
+)set message test on
+)set message auto off
+)clear all
+
+--S 1 of 1
+integrate((z^a+1)^b,z)
+--R
+--R z
+--R ++ a b
+--R (1) | (%I + 1) d%I
+--R ++
+--R Type: Union(Expression
Integer,...)
+--E 1
+@
+If we substitute z for %I we get:
+\begin{verbatim}
+ z
+ ++ a b
+ | (z + 1) dz
+ ++
+
+\end{verbatim}
+which is the original input integral.
+<<*>>=
+)spool
+)lisp (bye)
+
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}
_______________________________________________
Axiom-developer mailing list
Axiom-developer@nongnu.org
http://lists.nongnu.org/mailman/listinfo/axiom-developer
