Alternative/faster methods of converting an integer to a cartesian coordinate?

Question

As a fun side-project for myself to help in learning yet another PHP MVC framework, I've been writing Reversi / Othello as a PHP & Ajax application, mostly straightforward stuff. I decided against using a multidimensional array for a number of reasons and instead have a linear array ( in this case 64 elements long ) and a couple methods to convert from the coordinates to integers.

So I was curious, is there any other, possibly faster algorithms for converting an integer to a coordinate point?

function int2coord($i){
    $x = (int)($i/8);
    $y = $i - ($x*8);      
    return array($x, $y);
}

//Not a surprise but this is .003 MS slower on average
function int2coord_2($i){
    $b = base_convert($i, 10, 8);
    $x =  (int) ($b != 0 ? $b/8 : 0); // could also be $b < 8 for condition
    $y = $b % 10;
    return array($x, $y);
}

And for posterity sake, the method I wrote for coord2int

function coord2int($x, $y){
   return ($x*8)+$y;
}

Update:
So in the land of the weird, the results were not what I was expecting but using a pre-computed lookup table has predominantly shown to be the fastest, guess trading memory for speed is always a winner?

• There was a table with times here but I cut it due to styling issues with SO.

Answer 1

Oh yes! This is a perfect example of binary:

function int2coord($i){
    $x = $i >> 3;
    $y = $i & 0x07;      
    return array($x, $y);
}

The reality is that a good compiler will find this optimization and use it, so it's not necessarily faster. Test and see if your compiler/interpreter does this.

It works because any binary division by 8 is the same as a right shift by 3 bits. Modern processors have barrel shifters that can do up to a 32 bit shift in one instruction.

The reverse is as easy:

function coord2int($x, $y){
   return ($x << 3)+$y;
}

-Adam

Answer 2

I don't have the time to measure this myself right now, but I would suspect that a pre-computed lookup table would beat your solution in speed. The code would look something like this:

class Converter  {
    private $_table;

    function __construct() 
    {
        $this->_table = array();
        for ($i=0; $i<64; $i++) {
            $this->_table[$i] = array( (int)($i/8), (int)($i%8) ); 
        }
    }

    function int2coord( $i )
    {
        return $this->_table[$i];
    }
}

$conv = new Converter(); 
$coord = $conv->int2coord( 42 );

Of course, this does add a lot of over-head so in practice you would only bother to pre-compute all coordinates if you conversion code was called very often.