Anything in the review queue?

[Simen kjaeraas]

On Tue, 22 Mar 2011 02:08:39 +0100, dsimcha <dsimcha at 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.

-- 
Simen