[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: "Paulo J. Matos" <pocm@rnl.ist.utl.pt>*Subject*: Re: [plt-scheme] Divisions*From*: Jens Axel Søgaard <jensaxel@soegaard.net>*Date*: Sat, 1 Jun 2002 19:47:26 +0200*Cc*: <plt-scheme@fast.cs.utah.edu>, "Paulo J. Matos" <pocm@rnl.ist.utl.pt>*References*: <873cw7j535.fsf@localhost.localdomain><p05111701b91e6d6ee1a1@[10.0.1.5]><037801c20974$b8e580e0$0500000a@Lr30JS><87r8jrgf3n.fsf@localhost.localdomain><043501c2098c$7a0bcba0$0500000a@Lr30JS> <87it52ewmg.fsf@localhost.localdomain>*Sender*: owner-plt-scheme@fast.cs.utah.edu

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

**References**:**[plt-scheme] Divisions***From:*pocm@rnl.ist.utl.pt (Paulo J. Matos)

**Re: [plt-scheme] Divisions***From:*John Clements <clements@brinckerhoff.org>

**Re: [plt-scheme] Divisions***From:*Jens Axel Søgaard <jensaxel@soegaard.net>

**Re: [plt-scheme] Divisions***From:*pocm@rnl.ist.utl.pt (Paulo J. Matos)

**Re: [plt-scheme] Divisions***From:*Jens Axel Søgaard <jensaxel@soegaard.net>

**Re: [plt-scheme] Divisions***From:*pocm@rnl.ist.utl.pt (Paulo J. Matos)

- Prev by Date:
**Re: [plt-scheme] Divisions** - Next by Date:
**[plt-scheme] where to put extensions?** - Prev by thread:
**Re: [plt-scheme] Divisions** - Next by thread:
**[plt-scheme] where to put extensions?** - Index(es):