ts wrote:

>>>>>>"H" == Harry Ohlsen <(E-Mail Removed)> 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]]