[QUIZ] Modular Arithmetic (#179)

ruby-talk
2

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

···

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

  # 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.

     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

------------------------------------------------------------- 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 Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

3

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

···

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

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

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this quiz
until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

     <http://splatbang.com/rubyquiz/&gt;\.

3. Enjoy!

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

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

## Modular Arithmetic (#179)

_Quiz idea provided by Jakub Kuźma_

[Modular][1] [arithmetic][2] 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

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

4

## 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

5

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

···

On Fri, Oct 10, 2008 at 10:13 AM, Matthew Moss <matt@moss.name> wrote:

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

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

   <http://splatbang.com/rubyquiz/&gt;\.

3. Enjoy!

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

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

## Modular Arithmetic (#179)

_Quiz idea provided by Jakub Kuźma_

[Modular][1] [arithmetic][2] 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][3] 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

6

Matthew Moss ha scritto:

## Modular Arithmetic (#179)

_Quiz idea provided by Jakub Kuźma_

[Modular][1] [arithmetic][2] 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][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.

Bye.
Andrea

8

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 Bloom
  def test_add_reverse
    a = Modulo.new(15)
    assert_equal(30, 15 + a)
  end

  # from Ken Bloom
  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 Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

···

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

## Modular Arithmetic (#179)

[1]: Modular Arithmetic -- from Wolfram MathWorld
[2]: Modular arithmetic - Wikipedia
[3]: http://www.math.harvard.edu/~sarah/magic/topics/division

9

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

10

Hi,

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

Here below a refactored revision of my solution. Check

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

11

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

···

On Fri, Oct 10, 2008 at 11:13 AM, Matthew Moss <matt@moss.name> wrote:

## Modular Arithmetic (#179)

--
Technical Blaag at: http://blog.majesticseacreature.com | Non-tech
stuff at: http://metametta.blogspot.com

12

------------------------------------------------------------- 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.

Yes...

Though I am sometimes very explicit, I don't always state everything out explicitly. I like it when people surprise me. :slight_smile: 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.

13

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)?

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:

1. I didn't raise any errors for mismatched bases; I used the left 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.

14

That only takes one more line to fix

  def coerce o; [o, to_i]; end

···

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

On Fri, Oct 10, 2008 at 10:13 AM, Matthew Moss <matt@moss.name> wrote:

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

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

   <http://splatbang.com/rubyquiz/&gt;\.

3. Enjoy!

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

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

## Modular Arithmetic (#179)

_Quiz idea provided by Jakub Kuźma_

[Modular][1] [arithmetic][2] 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][3] 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

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

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

15

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

···

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

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)?

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:

1. I didn't raise any errors for mismatched bases; I used the left
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.

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/