From: Harry Ohlsen <harryo@...>
Date: 2003-07-01T21:15:39+09:00
Subject: Re: Terribly OT ...

ts wrote:

>>>>>>"H" == Harry Ohlsen <harryo@qiqsolutions.com> writes:
> 
> 
> H> I'm sitting here trying to write some Ruby code that generates the
> H> "magic table" from the remainders that pop up when executing Euclid's
> H> algorithm.  I don't suppose anyone happens to remember how that works? 
> 
>  Euh, this ???
> 
> 
> svg% cat b.rb
> #!/usr/bin/ruby
> def lcr(a, b, v)
>    r = a % b
>    if r == 0
>       []
>    else
>       q = a / b
>       x = [v[0] - q * v[2], v[1] - q * v[3]]
>       [x] + lcr(b, r, [v[2], v[3], *x])
>    end
> end
> 
> def lc(a, b)
>    if b == 0
>       [[1, 0]]
>    else
>       lcr(a, b, [1, 0, 0, 1])
>    end + [[a, b]]
> end
> 
> p lc(93512222, 6812345)
> svg% 
> 
> svg% b.rb
> [[1, -13], [-1, 14], [3, -41], [-4, 55], [7, -96], [-11, 151], [227, -3116], [-919, 12615], [42501, -583406], [-43420, 596021], [1345101, -18464036], [-2733622, 37524093], [93512222, 6812345]]
> svg% 
> 
> 
> Guy Decoux
> 
> 

I was able to get your code to produce the table precisely as it was in the exercise solution by making a couple of tiny changes, although I'm going to have to think about how your recursive code relates to my simplistic implementation of the Euclidean algorithm :-) ...


def lcr(a, b, v)
   r = a % b
   if r == 0
      []
   else
      q = a / b
      x = [v[0] - q * v[2], v[1] - q * v[3]]
      [x] + lcr(b, r, [v[2], v[3], *x])
   end
end

def lc(a, b)
   if b == 0
      [[1, 0]]
   else
      lcr(a, b, [1, 0, 0, 1])
   end + [[b, a]]
end

p lc(93512222, 6812345).map { |x| [x[1].abs, x[0].abs] }

D:\HarryO\Mathematics\NumberTheory>ruby guy.rb

[[13, 1], [14, 1], [41, 3], [55, 4], [96, 7], [151, 11], [3116, 227], [12615, 91
9], [583406, 42501], [596021, 43420], [18464036, 1345101], [37524093, 2733622],
[93512222, 6812345]]