What is a mod2 machine?

If I put it in extremely layman's term, it is a state machine that switches from low to high (or 0 to 1 or "foo" to "bar" or... ) if the input is divisible by 2.

Now, let's say we have a set of numbers from different bases (i.e. a mix of decimal, octal and hexadecimal numbers) and we need to extract even (odd) numbers.

Most obvious (easiest) solution

use strict; use warnings; if(112358 % 2 == 0){ print "even\n"; } else { print "odd\n"; }

What's the problem with this code?

Now, the problem with this code is it accepts the number as whole. To explain more clearly, we use a bona fide integer and it will be treated mathematically, hence taking more time... hold this thought for a moment, it will be proven soon.

Enter mod2 Machine logic.

Now, a number (no matter the base) is even if its last digit is even. Therefore, any number ending in {0, 2, 4, 6 ,8, A, C, E} will be an even number (I guess I do not need to prove this point). So this time we read a string and jump state to "even" if the last character is any one of the above list. The advantage of this mod2 machine is that, there are no mathematical operations, thereby executing faster.

#!/usr/bin/perl # mod2 Machine. use strict; use warnings; "112358" =~ /['0' | '2' | '4' | '6' | '8']$/i ? print "even\n" : +print "odd\n"; # if we add 'A' | 'C' | 'E' to the list, it can handle hexadecimals as + well.

On my Linux Mint (kernel 3.x), this is what it looks like. "evenodd.pl" is the mod2 Machine whereas "evenodd1.pl" uses the mathematical logic. Clear enough, there is a slight improvement, but imagine if the number is 1500 figures long? There will be significant reduction in execution time as there will be no mathematical operations and we are just interested in last character... only one comparison is enough to judge whether or not the number is even.

We can even classify a whole string as even or odd. Just out of the wild, I dream of creating a code that can learn. It will classify each answers to questions (or reply to certain phrases) as "polite" (even) or "naughty/rude" (odd) and then produce appropriate response. It's o.k. to pass away into the fantasy world.

Conclusion

Similar logic can be designed for checking divisibility of other numbers for example a mod3 machine will check for numbers that are divisible by 3. We can use the same "look at the last character only" logic or the fact that a number is divisible by 3 if the sum of digits of that number is divisible by 3. These machines will be faster because they tend to avoid mathematical operations.

UPDATES

What I meant by bona fide integer (I actually wanted to write "number" over here) is very simple. In the first code, 112358 means (assuming base 10)
( 8 * 1 + 5 * 10 + 3 * 100 + 2 * 1000 + 1 * 10000 + 1 * 100000 )
i.e. it is a mathematical figure. Whereas in the second code, "112358" is just a string of characters. The second code can even compare a string like "A quick brown fox jumped over the lazy dog." and classify it as even or odd.

Divisibility rule for 3 can verified here


In reply to A mod2 Machine. by code-ninja

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.