[GiNaC-devel] infinite loop in simplify_indexed()

[Alexei Sheplyakov]

Hello,

On Sun, May 15, 2011 at 10:22:27PM +0200, Jens Vollinga wrote:

> it seems GiNaC tries to loop over all 9! index permutations inside
> symm() in symmetry.cpp ... is that a good idea?!?

I don't think it's a good idea. Still I don't think a sum of 362880 terms
is really a big deal.

> Currently, I have no idea what to do about it.

The patch below (drastically) improves the run time at the expense of using
more RAM in some situations. Please note: it doesn't improve the actual
algorithm (iteration over all permutations).

diff --git a/ginac/symmetry.cpp b/ginac/symmetry.cpp
index 7d1ff97..d93e34c 100644
--- a/ginac/symmetry.cpp
+++ b/ginac/symmetry.cpp
@@ -22,6 +22,7 @@
 
 #include "symmetry.h"
 #include "lst.h"
+#include "add.h"
 #include "numeric.h" // for factorial()
 #include "operators.h"
 #include "archive.h"
@@ -495,7 +496,8 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite
 
 	// Loop over all permutations (the first permutation, which is the
 	// identity, is unrolled)
-	ex sum = e;
+	exvector sum_v;
+	sum_v.push_back(e);
 	while (std::next_permutation(iv, iv + num)) {
 		lst new_lst;
 		for (unsigned i=0; i<num; i++)
@@ -505,8 +507,9 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite
 			memcpy(iv2, iv, num * sizeof(unsigned));
 			term *= permutation_sign(iv2, iv2 + num);
 		}
-		sum += term;
+		sum_v.push_back(term);
 	}
+	ex sum = (new add(sum_v))->setflag(status_flags::dynallocated);
 
 	delete[] iv;
 	delete[] iv2;


Best regards,
	Alexei

P.S. The bug has nothing to do with infinite loops.