179 Modular Arithmetic


Quiz idea provided by Jakub Kuzma

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)
> puts (a - b)
> puts (b * 3)

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)

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

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

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

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

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

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

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

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

   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)

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

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

   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)


I’m going to examine the solution from Andrea Fazzi for this week’s quiz. It’s quite simple and easy to follow, and it is quite similar to some of the other solutions. (Note that I’ll examine this in a different order than Andrea’s presentation, but it does not affect the solution.)

First, initialization:

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

  def to_i

This is pretty straightforward; Andrea stores the numeric value and the modulus, and provides a way to convert the class to an integer. As @n is returned without using the modulus operator, care must be taken to always assign @n correctly. The initializer does this, and is the only assignment to @n here, so it’s safe.

Next, comparison operations:

  include Comparable
  def <=>(other_n)
    @n <=> other_n.to_i

Andrea makes use of the Comparable module, which supplies the various comparison operators provided the class provides the <=> operator. Since this is essentially dealing with integers, it simply performs the <=> on the integer portions. We know @n is an integer, and the call to to_i ensures the right-hand side is an integer as well.

Next, arithmetic:

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

A nice little bit of metaprogramming is shown here. Andrea uses the define_method method defined on Module, of which Class is a subclass. (Confused yet?) Since each of the arithmetic operators will look basically the same, this removes redundancy and reduces the amount of code. The alternative would have been this:

  def +(other_n)
    Modulo.new(@n + other_n.to_i, @m)

But repeat that for every operator. Using define_method inside the loop removes the redundant code and, potentially, will support other operators by simply adding them to the list. The only other cost, so to speak, is that you must use send to replace actual use of the operator, but this is certainly something every Ruby programmer knows, or should know.

If the class ended there, most basic use would be covered… at least until someone tried 3 + Modulo.new(5) instead of Modulo.new(5) + 3. That’s because integers don’t know anything about the Modulo class. Fortunately, there is a nice technique available for dealing with this issue:

  def coerce(numeric)
    [numeric, @n]


The example 3 + Modulo.new(5) is equivalent to 3.send(:+, Modulo.new(5)). The integer 3 doesn’t know what a Modulo object is, so it calls coerce. That is, Modulo.new(5).coerce(3). It’s now the responsibility of Modulo#coerce to provide values that integer addition can deal with. As shown, Andrea returns an array of the original first argument (currently in numeric) and the value of the Modulo object (in @n). This is sufficient for integer addition to work, which will produce the expected value 8.

So ends Andrea’s Modulo class. This design is similar to most of the others, and follows the convention I suggested on the mailing list: that the left argument of any arithmetic operation determines the result’s type. So Modulo.new(5) + 3 generates a new Modulo object, while 3 + Modulo.new(5) generates a new integer. Both have a value of 8, but this non-communitivity could potentially become confusing. Consider if you were adding two Modulo objects, one using a modulus of 26, the other a modulus of 10? What should the result be? Someone who didn’t know or expect the left-hand-side rule might get unexpected results.

The solution from Ken Bloom addresses this by providing ModularBase. This module provides:

1. A way to create “modulo” factories, to ease the creation of multiple values using the same modulus. 2. All the methods needed to perform arithmetic and comparisons. 3. A way to check that two modulo values were created from the same ModularBase.

The last ensures that confusion can’t occur when mixing bases. Such operations simply won’t work, and will instead throw an exception. Note that this does not completely prevent a developer from mixing bases, but he must now be explicit about it.

Mod26 = ModularBase.new(26)
Mod11 = ModularBase.new(11)

a = Mod26.new(23)
b = Mod11.new(179)
puts a + b        # This raises an incompatible bases ArgumentError...

puts a + b.to_i   # ... but this is safe.

And Ken also promotes all operations involving integers to ModularBase instances as well, a nice feature. (See his coerce for how this works.)

Thanks for the submissions. Tomorrow, a little more “elementary” mathematics…

Wednesday, February 04, 2009