[OT] GCD Algorithm

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[OT] GCD Algorithm

hernan.wilkinson
Hi,
 th


Reply | Threaded
Open this post in threaded view
|

[OT] GCD Algorithm

hernan.wilkinson
Sorry... I pressed the wrong button...
I wanted to ask for faster implementations of the GCD algorithm than the Euclid's one.
We found on the web that the Lehmer's and the Binary GCD are faster... has anyone experience on that? are they really faster? has anyone have a implementation in Smalltalk? (or similar language like C++ :-)  )

Thanks is advance and sorry to bother you people with this.
Hernan.

On 4/20/07, Hernan Wilkinson <[hidden email]> wrote:
Hi,
 th



Reply | Threaded
Open this post in threaded view
|

Re: [OT] GCD Algorithm

Nicolas Cellier-3
Hi Hernan,

Lehmer is faster than Euclid algorithm only for large integers.
According to papers for (u gcd: v) you can expect a (n log: 2)
improvement factor where n is the number of bits (u abs highBit min: v
abs highBit).

For huge integers for which FFT product algorithm is efficient, you can
even get better, but at the cost of algorithm complexity.

However, if you look at squeak Integer>>#gcd: you will find that it is
not the naive Euclid algorithm, but rather some form of Lehmer's, so
don't expect much gain (unless you connect gnuMP library).

Nicolas

Hernan Wilkinson a écrit :

> Sorry... I pressed the wrong button...
> I wanted to ask for faster implementations of the GCD algorithm than the
> Euclid's one.
> We found on the web that the Lehmer's and the Binary GCD are faster...
> has anyone experience on that? are they really faster? has anyone have a
> implementation in Smalltalk? (or similar language like C++ :-)  )
>
> Thanks is advance and sorry to bother you people with this.
> Hernan.
>
> On 4/20/07, *Hernan Wilkinson* < [hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hi,
>      th
>
>
>
> ------------------------------------------------------------------------
>
>


Reply | Threaded
Open this post in threaded view
|

Re: [OT] GCD Algorithm

hernan.wilkinson
Hi Nicolas,
 thank you for the answer!
 We'll take a look.

 Bye,
 Hernan.

On 4/20/07, nicolas cellier <[hidden email]> wrote:
Hi Hernan,

Lehmer is faster than Euclid algorithm only for large integers.
According to papers for (u gcd: v) you can expect a (n log: 2)
improvement factor where n is the number of bits (u abs highBit min: v
abs highBit).

For huge integers for which FFT product algorithm is efficient, you can
even get better, but at the cost of algorithm complexity.

However, if you look at squeak Integer>>#gcd: you will find that it is
not the naive Euclid algorithm, but rather some form of Lehmer's, so
don't expect much gain (unless you connect gnuMP library).

Nicolas

Hernan Wilkinson a écrit :

> Sorry... I pressed the wrong button...
> I wanted to ask for faster implementations of the GCD algorithm than the
> Euclid's one.
> We found on the web that the Lehmer's and the Binary GCD are faster...
> has anyone experience on that? are they really faster? has anyone have a
> implementation in Smalltalk? (or similar language like C++ :-)  )
>
> Thanks is advance and sorry to bother you people with this.
> Hernan.
>
> On 4/20/07, *Hernan Wilkinson* < [hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hi,
>      th
>
>
>
> ------------------------------------------------------------------------
>
>