[QUIZ] Modular Arithmetic (#179)


M

Matthew Moss

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

Advertisements

R

Rob Biedenharn

# The default modulus is 26.
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://agileconsultingllc.com
(e-mail address removed)
 
M

Matthew Moss

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

Ken Bloom

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

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.

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

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

Matthew Moss

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

Ken Bloom

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
 
Ad

Advertisements

T

toomln

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

Andrea Fazzi

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/modulo.rb

Bye.
Andrea
 
R

Rob Biedenharn


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://agileconsultingllc.com
(e-mail address removed)
 
K

Ken Bloom

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

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.

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

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

Advertisements

T

Todd Benson

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
 
A

Andrea Fazzi

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
 
Ad

Advertisements

G

Gregory Brown

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top