Asp Forum - [QUIZ] Modular Arithmetic (#179

Matthew Moss

10/10/2008 3:14:00 PM

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

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/ModularArith...
[2]: http://en.wikipedia.org/wiki/Modular_...
[3]: http://www.math.harvard.edu/~sarah/magic/topic...

13 Answers

Rob Biedenharn

10/10/2008 4:08:00 PM

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

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

> 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

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 Biedenharn http://agileconsult...
Rob@AgileConsultingLLC.com

Matthew Moss

10/10/2008 4:18:00 PM

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

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.

Ken Bloom

10/10/2008 6:21:00 PM

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

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

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

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

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

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu...

Matthew Moss

10/10/2008 8:29:00 PM

>
> 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
> def test_add_reverse
> a = Mod26.new(15)
> assert_equal(???, 15 + a)
> end
>
> #new
> def test_sub_reverse
> a = Mod26.new(15)
> assert_equal(???, 1-a)
> end
>
> #already defined
> 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)?

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.

Ken Bloom

10/12/2008 6:27:00 PM

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

>> 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
>> def test_add_reverse
>> a = Mod26.new(15)
>> assert_equal(???, 15 + a)
>> end
>>
>> #new
>> def test_sub_reverse
>> a = Mod26.new(15)
>> assert_equal(???, 1-a)
>> end
>>
>> #already defined
>> 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)?
>
>
> 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.

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

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

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

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

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

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu...

ThoML

10/12/2008 6:55:00 PM

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

Andrea Fazzi

10/12/2008 9:27:00 PM

Matthew Moss ha scritto:
> ## 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.
>

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

Bye.
Andrea

Rob Biedenharn

10/12/2008 10:08:00 PM

Rob Biedenharn

10/12/2008 10:13:00 PM

On Oct 10, 2008, at 11:13 AM, Matthew Moss wrote:
> ## Modular Arithmetic (#179)
>
> [1]: http://mathworld.wolfram.com/ModularArith...
> [2]: http://en.wikipedia.org/wiki/Modular_...
> [3]: http://www.math.harvard.edu/~sarah/magic/topic...

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

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

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

# from Ken Bloom
def test_add_reverse
a = Modulo.new(15)
assert_equal(30, 15 + a)
end

# from Ken Bloom
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

# def test_value_range
# end
end
__END__

Rob Biedenharn http://agileconsult...
Rob@AgileConsultingLLC.com

Ken Bloom

10/12/2008 10:53:00 PM

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

> On Fri, Oct 10, 2008 at 10:13 AM, Matthew Moss <matt@moss.name> wrote:
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>>
>> 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/rub....
>>
>> 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
>
> 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

That only takes one more line to fix

def coerce o; [o, to_i]; end

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu...

comp.lang.ruby

[QUIZ] Modular Arithmetic (#179

Matthew Moss

Rob Biedenharn

Matthew Moss

Ken Bloom

Matthew Moss

Ken Bloom

ThoML

Andrea Fazzi

Rob Biedenharn

Rob Biedenharn

Ken Bloom

x Login to ForumsZone