[SUMMARY] Modular Arithmetic (#179)

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

  1. Matthew Moss

    Matthew Moss Guest

    Apologies for the severely late summary.



    I'm going to examine the solution from _Andrea Fazzi_ for this week's
    quiz. It's quite simple and easy to follow, and it is quite similar to
    some of the other solutions. (Note that I'll examine this in a
    different order than Andrea's presentation, but it does not affect the
    solution.)

    First, initialization:

    class Modulo

    def initialize(n = 0, m = 26)
    @n, @m = n % m, m
    end

    def to_i
    @n
    end

    This is pretty straightforward; Andrea stores the numeric value and
    the modulus, and provides a way to convert the class to an integer. As
    `@n` is returned without using the modulus operator, care must be
    taken to always assign `@n` correctly. The initializer does this, and
    is the only assignment to `@n` here, so it's safe.

    Next, comparison operations:

    include Comparable

    def <=>(other_n)
    @n <=> other_n.to_i
    end

    Andrea makes use of the `Comparable` module, which supplies the
    various comparison operators provided the class provides the `<=>`
    operator. Since this is essentially dealing with integers, it simply
    performs the `<=>` on the integer portions. We know `@n` is an
    integer, and the call to `to_i` ensures the right-hand side is an
    integer as well.

    Next, arithmetic:

    [:+, :-, :*, :**].each do |meth|
    define_method(meth) { |other_n| Modulo.new(@n.send(meth,
    other_n.to_i), @m) }
    end

    A nice little bit of metaprogramming is shown here. Andrea uses the
    `define_method` method defined on `Module`, of which `Class` is a
    subclass. (Confused yet?) Since each of the arithmetic operators will
    look basically the same, this removes redundancy and reduces the
    amount of code. The alternative would have been this:

    def +(other_n)
    Modulo.new(@n + other_n.to_i, @m)
    end

    But repeat that for every operator. Using `define_method` inside the
    loop removes the redundant code and, potentially, will support other
    operators by simply adding them to the list. The only other cost, so
    to speak, is that you must use `send` to replace actual use of the
    operator, but this is certainly something every Ruby programmer knows,
    or should know.

    If the class ended there, most basic use would be covered... at least
    until someone tried `3 + Modulo.new(5)` instead of `Modulo.new(5) +
    3`. That's because integers don't know anything about the `Modulo`
    class. Fortunately, there is a nice technique available for dealing
    with this issue:

    private

    def coerce(numeric)
    [numeric, @n]
    end

    end

    The example `3 + Modulo.new(5)` is equivalent to `3.send:)+,
    Modulo.new(5))`. The integer `3` doesn't know what a `Modulo` object
    is, so it calls `coerce`. That is, `Modulo.new(5).coerce(3)`. It's now
    the responsibility of `Modulo#coerce` to provide values that integer
    addition can deal with. As shown, Andrea returns an array of the
    original first argument (currently in `numeric`) and the value of the
    `Modulo` object (in `@n`). This is sufficient for integer addition to
    work, which will produce the expected value `8`.

    So ends Andrea's `Modulo` class. This design is similar to most of the
    others, and follows the convention I suggested on the mailing list:
    that the left argument of any arithmetic operation determines the
    result's type. So `Modulo.new(5) + 3` generates a new `Modulo` object,
    while `3 + Modulo.new(5)` generates a new integer. Both have a value
    of 8, but this non-communitivity could potentially become confusing.
    Consider if you were adding two `Modulo` objects, one using a modulus
    of 26, the other a modulus of 10? What should the result be? Someone
    who didn't know or expect the left-hand-side rule might get unexpected
    results.

    The solution from _Ken Bloom_ addresses this by providing
    `ModularBase`. This module provides:

    1. A way to create "modulo" factories, to ease the creation of
    multiple values using the same modulus.
    2. All the methods needed to perform arithmetic and comparisons.
    3. A way to check that two modulo values were created from the same
    `ModularBase`.

    The last ensures that confusion can't occur when mixing bases. Such
    operations simply won't work, and will instead throw an exception.
    Note that this does not completely prevent a developer from mixing
    bases, but he must now be explicit about it.

    Mod26 = ModularBase.new(26)
    Mod11 = ModularBase.new(11)

    a = Mod26.new(23)
    b = Mod11.new(179)
    puts a + b # This raises an incompatible bases
    ArgumentError...

    puts a + b.to_i # ... but this is safe.

    And Ken also promotes all operations involving integers to
    `ModularBase` instances as well, a nice feature. (See his `coerce` for
    how this works.)

    Thanks for the submissions. Tomorrow, a little more "elementary"
    mathematics...
     
    Matthew Moss, Oct 17, 2008
    #1
    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:
    486
    Michael Spencer
    Jan 22, 2005
  2. Tuvas
    Replies:
    20
    Views:
    1,002
    Tuvas
    Mar 6, 2006
  3. Simon Brooke

    J2ME location api (jsr 179) - where?

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

    [QUIZ] Modular Arithmetic (#179)

    Matthew Moss, Oct 10, 2008, in forum: Ruby
    Replies:
    13
    Views:
    253
    Gregory Brown
    Oct 13, 2008
Loading...

Share This Page