Hi Nicolas,<br> thank you for the answer!<br> We'll take a look.<br><br> Bye,<br> Hernan.<br><br><div><span class="gmail_quote">On 4/20/07, <b class="gmail_sendername">nicolas cellier</b> <<a href="mailto:ncellier@ifrance.com">
ncellier@ifrance.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Hi Hernan,<br><br>Lehmer is faster than Euclid algorithm only for large integers.
<br>According to papers for (u gcd: v) you can expect a (n log: 2)<br>improvement factor where n is the number of bits (u abs highBit min: v<br>abs highBit).<br><br>For huge integers for which FFT product algorithm is efficient, you can
<br>even get better, but at the cost of algorithm complexity.<br><br>However, if you look at squeak Integer>>#gcd: you will find that it is<br>not the naive Euclid algorithm, but rather some form of Lehmer's, so
<br>don't expect much gain (unless you connect gnuMP library).<br><br>Nicolas<br><br>Hernan Wilkinson a écrit :<br>> Sorry... I pressed the wrong button...<br>> I wanted to ask for faster implementations of the GCD algorithm than the
<br>> Euclid's one.<br>> We found on the web that the Lehmer's and the Binary GCD are faster...<br>> has anyone experience on that? are they really faster? has anyone have a<br>> implementation in Smalltalk? (or similar language like C++ :-) )
<br>><br>> Thanks is advance and sorry to bother you people with this.<br>> Hernan.<br>><br>> On 4/20/07, *Hernan Wilkinson* < <a href="mailto:hernan.wilkinson@gmail.com">hernan.wilkinson@gmail.com</a><br>
> <mailto:<a href="mailto:hernan.wilkinson@gmail.com">hernan.wilkinson@gmail.com</a>>> wrote:<br>><br>> Hi,<br>> th<br>><br>><br>><br>> ------------------------------------------------------------------------
<br>><br>><br><br><br></blockquote></div><br>