## 179 Modular Arithmetic

### Description

*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)
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
```

### Summary

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
end
def to_i
@n
end
```

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
end
```

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) }
end
```

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)
end
```

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:

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

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…