From 6564c3b961f7e0b69c20187b56f90d86d4fdcb9a Mon Sep 17 00:00:00 2001 From: Christian Bauer Date: Wed, 1 Mar 2000 20:51:01 +0000 Subject: [PATCH] - pseries::coeff() now uses a binary instead of a linear search algorithm --- ginac/normal.cpp | 2 ++ ginac/pseries.cpp | 34 ++++++++++++++++++++++++---------- 2 files changed, 26 insertions(+), 10 deletions(-) diff --git a/ginac/normal.cpp b/ginac/normal.cpp index d7557bdc..a5ebeb8b 100644 --- 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) { +//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()) diff --git a/ginac/pseries.cpp b/ginac/pseries.cpp index 44919158..87d0e437 100644 --- 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)) { - 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); } -- 2.44.0