# Modular Arithmetic (#179)

#1

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

The three rules of Ruby Q. 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 Q. 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Q. 2. Until then,
please visit the temporary website at

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
the original quiz message, if you can.

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

## Modular Arithmetic (#179)

Quiz idea provided by Jakub KuÅºma

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

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

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

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

#2

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

As noted in the example, you should use a modulus of 26 if none is
specified in the initializer.

``````    assert_equal(6, a - b)
assert_equal(3, a * b)
end
``````

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

## 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 B. http://agileconsultingllc.com

#3

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

#4

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

## Modular Arithmetic (#179)

24)`, I take the congruent value mod 24, which is 5. So seven hours
# 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

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
a = Mod26.new(15)
assert_equal(???, 15 + a)
end

#new
def test_sub_reverse
a = Mod26.new(15)
assert_equal(???, 1-a)
end

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

#5
``````    assert_nothing_raised do
end
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.

#6

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

``````      Mod26.new(1)+Mod8.new(1).to_i

end
``````

When I started experimenting with my own solution, my design choice was
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.

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

a = Mod26.new(15)
b = Mod26.new(0)
assert_equal(a, a + b)
end

a = Mod26.new(15)
b = Mod26.new(19)
c = Mod26.new(8)
assert_equal(c, a + b)
end

a = Mod26.new(15)
assert_equal(4, 15 + a)
end

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

#7

On Fri, Oct 10, 2008 at 10:13 AM, Matthew M. removed_email_address@domain.invalid wrote:

## Modular Arithmetic (#179)

value mod 24, which is 5. So seven hours after 10pm is 5am.

a = Modulo.new(15)

`````` def test_modulo_equality
assert_equal(a, a + b)
a = Modulo.new(15)

assert_equal(c, a * b)
assert_equal(77, 11 * a)

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

#8

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

#9

Matthew M. ha scritto:

10pm, I would add 22 and 7 to get 29. As that is outside the range

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.

http://github.com/remogatto/quizzes/tree/master/179/lib/modulo.rb

Bye.
Andrea

#10

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

## Modular Arithmetic (#179)

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

# 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

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

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

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

a = Modulo.new(15)
assert_equal(30, 15 + a)
end

# from Ken B.

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

# end

end
END

Rob B. http://agileconsultingllc.com

#11

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

please visit the temporary website at

10pm, I would add 22 and 7 to get 29. As that is outside the range `[0,

As noted in the example, you should use a modulus of 26 if none is

``````    a = Modulo.new(15)

assert_equal(c, a - b)
b = Modulo.new(7)
def test_mul_int_reverse
assert_equal(3, a * b)
def test_sort
``````

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

That only takes one more line to fix

def coerce o; [o, to_i]; end

#12

Hi,

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

Here below a refactored revision of my solution. Check

http://github.com/remogatto/quizzes/tree/master/179/lib/modulo.rb

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

#13

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

#14

On Fri, Oct 10, 2008 at 11:13 AM, Matthew M. removed_email_address@domain.invalid wrote:

## Modular Arithmetic (#179)

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