|Perl: the Markov chain saw|
Re: A mod2 Machine.by Laurent_R (Monsignor)
|on Jul 07, 2013 at 22:04 UTC||Need Help??|
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.