Forum: Ruby Modular Arithmetic (#179)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-10-10 17:16
(Received via mailing list)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

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



[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
Ef3aa7f7e577ea8cd620462724ddf73b?d=identicon&s=25 Rob Biedenharn (Guest)
on 2008-10-10 18:11
(Received via mailing list)
On Oct 10, 2008, at 11:13 AM, Matthew Moss 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 Biedenharn    http://agileconsultingllc.com
Rob@AgileConsultingLLC.com
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-10-10 18:21
(Received via mailing list)
> 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.
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2008-10-10 20:25
(Received via mailing list)
On Fri, 10 Oct 2008 10:13:59 -0500, Matthew Moss 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
       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
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-10-10 22:32
(Received via mailing list)
>         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.
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2008-10-12 20:42
(Received via mailing list)
On Fri, 10 Oct 2008 15:29:02 -0500, Matthew Moss 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

   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
9b905791cbdbb1af35b65e02c3217e23?d=identicon&s=25 toomln (Guest)
on 2008-10-12 21:00
(Received via mailing list)
> ## 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
289cf19aa581c445915c072bf45c5e25?d=identicon&s=25 Todd Benson (Guest)
on 2008-10-12 22:04
(Received via mailing list)
On Fri, Oct 10, 2008 at 10:13 AM, Matthew Moss <matt@moss.name> 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
B63501aa235ec0a016402b3d78543088?d=identicon&s=25 Andrea Fazzi (remogatto)
on 2008-10-12 23:29
(Received via mailing list)
Matthew Moss 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/17...

Bye.
Andrea
Ef3aa7f7e577ea8cd620462724ddf73b?d=identicon&s=25 Rob Biedenharn (Guest)
on 2008-10-13 00:16
(Received via mailing list)
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@AgileConsultingLLC.com
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2008-10-13 01:12
(Received via mailing list)
On Sun, 12 Oct 2008 15:00:27 -0500, Todd Benson 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
289cf19aa581c445915c072bf45c5e25?d=identicon&s=25 Todd Benson (Guest)
on 2008-10-13 05:12
(Received via mailing list)
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
B63501aa235ec0a016402b3d78543088?d=identicon&s=25 Andrea Fazzi (remogatto)
on 2008-10-13 10:35
(Received via mailing list)
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/17...

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
31e038e4e9330f6c75ccfd1fca8010ee?d=identicon&s=25 Gregory Brown (Guest)
on 2008-10-13 19:18
(Received via mailing list)
On Fri, Oct 10, 2008 at 11:13 AM, Matthew Moss <matt@moss.name> 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
This topic is locked and can not be replied to.