Simen kjaeraas wrote:
On Tue, 22 Mar 2011 02:08:39 +0100, dsimcha <dsim...@yahoo.com> wrote:
The biggest perf issue, though, seems to be Euler's algorithm instead
of BinaryGCD. This is definitely going to get fixed eventually by me,
since I've read up on BinaryGCD and it doesn't look hard to implement
generically. I naively thought Euler's algorithm was pretty darn
efficient when I wrote the first version, not knowing much about how
BigInts work under the hood. I'm not sure if Don had something even
more efficient than a good generic BinaryGCD implementation in mind,
or if there are other areas where a templated Rational is a Bad Idea,
though.
The algorithmic complexity is the same for BinaryGCD as it is for normal
GCD. What Don had in mind was sub-quadratic. Might have been something
from this paper:
http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf
Page 10 onwards claims subquadratic performance.
Yes, and there's been a couple of improved algorithmic tweaks since
then. The best algorithms are described in "Modern Computer Arithmetic"
which was published just a few months back.
But this stuff doesn't really matter terribly much, as these algorithms
are only beneficial for very large numbers. The most important thing,
really, is to avoid Euclid's algorithm.
