[QUIZ] Modular Arithmetic (#179)

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

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.

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

## Modular Arithmetic (#179)

_Quiz idea provided by Jakub Ku=C5=BAma_

[Modular][1] [arithmetic][2] is integer-based arithmetic in which the =20=

operands and results are constrained to a limited range, from zero to =20=

one less than the modulus. Take, for example, the 24-hour clock. Hours =20=

on the clock start at 0 and increase up to (and include) 23. But above =20=

that, we must use the appropriate congruent value modulo 24. For =20
example, if I wanted to know what time it would be seven hours after =20
10pm, I would add 22 and 7 to get 29. As that is outside the range =20
`[0, 24)`, I take the congruent value mod 24, which is 5.  So seven =20
hours after 10pm is 5am.

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

For example:

    # The default modulus is 26.
    > a =3D Modulo.new(15)
    > b =3D 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 =20
specified in the initializer.

While most operations will be straightforward, modular division is a =20
bit trickier. [Here is one article][3] that explains how it can be =20
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 =3D Modulo.new(23)
          b =3D Modulo.new(23)
          c =3D Modulo.new(179)
          assert_equal(a, b)
          assert_equal(a, c)
       end

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

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

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

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

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

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

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

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

       def test_non_default_modulo
          a =3D Modulo.new(15, 11)
          b =3D 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) <=3D> Modulo.new(30))
       end

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

       def test_sort
          x =3D [Modulo.new(15), Modulo.new(29), Modulo.new(-6), =20
Modulo.new(57)]
          y =3D [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