Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re: A mod2 Machine.

by Laurent_R (Abbot)
on Jul 07, 2013 at 22:04 UTC ( #1043016=note: print w/replies, xml ) Need Help??

in reply to A mod2 Machine.

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.

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

    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.

      I think we agree.

      My point is that I was using the ^ logical operation on actual binaries, something very similar to what you showed:

      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).

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1043016]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (7)
As of 2017-02-25 10:09 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (365 votes). Check out past polls.