From b1da89e057fea6f9c9c6e32bd92ecb5980b6713a Mon Sep 17 00:00:00 2001 From: Christian Bauer Date: Mon, 28 May 2001 22:16:47 +0000 Subject: [PATCH] - dirac_trace() is twice as fast - permutation_sign() uses shaker sort - shaker_sort() doesn't require less-than comparable iterators any more --- ginac/clifford.cpp | 128 +++++++++++++++++++-------------------- ginac/indexed.cpp | 6 +- ginac/inifcns.cpp | 5 +- ginac/utils.h | 146 +++++++++++++++++++++++++++++++-------------- 4 files changed, 168 insertions(+), 117 deletions(-) diff --git a/ginac/clifford.cpp b/ginac/clifford.cpp index b5dff072..3af4fcae 100644 --- a/ginac/clifford.cpp +++ b/ginac/clifford.cpp @@ -345,6 +345,42 @@ static bool is_clifford_tinfo(unsigned ti) return (ti & ~0xff) == TINFO_clifford; } +/** Take trace of a string of an even number of Dirac gammas given a vector + * of indices. */ +static ex trace_string(exvector::const_iterator ix, unsigned num) +{ + // Tr gamma.mu gamma.nu = 4 g.mu.nu + if (num == 2) + return lorentz_g(ix[0], ix[1]); + + // Tr gamma.mu gamma.nu gamma.rho gamma.sig = 4 (g.mu.nu g.rho.sig + g.nu.rho g.mu.sig - g.mu.rho g.nu.sig + else if (num == 4) + return lorentz_g(ix[0], ix[1]) * lorentz_g(ix[2], ix[3]) + + lorentz_g(ix[1], ix[2]) * lorentz_g(ix[0], ix[3]) + - lorentz_g(ix[0], ix[2]) * lorentz_g(ix[1], ix[3]); + + // Traces of 6 or more gammas are computed recursively: + // Tr gamma.mu1 gamma.mu2 ... gamma.mun = + // + g.mu1.mu2 * Tr gamma.mu3 ... gamma.mun + // - g.mu1.mu3 * Tr gamma.mu2 gamma.mu4 ... gamma.mun + // + g.mu1.mu4 * Tr gamma.mu3 gamma.mu3 gamma.mu5 ... gamma.mun + // - ... + // + g.mu1.mun * Tr gamma.mu2 ... gamma.mu(n-1) + exvector v(num - 2); + int sign = 1; + ex result; + for (int i=1; i iv; - iv.reserve(num-1); + ex idx4 = ix[l]; + iv[0] = i; iv[1] = j; iv[2] = k; iv[3] = l; exvector v; - v.reserve(num-1); - iv.push_back(i); iv.push_back(j); iv.push_back(k); iv.push_back(l); - for (int n=1; n 2 && (symmetry != unknown && symmetry != mixed)) { - exvector v = seq; + if (seq.size() > 2 && (symmetry == symmetric || symmetry == antisymmetric)) { + exvector v(seq); int sig = canonicalize_indices(v.begin() + 1, v.end(), symmetry == antisymmetric); if (sig != INT_MAX) { // Something has changed while sorting indices, more evaluations later diff --git a/ginac/inifcns.cpp b/ginac/inifcns.cpp index 26672154..beb51d62 100644 --- a/ginac/inifcns.cpp +++ b/ginac/inifcns.cpp @@ -533,10 +533,9 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite // Sort object vector, transform it into a list, and make a copy so we // will know which objects get substituted for which - exvector iv(first, last); - sort(iv.begin(), iv.end(), ex_is_less()); exlist iv_lst; - iv_lst.insert(iv_lst.begin(), iv.begin(), iv.end()); + iv_lst.insert(iv_lst.begin(), first, last); + shaker_sort(iv_lst.begin(), iv_lst.end(), ex_is_less()); lst orig_lst(iv_lst); // With n objects there are n! possible permutations diff --git a/ginac/utils.h b/ginac/utils.h index efdeaa2b..c0bc2efe 100644 --- a/ginac/utils.h +++ b/ginac/utils.h @@ -128,68 +128,111 @@ inline unsigned golden_ratio_hash(unsigned n) } /* Compute the sign of a permutation of a container, with and without an - explicitly supplied comparison function. The containers gets modified - during the operation. */ + explicitly supplied comparison function. If the sign returned is 1 or -1, + the container is sorted after the operation. */ template -int permutation_sign(It first, It last) +inline int permutation_sign(It first, It last) { if (first == last) return 0; - It i = first; - ++i; - if (i == last) + --last; + if (first == last) return 0; - i = first; - It next_to_last = last; - --next_to_last; - + It flag = first; int sign = 1; - while (i != next_to_last) { - It j = i; - ++j; - while (j != last) { - if (!(*i < *j)) { - if (!(*j < *i)) - return 0; - iter_swap(i, j); + + do { + It i = last, other = last; + --other; + bool swapped = false; + while (i != first) { + if (*i < *other) { + iter_swap(other, i); + flag = other; + swapped = true; sign = -sign; - } - ++j; + } else if (!(*other < *i)) + return 0; + --i; --other; + } + if (!swapped) + return sign; + ++flag; + if (flag == last) + return sign; + first = flag; + i = first; other = first; + ++other; + swapped = false; + while (i != last) { + if (*other < *i) { + iter_swap(i, other); + flag = other; + swapped = true; + sign = -sign; + } else if (!(*i < *other)) + return 0; + ++i; ++other; } - ++i; - } + if (!swapped) + return sign; + last = flag; + --last; + } while (first != last); + return sign; } -/** Compute the sign of a permutation of a container */ template -int permutation_sign(It first, It last, Cmp comp) +inline int permutation_sign(It first, It last, Cmp comp) { if (first == last) return 0; - It i = first; - ++i; - if (i == last) + --last; + if (first == last) return 0; - i = first; - It next_to_last = last; - --next_to_last; - + It flag = first; int sign = 1; - while (i != next_to_last) { - It j = i; - ++j; - while (j != last) { - if (!comp(*i, *j)) { - if (!comp(*j, *i)) - return 0; - iter_swap(i, j); + + do { + It i = last, other = last; + --other; + bool swapped = false; + while (i != first) { + if (comp(*i, *other)) { + iter_swap(other, i); + flag = other; + swapped = true; sign = -sign; - } - ++j; + } else if (!comp(*other, *i)) + return 0; + --i; --other; } - ++i; - } + if (!swapped) + return sign; + ++flag; + if (flag == last) + return sign; + first = flag; + i = first; other = first; + ++other; + swapped = false; + while (i != last) { + if (comp(*other, *i)) { + iter_swap(i, other); + flag = other; + swapped = true; + sign = -sign; + } else if (!comp(*i, *other)) + return 0; + ++i; ++other; + } + if (!swapped) + return sign; + last = flag; + --last; + } while (first != last); + return sign; } @@ -203,30 +246,41 @@ inline void shaker_sort(It first, It last, Cmp comp) if (first == last) return; It flag = first; + do { It i = last, other = last; --other; - while (i > first) { + bool swapped = false; + while (i != first) { if (comp(*i, *other)) { iter_swap(other, i); flag = other; + swapped = true; } --i; --other; } + if (!swapped) + return; ++flag; + if (flag == last) + return; first = flag; i = first; other = first; ++other; - while (i < last) { + swapped = false; + while (i != last) { if (comp(*other, *i)) { iter_swap(i, other); flag = other; + swapped = true; } ++i; ++other; } + if (!swapped) + return; last = flag; --last; - } while (first <= last); + } while (first != last); } /* Function objects for STL sort() etc. */ -- 2.44.0