OpenEuphoria

Re: fraclib.e

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Jan 21, 2003
• 464 views

On Tue, 21 Jan 2003 10:28:04 +0100, Juergen Luethje <eu.lue at gmx.de>
wrote:

>global function gcd2 (biginteger p, biginteger q)

Similar to mine, but yours is neater, better commented, and works with
negative numbers =20

>   -- The number of steps needed to arrive at the greatest common
>   -- divisor for two numbers is <=3D 5 times the number of digits in
>   -- the number with the smaller absolute value, i.e.:
>   --    n =3D min(abs(p), abs(q))
>   --    steps <=3D 5*(floor(log10(n))+1)
Quite fast then.
>   -- The worst case occurs when the algorithm is applied to two
>   -- consecutive Fibonacci numbers.
>   -- [ by JuLu,
>   --   after http://mathworld.wolfram.com/EuclideanAlgorithm.html ]
Hairy stuff indeed.

Pete