Anything in the review queue?

[Don]

Simen kjaeraas wrote:
> 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.
> 

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.