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
>
>
>
> ------------------------------------------------------------------------
>
>
Locked
