|
Re: A mod2 Machine.
by choroba (Cardinal) on Jul 04, 2013 at 00:07 UTC
|
1
Rate mod machine
mod 1949318/s -- -55%
machine 4329004/s 122% --
2
Rate machine mod
machine 1428571/s -- -23%
mod 1851852/s 30% --
3
Rate machine mod
machine 204666/s -- -89%
mod 1848429/s 803% --
4
Rate machine mod
machine 974659/s -- -48%
mod 1858736/s 91% --
5
Rate mod machine
mod 1855288/s -- -9%
machine 2044990/s 10% --
7
Rate machine mod
machine 224517/s -- -88%
mod 1845018/s 722% --
10
Rate mod machine
mod 1851852/s -- -39%
machine 3058104/s 65% --
11
Rate machine mod
machine 209820/s -- -88%
mod 1801802/s 759% --
| [reply]
[d/l]
[select] |
Re: A mod2 Machine.
by BrowserUk (Patriarch) on Jul 04, 2013 at 00:10 UTC
|
$MAX=1e7;
cmpthese -1, {
a => q[
my $c = 0;
$_%2 and ++$c for 0 .. $MAX;
print "a:$c"
],
b => q[
my $c = 0;
$_ =~ m[[02468]$] or ++$c for 0 .. $MAX;
print "b:$c"
]
};;
a:5000000
a:5000000
b:5000000
b:5000000
s/iter b a
b 3.50 -- -64%
a 1.27 177% --
$MAX=1e8;
cmpthese -1, {
a => q[my $c = 0; $_%2 and ++$c for 0 .. $MAX; print "a:$c" ],
b => q[ my $c = 0; $_=~ m[[02468]$] or ++$c for 0 .. $MAX; print "
+b:$c" ]
};;
a:50000000
a:50000000
b:50000000
b:50000000
s/iter b a
b 34.3 -- -64%
a 12.3 179% --
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l] |
Re: A mod2 Machine.
by hdb (Monsignor) on Jul 04, 2013 at 05:49 UTC
|
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";
compare to
my $n = 112358;
$n =~ /['0' | '2' | '4' | '6' | '8']$/i ? print "even\n" : print "odd
+\n";
It would be great if someone familiar with Perl's inner workings could comment on this.
| [reply]
[d/l]
[select] |
|
|
#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;
}
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] |
|
|
I was wondering about what you said: whether the speed-up does rely on providing an outright string into the regex
my $n = 112358;
...
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.
NoteMy explanation is open for abuse... :D | [reply]
[d/l] |
Re: A mod2 Machine.
by ww (Archbishop) on Jul 03, 2013 at 23:14 UTC
|
| [reply]
[d/l] |
Re: A mod2 Machine.
by Lawliet (Curate) on Jul 04, 2013 at 00:45 UTC
|
a bona fide integer will be treated mathematically, hence taking more time
...more time in a small enough base. Given a base that requires twice the number of symbols needed to represent every digit than the number of operations it takes to compare one symbol to every symbol, your statement doesn't hold (italics for readability).
Just poking fun. I thought it was a good writeup and an interesting observation ;).
| [reply] |
Re: A mod2 Machine.
by choroba (Cardinal) on Jul 04, 2013 at 07:09 UTC
|
/['0' | '2' | '4' | '6' | '8']$/i
A string ending in |, ' or a space is not even. Digits do not have upper and lower case variants.
/[02468]$/
| [reply]
[d/l]
[select] |
|
|
/[02468ace]$/i;
/i is now significant. | [reply]
[d/l]
[select] |
Re: A mod2 Machine.
by RichardK (Parson) on Jul 04, 2013 at 12:01 UTC
|
I have to disagree with you conclusions, you're just not comparing like with like.
Which technique is faster depends entirely on the data format. If the data is in binary then you will only have to test the least significant bit, and one bit test will be faster than comparing the last digit against a list of alternatives.
OTOH converting text to binary then performing a mathematical operation may be slower than just operating on the text directly. But you will have to identify the last digit in the text and so will probable be running a regex, which are complex and therefore take time.
So exactly which approach is faster will depend on many factors and will take comprehensive testing to determine which is best.
Modern processors are highly complex and highly optimised and just assuming that mathematical operations are slow is a mistake. You really have to carefully test your code to determine which approach is better in any particular situation. And even they you've only optimised it for one platform if you want your code to portable then that's even more difficult.
In general it's much better to design a simple algorithm that's easy for a human to understand and let the interpreter/compiler & processor work out the best way to run it. Compilers and processors have lots of very clever optimization techniques and they are usually better at turning source code into running code that we are, so let them do their job.
The conclusions you should draw are
- It's better to choose an algorithm that matches the data format.
- choosing the wrong algorithm could be slow.
- Don't second guess the processor/compiler -- test it properly.
- designing good tests is hard.
| [reply] |
|
|
If the data is in binary, the data will be even if its LSB is 0. The mod2 logic does exactly that. For data in the binary format, it is checking the LSB instead of converting the number to decimal or doing other exotic things. You're right about one bit test but then I'm using the mod2 logic to handle all kinds of numbers (where all kinds == {decimal, octal, hexadecimal, binary}).
my $n = 534587;
print "even\n" if($n % 2 == 0);
This will print nothing on the screen (obviously, it indicates that the number is odd) and no matter how fast the processor is, the condition inside "if" will actually be evaluated i.e. 534587 will actually be divided by 2 and the remainder will be compared with 0. Do any compiler/processor optimization, this fact will not change (afaik, that is to say).
OTOH,
my $n = "534587";
print "even\n" if ($n =~ /[02468]$/);
there are no mathematical evaluations here, no matter how big the string is, the regex here just checks last character. There will be no need of actually calculating the remainder and comparing.
I'm not saying that processor will take time to evaluate a mathematical expression, it will be derogatory to think that about modern processors. I'm just trying to stress on the fact mod2 machine circumvents any mathematical operation.
This algorithm does fail if the bases are not of the form of 2^n or base 10. Also, as ww said, it will fail for base 3 numbers on a quantum computer | [reply]
[d/l]
[select] |
Re: A mod2 Machine.
by Laurent_R (Canon) on Jul 07, 2013 at 22:04 UTC
|
Interesting discussion, but it is not necessary that clear that arithmetic operations should be slower.
I had a discussion on a French Perl forum a few months ago about the modelisation of a game. Without going too much in details, the game is played on a 4x4 grid with stones which have a white and a black side. At the start, each of the 16 positions has a stone, either white or black. Each time the player plays, she or he can flip some of the stones in accordance with some rules (you may flip all the stones of a row, all the stones of a column, all the stones of the two diagonals, plus some other patterns, in total 46 authorized moves). The aim is to get to all stones being white. It can be demonstrated that with any start position, given the set of authorized moves, it is always possible to win in 5 moves or less.
The discussion on the forum soon converged on the idea that the game can be represented in binary. For example, a start position where all the stones are black can be represented as 1111 1111 1111 1111 and the winning position where they are all white would be 0000 0000 0000 0000. Similarly a move could be represented as a binary: flipping the first row might be the binary 1111 0000 0000 0000. Executing a move is then a simple exclusive or (xor) between the original position and the move. So that applying the move just given on the initial position would lead to this new position: 0000 1111 1111 1111.
The issue I am coming at is that, in this discussion, two or three persons were thinking of binary strings, i.e. strings made of 0 and 1. My idea was that it was much better to use actual binary numbers. Any position can be represented as a number between 0 (the winning position) and 2^16 - 1, i.e. 65535 in decimal notation. Similarly, the moves can be represented by some 46 numbers between 0 and 65535. In this case, applying a move consists simply in using the ^ operator between the position and the move, which ought to be faster than doing the equivalent thing on a binary string (there were other reasons for chosing real binary number, including memory usage, etc.).
Anyway, to try to prove my point that using real binary numbers and the ^ operator was better, I needed to compare it with various means of doing the same thing with binary strings. I benchmarked about a dozen different ways to apply a move to a position with binary strings (using regex, arithmetics, etc.). I may not have found the best way to do it, but the best I found, by far, was to add the position string to the move string, and then use tr/// to changes the 2's into 0's. For example, position 1111111111111111 and move 1111000000000000 can be added to give 2222111111111111, yielding 0000111111111111 after the 2 to 0 substitution.
My point is just that in such a case, the best solution I found for making an exclusive or on binary strings was an arithmetic addition followed by a character substitution. Any solution using regexes or trying to break the binary string into individual elements was far far slower. Now, of course, my experiments might just prove that I was not clever enough on how to do this exclusive or on two binary strings efficiently.
Just in the event that you are interested, the true binary xor was between 4 and 5 times faster than the best binary string xor I could come up with. But that is not my point today.
I just wanted to say that there are cases where arithmetic operations seem to turn out to be faster than character or string operations. Granted, we are quite far from the OP situation, but I thought this experience might bring some food for thought.
| [reply] |
|
|
Ok, I'll be more clear. First, when I said that the arithmetic operation will take more time, I said it with respect to the mod2 machine. Second, let's take your example (just a wild guess, is this game GO)
#!/usr/bin/perl
# note that %b modifier processes binary. Similarly, %x processes hexa
+decimal and %o is for octal.
use strict;
use warnings;
my ($move, $pos);
$move = 0b1111111111111111;
$pos = 0b0000111111111111;
printf "%b\n", ($move ^ $pos);
Even here, there are no arithmetical operations. Note that Exclusive Or is a logical operation. This is somewhat similar to a mod machine. You change state only if there are opposite inputs. The catch here is, if we'd have used strings instead of a number, there would've been a few more lines of code, keeping in mind and as you said, breaking the string and using regexes. I'm not saying that we should replace every arithmetic operation with string/logical operation, we just can't, I'm just trying to convey that there are better ways to do simple things that school teaches us in a very dogmatic way.
I mean seriously, why should I actually divide a number by 2 and check the remainder when I can directly check the last digit?! Or why should I recursively divide and mod by 10 to generate the reverse of a number when I can do it in one line?!
/* Apologies for using C, but its my "mother-tongue" :P */
#include <stdio.h>
int main(int argc, char **argv)
{
int ;
for(i = (strlen(argv[1]) - 1); i >= 0; i--){
printf("%c", *(argv[1] + i)); /* reverse a string, a number, a
+ sentence, a novel... */
}
}
Note/PS:
Logical operations, too, are faster than arithmetical operations afaik.
| [reply]
[d/l]
[select] |
|
|
my ($move, $pos);
$move = 0b1111111111111111;
$pos = 0b0000111111111111;
printf "%b\n", ($move ^ $pos);
But I needed to show that using actual binaries, such as 0b0000111111111111 was far superior to using binary strings, i.e. something like "0000111111111111". To do this, I needed to find the best possible way to do the equivalent of ^ for strings. And it turned out that the fastest way I found was to add the strings (meaning an implicit conversion of the string to a digit), giving a result like 1111222222222222, and then (with another implicit conversion) replacing the twos by zeros (with a command like tr/2/0/) to finally get "1111000000000000". And that was four times slower than the logical ^ on actual binaries. But it was still the fastest way to do it on strings. So that, in that case, arithmetics was faster than, for example, regexes or splitting the strings into individual characters to process them one by one..
I mean seriously, why should I actually divide a number by 2 and check the remainder when I can directly check the last digit?!
I definitely agree with you on that. I was only saying that there are some other cases where arithmetics is faster than other means. Although, in my case, the best, by far, was to use actual binary nombers and a logical exclusive or (4 fimes faster than artithmetics on binary strings).
| [reply]
[d/l] |
Re: A mod2 Machine.
by nonsequitur (Pilgrim) on Jul 12, 2013 at 10:15 UTC
|
This may be OT since it doesn't really have anything to do with Perl,
but one of your original assumptions is wrong.
In an even base a integer ending in an even digit must be even because
the previous digits are multiplied by a power of an even base .
Leaving the last digit to decide the parity.
In an odd base the total of the digits must be even for the integer to
be even because all of the digits are multiplied by a power of an odd base so
that the that the parity of the integer depends on parity of all the digits.
| [reply] |
|
|
hmm... hmm... umm... I said this algorithm will work for all bases of the form 2^n and base 10. But according to you, this algorithm will work if the base is of the form 2*n. I'll just clarify right after commenting. Hold on...
UPDATE
apologies, my assumption was wrong. This algorithm will work, i.e. produce correct output, if the base is of the form 2*n.
| [reply] |
Re: A mod2 Machine.
by zork42 (Monk) on Jul 10, 2013 at 10:37 UTC
|
I wonder how the speed of
my $n = 534587;
print "even\n" if($n % 2 == 0); # modulo operator of possibly a flo
+at or possibly an integer (*)
compares with
use integer;
my $n = 534587;
print "even\n" if($n & 1 == 0); # checking LSB with Bitwise And on
+an integer
(*) perlop: Integer-Arithmetic says
"By default, Perl assumes that it must do most of its arithmetic in floating point."
=====
Also I wonder how this
my $n = "534587";
print "even\n" if($n =~ /[02468]$/); # reg exp
compares with:
my $n = "534587";
my $c = substr($n, -1, 1); # last char
print "even\n" if ( ($c == '0') || ($c == '2') || ($c == '4') || ($c =
+= '6') || ($c == '8') ); # no regexp
| [reply]
[d/l]
[select] |
|
|
| [reply] |
|
|
I was just about to say that!
zork42 please do benchmark it and post the results.
PS: I'm really very lazy to do that and plus I'm busy perusing the perldoc's PerlRE tutorial. :)
| [reply] |
|
|
Re: A mod2 Machine.
by zork42 (Monk) on Jul 13, 2013 at 09:22 UTC
|
using floats to compute modulo does not seem reasonable to me.
I only included this:
my $n = 534587;
print "even\n" if($n % 2 == 0); # modulo operator of possibly a flo
+at or possibly an integer (*)
because
- it is equivalent to the OP's "Most obvious (easiest) solution" (infact code-ninja used this exact example here: Re^2: A mod2 Machine.)
- it might actually be doing a (possibly comparatively slow) float operation because use integer was not used.
It probably had to go: float 534587 --> integer 534587 --> integer modulo operation on integer 534587
Whereas doing a proper integer bit test should be faster:
use integer;
my $n = 534587;
print "even\n" if($n & 1 == 0); # checking LSB with Bitwise And on
+an integer
| [reply]
[d/l]
[select] |
|
|
Rate machine bitwise
machine 819199/s -- -43%
bitwise 1448690/s 77% --
| [reply]
[d/l]
[select] |