From: Harry Ohlsen <harryo@...>
Date: 2003-07-02T18:50:50+09:00
Subject: Re: Terribly OT ...

ts wrote:

>  It came from here :
> 
>  http://www.maths.usyd.edu.au:8000/u/bobh/UoS/MATH3009/wk2.pd

Thanks again, Guy. Based on that reference, I was able to get my naive (non-recursive) implementation working and generating the correct magic table ...


module Euclid
   class MagicTable < Array
      Row = Struct.new("Row", :d, :p, :q)

      def initialize
         self << Row.new(nil, 0, 1)
         self << Row.new(nil, 1, 0)
      end

      alias :<< push

      def <<(row)
         push(Row.new(*row))
      end

      def to_s
         s = ""

         self.each do |row|
            d = row.d

            if d.nil?
               s << "     "
            else
               s << (sprintf "%4d ", d)
            end
         end

         s << "\n"

         self.each { |row| s << (sprintf "%4d ", row.p) }

         s << "\n"

         self.each { |row| s << (sprintf "%4d ", row.q) }

         s << "\n"

         return s
      end
   end

   def Euclid.GCD(a, b)
      magic = MagicTable.new

      if a < b
         a, b = b, a
      end

      while b > 0
         d = a / b
         r = a % b

         p = d * magic[-1].p + magic[-2].p
         q = d * magic[-1].q + magic[-2].q

         magic << [d, p, q]

         a, b = b, a % b
      end

      return a, magic
   end

end

if $0 == __FILE__
   gcd, magic = Euclid.GCD(787, 268)

   puts "(787, 268) = #{gcd}\n\n"

   puts "Magic Table ...\n\n#{magic}"
end