Modular Arithmetic (#179)

mansfiem · October 10, 2008, 5:16pm

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q. 2:

Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.
Support Ruby Q. 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Q. 2. Until then,
please visit the temporary website at

http://splatbang.com/rubyquiz/.
Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Modular Arithmetic (#179)

Quiz idea provided by Jakub KuÅºma

Modular arithmetic is integer-based arithmetic in which the
operands and results are constrained to a limited range, from zero to
one less than the modulus. Take, for example, the 24-hour clock. Hours
on the clock start at 0 and increase up to (and include) 23. But above
that, we must use the appropriate congruent value modulo 24. For
example, if I wanted to know what time it would be seven hours after
10pm, I would add 22 and 7 to get 29. As that is outside the range
[0, 24), I take the congruent value mod 24, which is 5. So seven
hours after 10pm is 5am.

Your task this week is to write a class Modulo that behaves in
almost all ways like an Integer. It should support all basic
operations: addition, subtraction, multiplication, exponentiation,
conversion to string, etc. The significant difference, of course, is
that an instance of Modulo should act modularly.

For example:

# The default modulus is 26.
> a = Modulo.new(15)
> b = Modulo.new(19)
> puts (a + b)
8
> puts (a - b)
22
> puts (b * 3)
5

As noted in the example, you should use a modulus of 26 if none is
specified in the initializer.

While most operations will be straightforward, modular division is a
bit trickier. Here is one article that explains how it can be
done, but I will leave division as extra credit.

Enjoy this test file as you get started…

require 'test/unit'
require 'modulo'

class TestModulo < Test::Unit::TestCase
   def test_modulo_equality
      a = Modulo.new(23)
      b = Modulo.new(23)
      c = Modulo.new(179)
      assert_equal(a, b)
      assert_equal(a, c)
   end

   def test_add_zero
      a = Modulo.new(15)
      b = Modulo.new(0)
      assert_equal(a, a + b)
   end

   def test_add
      a = Modulo.new(15)
      b = Modulo.new(19)
      c = Modulo.new(8)
      assert_equal(c, a + b)
   end

   def test_add_int
      a = Modulo.new(15)
      c = Modulo.new(10)
      assert_equal(c, a + 21)
   end

   def test_sub
      a = Modulo.new(15)
      b = Modulo.new(19)
      c = Modulo.new(22)
      assert_equal(c, a - b)
   end

   def test_sub_int
      a = Modulo.new(15)
      c = Modulo.new(1)
      assert_equal(c, a - 66)
   end

   def test_mul
      a = Modulo.new(15)
      b = Modulo.new(7)
      c = Modulo.new(1)
      assert_equal(c, a * b)
   end

   def test_mul_int
      a = Modulo.new(15)
      c = Modulo.new(9)
      assert_equal(c, a * 11)
   end

   def test_mul_int_reverse
      a = Modulo.new(15, 8)
      assert_equal(77, 11 * a)
   end

   def test_non_default_modulo
      a = Modulo.new(15, 11)
      b = Modulo.new(9, 11)

      assert_equal(2, a + b)
      assert_equal(6, a - b)
      assert_equal(3, a * b)
   end

   def test_compare
      assert_equal(1, Modulo.new(15) <=> Modulo.new(30))
   end

   def test_compare_int
      assert_equal(-1, Modulo.new(15) <=> 35)
   end

   def test_sort
      x = [Modulo.new(15), Modulo.new(29), Modulo.new(-6),

Modulo.new(57)]
y = [3, 5, 15, 20]
assert_equal(y, x.sort)
end
end

mansfiem · October 10, 2008, 6:11pm

On Oct 10, 2008, at 11:13 AM, Matthew M. wrote:

As noted in the example, you should use a modulus of 26 if none is
specified in the initializer.

    assert_equal(6, a - b)
    assert_equal(3, a * b)
 end

So I suppose the method signature would be documented something like:

Modulo::new
Modulo.new(value=0, modulus=26)

  Returns a new object that behaves according to the rules of
  Modular Arithmetic, but otherwise responds like an Integer from
  the set of integers between 0 and modulus-1.

You never specifically said how an alternate modulus was indicated,
but your tests give a good hint.

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

mansfiem · October 10, 2008, 6:21pm

but your tests give a good hint.
Yes…

Though I am sometimes very explicit, I don’t always state everything
out explicitly. I like it when people surprise me. Granted, the
tests I wrote do assume the interface you provided above which, given
the description and the test, is what I expect most people would have
come up with.

mansfiem · October 10, 2008, 8:25pm

On Fri, 10 Oct 2008 10:13:59 -0500, Matthew M. wrote:

Modular Arithmetic (#179)

24)`, I take the congruent value mod 24, which is 5. So seven hours
# The default modulus is 26.
> a = Modulo.new(15)
> b = Modulo.new(19)
> puts (a + b)
8
> puts (a - b)
22
> puts (b * 3)
5

Just a preview of my solution (inspired by TZFile):

Mod26=ModularBase.new(26)
Mod8=ModularBase.new(8)

   def test_incompat_bases
     assert_raises(ArgumentError) do
       Mod26.new(1)+Mod8.new(1)
     end
     assert_nothing_raised do
       Mod26.new(1)+Mod8.new(1).to_i
     end
   end

That said, please clarify on the behavior of a couple tests:

   #new
   def test_add_reverse
      a = Mod26.new(15)
      assert_equal(???, 15 + a)
   end

   #new
   def test_sub_reverse
      a = Mod26.new(15)
      assert_equal(???, 1-a)
   end

   #already defined
   def test_mul_int_reverse
      a = Mod8.new(15)
      assert_equal(77, 11 * a)
   end

Clearly a Modulo +/*/- an Integer should give a Modulo
Should the reverse relation promote the Modulo to an Integer, or promote
the Integer to a Modulo (of the same base)?

–Ken

mansfiem · October 10, 2008, 10:32pm

    assert_nothing_raised do
  end
     assert_equal(77, 11 * a)
  end
Clearly a Modulo +/*/- an Integer should give a Modulo
Should the reverse relation promote the Modulo to an Integer, or
promote
the Integer to a Modulo (of the same base)?

This issue requires some sort of design decision, which I
intentionally left out of the requirements, so you may do what you
like in this respect, and perhaps explain why you made a particular
choice.

When I started experimenting with my own solution, my design choice
was that the result type of any operation was the same as the first
operand. I did this primarily for simplicity, since I didn’t need to
raise errors for incompatible bases, and most operations became
trivial. Of course, this choice is not without problem, since some
operations that might normally be communitive (if compatible modulo
was enforced) are no longer communitive.

In context with your questions above and my particular design choice:

I didn’t raise any errors for mismatched bases; I used the left
operand to determine the result’s type.
As all your reverse tests (which should be considered by all
implementors) have a left Integer argument, all the answers would be
the same, and the domain would be the full integer set. So, from top
to bottom, I would replace ??? with 30 and -14.

mansfiem · October 12, 2008, 8:42pm

On Fri, 10 Oct 2008 15:29:02 -0500, Matthew M. wrote:

      Mod26.new(1)+Mod8.new(1).to_i

  end
When I started experimenting with my own solution, my design choice was
operand to determine the result’s type. 2. As all your reverse tests
(which should be considered by all implementors) have a left Integer
argument, all the answers would be the same, and the domain would be the
full integer set. So, from top to bottom, I would replace ??? with 30
and -14.

OK. I decided against that and decided that the operations would be
commutative, always promoting to modular arithmetic.

Here’s my solution:

module ModularBase
def self.new base
c=Class.new do
include ModularBase
end
c.class_eval do
define_method :base do
base
end
end
c
end

def self.define_op op
class_eval <<-“end;”
def #{op} rhs
case rhs
when self.class: self.class.new(@value #{op}
rhs.instance_variable_get(:@value))
when Integer: self.class.new(@value #{op} rhs)
when ModularBase: raise ArgumentError, “Error performing modular
arithmetic with incompatible bases”
else
raise ArgumentError, “Requires an integer or compatible base”
end
end
end;
end

#begin defining operations

def initialize value
@value = value % base
end

define_op :+
define_op :-
define_op :*

def == rhs
case rhs
when self.class: @value == rhs.instance_variable_get(:@value)
when ModularBase: false
when Integer: @value == rhs
else false
end
end

def coerce other
[self.class.new(other), self]
end

def <=> rhs
case rhs
when self.class: @value <=> rhs.instance_variable_get(:@value)
when Integer: @value <=> rhs
else raise ArgumentError
end
end

def to_i
@value
end
def to_s
@value.to_s
end
end

exit if FILE != $0

require ‘test/unit’

class TestModulo < Test::Unit::TestCase
Mod26=ModularBase.new(26)
Mod11=ModularBase.new(11)
Mod8=ModularBase.new(8)

def test_modulo_equality
a = Mod26.new(23)
b = Mod26.new(23)
c = Mod26.new(179)
assert_equal(a, b)
assert_equal(a, c)
end

def test_add_zero
a = Mod26.new(15)
b = Mod26.new(0)
assert_equal(a, a + b)
end

def test_add
a = Mod26.new(15)
b = Mod26.new(19)
c = Mod26.new(8)
assert_equal(c, a + b)
end

def test_add_reverse
a = Mod26.new(15)
assert_equal(4, 15 + a)
end

def test_add_int
a = Mod26.new(15)
c = Mod26.new(10)
assert_equal(c, a + 21)
end

def test_sub
a = Mod26.new(15)
b = Mod26.new(19)
c = Mod26.new(22)
assert_equal(c, a - b)
end

def test_sub_reverse
a = Mod26.new(15)
assert_equal(12, 1-a)
end

def test_sub_int
a = Mod26.new(15)
c = Mod26.new(1)
assert_equal(c, a - 66)
end

def test_mul
a = Mod26.new(15)
b = Mod26.new(7)
c = Mod26.new(1)
assert_equal(c, a * b)
end

def test_mul_int
a = Mod26.new(15)
c = Mod26.new(9)
assert_equal(c, a * 11)
end

def test_mul_int_reverse
a = Mod8.new(15)
assert_equal(5, 11 * a)
end

def test_non_default_modulo
a = Mod11.new(15)
b = Mod11.new(9)

  assert_equal(2, a + b)
  assert_equal(6, a - b)
  assert_equal(3, a * b)

end

def test_compare
assert_equal(1, Mod26.new(15) <=> Mod26.new(30))
end

def test_compare_int
assert_equal(-1, Mod26.new(15) <=> 35)
end

def test_sort
x = [Mod26.new(15), Mod26.new(29), Mod26.new(-6), Mod26.new(57)]
y = [3, 5, 15, 20]
assert_equal(y, x.sort)
end

def test_incompat_bases
assert_raises(ArgumentError) do
Mod26.new(1)+Mod8.new(1)
end
assert_nothing_raised do
Mod26.new(1)+Mod8.new(1).to_i
end
end
end

mansfiem · October 12, 2008, 10:04pm

On Fri, Oct 10, 2008 at 10:13 AM, Matthew M. [email protected] wrote:

Modular Arithmetic (#179)

value mod 24, which is 5. So seven hours after 10pm is 5am.

a = Modulo.new(15)
 def test_modulo_equality
    assert_equal(a, a + b)
    a = Modulo.new(15)

    assert_equal(c, a * b)
    assert_equal(77, 11 * a)

    y = [3, 5, 15, 20]
    assert_equal(y, x.sort)
 end
end

Lazy, minimalistic version…

class Modulo
def initialize(v, b = 26); @v, @b = v % b, b; end
def to_i; @v; end
def == o; @v == o.to_i % @b; end
def <=> o; @v <=> o.to_i; end
[:+, :-, :*].each {|op| define_method(op) {|rh|
instance_eval(“Modulo.new((@v #{op} #{rh.to_i}) % @b)”)}}
end

Error in test_mul_int_reverse, though.

Todd

mansfiem · October 12, 2008, 9:00pm

Modular Arithmetic (#179)

Here is a (maybe too) simple proxy solution. Modular division isn’t
implemented. It passes the tests – little more.

This solution is for ruby 1.9 only. AFAIK facets also has a
BasicObject class that could (or maybe not) be used as a replacement
for ruby19’s BasicObject.

Regards,
Thomas.

#!/usr/bin/env ruby19

class Modulo < BasicObject

def initialize(num, modulo=26)
    @modulo = modulo
    @num = num % @modulo
end

def method_missing(meth, *args)
    rv = @num.send(meth, *args)
    case rv
    when ::Numeric
        ::Modulo.new(rv % @modulo)
    else
        rv
    end
end

def <=>(other)
    @num <=> other.real
end

def ==(other)
    @num == other.real
end
alias :equal? :==

def real
    @num
end

end

mansfiem · October 12, 2008, 11:29pm

Matthew M. ha scritto:

10pm, I would add 22 and 7 to get 29. As that is outside the range

As noted in the example, you should use a modulus of 26 if none is
specified in the initializer.

While most operations will be straightforward, modular division is a
bit trickier. [Here is one article][3] that explains how it can be
done, but I will leave division as extra credit.

Hi,

here’s my solution:

class Modulo

include Comparable

[:+, :-, :*].each do |meth|
define_method(meth) { |other_n| Modulo.new(@n.send(meth,
other_n.to_i), @m) }
end

def initialize(n = 0, m = 26)
@m = m
@n = modularize(n)
end

def <=>(other_n)
@n <=> other_n.to_i
end

def to_i
@n
end

private

def coerce(numeric)
[@n, numeric]
end

def modularize(n)
return (n > 0 ? n % @m : (n - @m) % @m) if (n - @m) >= 0 or n < 0
n
end

end

Please, refer to the git repository below for updated revisions of this
solution.

github.com

remogatto/quizzes/blob/master/179/lib/modulo.rb

class Modulo

  include Comparable

  [:+, :-, :*, :**].each do |meth|
    define_method(meth) { |other_n| Modulo.new(@n.send(meth, other_n.to_i), @m) }
  end

  def initialize(n = 0, m = 26)
    @n, @m = n % m, m
  end

  def <=>(other_n)
    @n <=> other_n.to_i
  end

  def to_i
    @n
  end

This file has been truncated. show original

Bye.
Andrea

mansfiem · October 13, 2008, 12:16am

On Oct 10, 2008, at 11:13 AM, Matthew M. wrote:

Modular Arithmetic (#179)

I agreed with Matthew’s design choices regarding the type of “Integer
{op} Modulo” being Integer. I’d intended to add some tests to show
that Modulo.new(0)-10 would give Modulo.new(16) and generally give an
integer value in the 0…modulus domain. (Of course, if I were less
busy, I’d have taken a shot at division, too.)

-Rob

==> modulo.rb <==
class Modulo
include Comparable

Returns a new object that behaves according to the rules of

Modular Arithmetic, but otherwise responds like an Integer from

the set of integers between 0 and modulus-1.

def initialize(value=0, modulus=26)
@modulus = modulus
@value = value % @modulus
end

def to_int
@value
end

def to_i
self.to_int
end

def <=>(other)
case other
when Modulo
@value <=> other.to_int
when Integer
@value <=> other
else
raise ArgumentError, “I don’t know how to compare a
#{other.class.name}”
end
end

def coerce(other)
case other
when Integer
return other, self.to_int
else
super
end
end

[ :+, :-, :* ].each do |method|
define_method method do |other|
self.class.new(@value.send(method, other.to_int), @modulus)
end
end

end
END

==> test_modulo.rb <==
require ‘test/unit’
require ‘modulo’

class TestModulo < Test::Unit::TestCase
def test_modulo_equality
a = Modulo.new(23)
b = Modulo.new(23)
c = Modulo.new(179)
assert_equal(a, b)
assert_equal(a, c)
end

def test_add_zero
a = Modulo.new(15)
b = Modulo.new(0)
assert_equal(a, a + b)
end

def test_add
a = Modulo.new(15)
b = Modulo.new(19)
c = Modulo.new(8)
assert_equal(c, a + b)
end

def test_add_int
a = Modulo.new(15)
c = Modulo.new(10)
assert_equal(c, a + 21)
end

def test_sub
a = Modulo.new(15)
b = Modulo.new(19)
c = Modulo.new(22)
assert_equal(c, a - b)
end

def test_sub_int
a = Modulo.new(15)
c = Modulo.new(1)
assert_equal(c, a - 66)
end

def test_mul
a = Modulo.new(15)
b = Modulo.new(7)
c = Modulo.new(1)
assert_equal(c, a * b)
end

def test_mul_int
a = Modulo.new(15)
c = Modulo.new(9)
assert_equal(c, a * 11)
end

from Ken B.

def test_add_reverse
a = Modulo.new(15)
assert_equal(30, 15 + a)
end

from Ken B.

def test_sub_reverse
a = Modulo.new(15)
assert_equal(-14, 1-a)
end

def test_mul_int_reverse
a = Modulo.new(15, 8)
assert_equal(77, 11 * a)
end

def test_non_default_modulo
a = Modulo.new(15, 11)
b = Modulo.new(9, 11)

assert_equal(2, a + b)
assert_equal(6, a - b)
assert_equal(3, a * b)

end

def test_compare
assert_equal(1, Modulo.new(15) <=> Modulo.new(30))
end

def test_compare_int
assert_equal(-1, Modulo.new(15) <=> 35)
end

def test_sort
x = [Modulo.new(15), Modulo.new(29), Modulo.new(-6), Modulo.new(57)]
y = [3, 5, 15, 20]
assert_equal(y, x.sort)
end

def test_value_range

end

end
END

Rob B. http://agileconsultingllc.com
[email protected]

mansfiem · October 13, 2008, 1:12am

On Sun, 12 Oct 2008 15:00:27 -0500, Todd B. wrote:

please visit the temporary website at

10pm, I would add 22 and 7 to get 29. As that is outside the range `[0,

As noted in the example, you should use a modulus of 26 if none is
    a = Modulo.new(15)

    assert_equal(c, a - b)
    b = Modulo.new(7)
 def test_mul_int_reverse
    assert_equal(3, a * b)
 def test_sort
def == o; @v == o.to_i % @b; end
def <=> o; @v <=> o.to_i; end
[:+, :-, :*].each {|op| define_method(op) {|rh|
instance_eval(“Modulo.new((@v #{op} #{rh.to_i}) % @b)”)}} end

Error in test_mul_int_reverse, though.

Todd

That only takes one more line to fix

def coerce o; [o, to_i]; end

mansfiem · October 13, 2008, 10:35am

Hi,

I realized that Modulo#modularize contains a lot of useless
conditionals.

Here below a refactored revision of my solution. Check

github.com

remogatto/quizzes/blob/master/179/lib/modulo.rb

class Modulo

  include Comparable

  [:+, :-, :*, :**].each do |meth|
    define_method(meth) { |other_n| Modulo.new(@n.send(meth, other_n.to_i), @m) }
  end

  def initialize(n = 0, m = 26)
    @n, @m = n % m, m
  end

  def <=>(other_n)
    @n <=> other_n.to_i
  end

  def to_i
    @n
  end

This file has been truncated. show original

for better formatting.

class Modulo

include Comparable

[:+, :-, :*].each do |meth|
define_method(meth) { |other_n| Modulo.new(@n.send(meth,
other_n.to_i), @m) }
end

def initialize(n = 0, m = 26)
@n, @m = n % m, m
end

def <=>(other_n)
@n <=> other_n.to_i
end

def to_i
@n
end

private

def coerce(numeric)
[@n, numeric]
end

end

Regards,
Andrea

mansfiem · October 13, 2008, 5:12am

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

mansfiem · October 13, 2008, 7:18pm

On Fri, Oct 10, 2008 at 11:13 AM, Matthew M. [email protected] wrote:

Modular Arithmetic (#179)

Doesn’t handle division, may have some other issues, but more-or-less
works.

-greg

class Modulo

include Comparable

def initialize(num, mod=26)
@num = num
@mod = mod
end

def to_i
@num % @mod
end

def coerce(other)
[other,to_i]
end

def <=>(other)
to_i <=> other.to_i
end

def self.modulo_operators(*ops)
ops.each do |op|
define_method(op) { |other| Modulo.new(@num.send(op, other.to_i) %
@mod) }
end
end

def self.modulo_delegates(*msgs)
msgs.each { |msg| define_method(msg) { |*args| to_i.send(msg, *args)
} }
end

modulo_operators :+, :-, :*, :**
modulo_delegates :to_s

end

Modular Arithmetic (#179)

Modular Arithmetic (#179)

Modulo::new Modulo.new(value=0, modulus=26)

Modular Arithmetic (#179)

Modular Arithmetic (#179)

Modular Arithmetic (#179)

Modular Arithmetic (#179)

Returns a new object that behaves according to the rules of

Modular Arithmetic, but otherwise responds like an Integer from

the set of integers between 0 and modulus-1.

from Ken B.

from Ken B.

def test_value_range

end

Modular Arithmetic (#179)

Modulo::new
Modulo.new(value=0, modulus=26)