class MathPrograms::Axby1

The class Axby1 is an equation ax+by=1. When it is created, two arguments are given. They are the coefficients a and b. The instance method ‘solve’ returns a pair of the solution [x, y]. It uses euclidian algorithm.

Attributes

a[RW]

b[RW]

Public Class Methods

new(a = nil, b = nil) click to toggle source

Two arguments a and b are the constants of ax+by=1. They must be coprime. Otherwise the coefficients a and b, that are @a and @b in the instance, are set to be nil. Then the methods ‘solve’ returns nil.

# File lib/math_programs/axby1.rb, line 13
def initialize a = nil, b = nil
  if a.instance_of?(Integer) && b.instance_of?(Integer) && a.gcd(b) == 1
    @a, @b = a, b
  else
    @a = @b = nil
  end
end

Public Instance Methods

solve() click to toggle source

Returns the solution of ax+by=1. It uses euclidian algorithm so it takes short time to get an answer even if a and b are very big.

# File lib/math_programs/axby1.rb, line 23
def solve
  if @a == nil || @b == nil
    return nil
  end
  d = []
  d << [@a,@b,@a/@b,@a.modulo(@b)]
  until d[-1][3] == 0 do
    d << euclid(d[-1])
  end

  e = []
  a = d.pop
  # a[1] = 1 or -1
  e << [a[0],a[1],a[1],-a[1]*(a[2]-1)]
  while (a = d.pop) do
    e << [a[0],e[-1][3],a[1],e[-1][1]-e[-1][3]*a[2]]
  end

  if e[-1][1] >= 0
    [e[-1][1], e[-1][3]]
  else
    [e[-1][1]+@b, e[-1][3]-@a]
  end
end