From: ts <decoux@...>
Date: 2003-07-01T20:47:51+09:00
Subject: Re: Terribly OT ...

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