From: Todd Benson <caduceass@...>
Date: 2008-10-13T12:07:23+09:00
Subject: Re: [QUIZ] Modular Arithmetic (#179)

Same as previous, but with #coerce, #recurse, and #/

I cheated and looked at the pseudocode for extended Euclidean algorithm.

class Modulo
  def initialize(v, b = 26); @v, @b = v % b, b; end
  def to_i; @v; end
  def coerce o; [o, to_i]; end
  def == o; @v == o.to_i % @b; end
  def <=> o; @v <=> o.to_i; end
  [:+, :-, :*].each do |op|
    define_method(op) {|rh| instance_eval("Modulo.new((@v #{op}
#{rh.to_i}) % @b)")}}
  end
  def recurse(a, b)
    return [0, 1] if a % b == 0
    x, y = recurse(b, a % b)
    [y, x - y * (a / b)]
  end
  def / o; recurse(o.to_i, @b).first * @v % @b; end
end


Todd