Re: [plt-scheme] Divisions

[Jens Axel Søgaard <jensaxel@soegaard.net>]

Paulo J. Matos wrote:
> Anyway, do you think that calling from source GCD-
> Extended from GMP will give us better results?

I was just coming to that :-)

You are using the standard Euclidean algorithm to
find the coeffecients. Now, I remembered that
Knuth mentioned that Stein in 1961 (Ok - I couldn't
remember the year) conceived the binary gcd algorithm,
which is 20% faster in average.

Finding my notes I tried to figure out a way to use this method
to find the coeffecients, but had troubles in the case
where  the numbers had different parity. I gave up and looked
in Knuth. It turns out that he mentions yet another gcd algorithm
namely the Lehmer algorithm. For very large numbers it works
only on the leading digits and can therefore replace som
multiprecision operations with some single precisíon brothers.

Checking the GMP manual, it turns out that GMP uses the
Lehmer algorithm also for the extended gcd algorithm.
I therefore believe that the GMP version will be faster,
but proably only noticeably on large [whatever that means]
numbers.

Now after the Lehmer algorithm Knuth mentions that using the same
trick the binary algorithm can also be improved - and that it'll
be faster than Lehmers. However, he leaves these improved
algoriths to two exercices. Undoubtly the reason that they are
not implemented in GMP :-)

Yours,
Jens Axel Søgaard

Denmark 2 - 1 Uruguay
http://fifaworldcup.yahoo.com/en/020601/2/obk.html