- pseries::coeff() now uses a binary instead of a linear search algorithm

diff --git a/ginac/normal.cpp b/ginac/normal.cpp
index d7557bdc727debaca44547b7db0310d39555370b..a5ebeb8b691ee4b6d95355fff45a17d68d87a414 100644 (file)
--- a/ginac/normal.cpp
+++ b/ginac/normal.cpp
@@ -1101,6 +1101,8 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const
 
 ex gcd(const ex &a, const ex &b, ex *ca, ex *cb, bool check_args)
 {
 
 ex gcd(const ex &a, const ex &b, ex *ca, ex *cb, bool check_args)
 {

+//clog << "gcd(" << a << "," << b << ")\n";
+

        // Partially factored cases (to avoid expanding large expressions)
        if (is_ex_exactly_of_type(a, mul)) {
                if (is_ex_exactly_of_type(b, mul) && b.nops() > a.nops())
        // Partially factored cases (to avoid expanding large expressions)
        if (is_ex_exactly_of_type(a, mul)) {
                if (is_ex_exactly_of_type(b, mul) && b.nops() > a.nops())

diff --git a/ginac/pseries.cpp b/ginac/pseries.cpp
index 4491915841b1cd746d32cde71c8effc395257d4c..87d0e4377a6ccbb3023723759b5c6be3773b45d8 100644 (file)
--- a/ginac/pseries.cpp
+++ b/ginac/pseries.cpp
@@ -242,16 +242,30 @@ int pseries::ldegree(const symbol &s) const
 ex pseries::coeff(const symbol &s, int n) const
 {
     if (var.is_equal(s)) {
 ex pseries::coeff(const symbol &s, int n) const
 {
     if (var.is_equal(s)) {

-        epvector::const_iterator it = seq.begin(), itend = seq.end();
-        while (it != itend) {
-            int pow = ex_to_numeric(it->coeff).to_int();
-            if (pow == n)
-                return it->rest;
-            if (pow > n)
-                return _ex0();
-            it++;
-        }
-        return _ex0();
+               if (seq.size() == 0)
+                       return _ex0();
+
+               // Binary search in sequence for given power
+               numeric looking_for = numeric(n);
+               int lo = 0, hi = seq.size() - 1;
+               while (lo <= hi) {
+                       int mid = (lo + hi) / 2;
+                       GINAC_ASSERT(is_ex_exactly_of_type(seq[mid].coeff, numeric));
+                       int cmp = ex_to_numeric(seq[mid].coeff).compare(looking_for);
+                       switch (cmp) {
+                               case -1:
+                                       lo = mid + 1;
+                                       break;
+                               case 0:
+                                       return seq[mid].rest;
+                               case 1:
+                                       hi = mid - 1;
+                                       break;
+                               default:
+                                       throw(std::logic_error("pseries::coeff: compare() didn't return -1, 0 or 1"));
+                       }
+               }
+               return _ex0();

     } else
         return convert_to_poly().coeff(s, n);
 }
     } else
         return convert_to_poly().coeff(s, n);
 }