[QUIZ] Modular Arithmetic (#179)

Discussion in 'Ruby' started by Matthew Moss, Oct 10, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    -=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
     
    Matthew Moss, Oct 10, 2008
    #1
    1. Advertising

  2. 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://agileconsultingllc.com
     
    Rob Biedenharn, Oct 10, 2008
    #2
    1. Advertising

  3. Matthew Moss

    Matthew Moss Guest

    > -------------------------------------------------------------
    > 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.
     
    Matthew Moss, Oct 10, 2008
    #3
  4. Matthew Moss

    Ken Bloom Guest

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

    --
    Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    Department of Computer Science. Illinois Institute of Technology.
    http://www.iit.edu/~kbloom1/
     
    Ken Bloom, Oct 10, 2008
    #4
  5. Matthew Moss

    Matthew Moss Guest

    >
    > 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.
     
    Matthew Moss, Oct 10, 2008
    #5
  6. Matthew Moss

    Ken Bloom Guest

    [QUIZ][SOLUTION] Modular Arithmetic (#179)

    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/~kbloom1/
     
    Ken Bloom, Oct 12, 2008
    #6
  7. Matthew Moss

    toomln Guest

    Re: Modular Arithmetic (#179)

    > ## 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
     
    toomln, Oct 12, 2008
    #7
  8. Matthew Moss

    Andrea Fazzi Guest

    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
     
    Andrea Fazzi, Oct 12, 2008
    #8
  9.  
    Rob Biedenharn, Oct 12, 2008
    #9
  10. On Oct 10, 2008, at 11:13 AM, Matthew Moss wrote:
    > ## Modular Arithmetic (#179)
    >
    > [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


    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
     
    Rob Biedenharn, Oct 12, 2008
    #10
  11. Matthew Moss

    Ken Bloom Guest

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

    > On Fri, Oct 10, 2008 at 10:13 AM, 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/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


    --
    Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    Department of Computer Science. Illinois Institute of Technology.
    http://www.iit.edu/~kbloom1/
     
    Ken Bloom, Oct 12, 2008
    #11
  12. Matthew Moss

    Todd Benson Guest

    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
     
    Todd Benson, Oct 13, 2008
    #12
  13. Matthew Moss

    Andrea Fazzi Guest

    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
     
    Andrea Fazzi, Oct 13, 2008
    #13
  14. On Fri, Oct 10, 2008 at 11:13 AM, Matthew Moss <> 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



    --
    Technical Blaag at: http://blog.majesticseacreature.com | Non-tech
    stuff at: http://metametta.blogspot.com
     
    Gregory Brown, Oct 13, 2008
    #14
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dan Stromberg
    Replies:
    2
    Views:
    479
    Michael Spencer
    Jan 22, 2005
  2. Tuvas
    Replies:
    20
    Views:
    967
    Tuvas
    Mar 6, 2006
  3. Simon Brooke

    J2ME location api (jsr 179) - where?

    Simon Brooke, Aug 14, 2006, in forum: Java
    Replies:
    1
    Views:
    679
    Mario Kusek
    Aug 17, 2006
  4. Sam Roberts
    Replies:
    2
    Views:
    372
    Bret Jolly
    Nov 23, 2004
  5. Matthew Moss

    [SUMMARY] Modular Arithmetic (#179)

    Matthew Moss, Oct 17, 2008, in forum: Ruby
    Replies:
    0
    Views:
    179
    Matthew Moss
    Oct 17, 2008
Loading...

Share This Page