From: Ken Bloom Date: 2008-10-13T08:07:34+09:00 Subject: Re: [QUIZ] Modular Arithmetic (#179) 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 >> >> . >> >> 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/