in reply to A mod2 Machine.

Thanks for this very thought-provoking write up. It is questioning many of my beliefs and it is good to go back and check on them. For example, The advantage of this mod2 machine is that, there are no mathematical operations, thereby executing faster. is just the opposite of what I would have thought. My background is more C/C++ so before checking the last digit, one has to turn a simple number into something much more complex, a string, and then do some operations on it. I would also have thought that most mathematical operations are in hardware nowadays and should take almost no time. But these assumptions might not be valid in Perl where translating between numbers and strings is build in already.

There is a good article on Wikipedia on divisibility rules: http://en.wikipedia.org/wiki/Divisibility_rule (for the non-mathematicians...).

As for the generalization of your idea, I am a bit sceptical. "Check the last digit" does only work for mod2 and mod5 and not even in all bases. For example, 11 base 3 is an even number (4). 14 base 16 is divisible by 5 (20). Other rules are more complex and also depend on the base. The divisibility rules for 3 and 9 based on the sum of the digits rely on 10**n % 3 = 1 and 10**n % 9 = 1. In base 3 a number is divisible by 3 if the last digit is 0.

Another thing I am wondering is whether the speed-up does rely on providing an outright string into the regex? So how does 

"112358" =~ /['0' | '2' | '4' | '6' | '8']$/i ? print "even\n" :  prin
+t "odd\n";

[download]

compare to 

my $n = 112358;
$n =~ /['0' | '2' | '4' | '6' | '8']$/i ? print "even\n" :  print "odd
+\n";

[download]

It would be great if someone familiar with Perl's inner workings could comment on this.

Replies are listed 'Best First'.
Re^2: A mod2 Machine.
by code-ninja (Scribe) on Jul 04, 2013 at 07:22 UTC

    Even in C, we can do this without any conversions (i.e. convert a number to string) we can directly read a string and do this 

    #include <stdio.h>
#include <string.h>
int main(int argc, char **argv)
{
char *str = malloc(strlen(argv[1]);
strcpy(argv[1], str);
char last = str[strlen(str) - 1];
switch (last){
case '0':
case '2':
case '4':
case '6':
case '8':
case 'A':
case 'a':
case 'C':
case 'c':
case 'E':
case 'e': printf("even\n"); break;
default: printf("odd\n"); break;
}

    [download]

    A caveat, in search of a better word, would be the string allocation and copying routine. I used the standard string library functions but it will still take time even though the actual logic (the switch statement) is really fast.

    As for the generalization of the idea, yes, this logic is applicable only for mod2 and mod5 machines where only 2 states are sufficient. And yeah, this is applicable for all bases that are of the form 2^n and base 10 (example, convert 112358 base 10 to base 32 and 11235813 base 10 to base 32).

    For bases >16, we need to go beyond `F' for example, in base 32, 15 base 10 will be represented as F and 16 as G. Therefore, in base 32, if the number ends with a G, it is even.

[reply]
[d/l]
[select]

      Correct, if you have the number as a string already, you do not need to convert the number to a string.

      You do not need to copy the string though, you could get the last character directly from argv[1] in your example.

[reply]
[d/l]
Re^2: A mod2 Machine.
by code-ninja (Scribe) on Jul 04, 2013 at 17:31 UTC
    I was wondering about what you said: whether the speed-up does rely on providing an outright string into the regex 

    my $n = 112358;
...

    [download]

    I guess, it does rely on it. Not much but look at it from the processor's perspective. It is an assignment operation hence there will be an extra "mov" instruction moving data from the accumulator to say the DX register, right? Whereas providing an outright string will take data directly from the accumulator.

    Note

    My explanation is open for abuse... :D

[reply]
[d/l]

In Section Meditations