From: Matthew Moss <matt@...>
Date: 2008-10-11T00:13:59+09:00
Subject: [QUIZ] Modular Arithmetic (#179)

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

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

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



[1]: http://mathworld.wolfram.com/ModularArithmetic.html
[2]: http://en.wikipedia.org/wiki/Modular_arithmetic
[3]: http://www.math.harvard.edu/~sarah/magic/topics/division