On Tue, 22 Mar 2011 02:08:39 +0100, dsimcha <[email protected]> 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. -- Simen
