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

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.

Answer 2

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;
}

Answer 3

I'm not in a position to measure right now, but you should be able to eke out some additional speed with this:

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

edit: ignore me -- Adam's bitshifting answer should be superior.

Answer 4

function int2coord_3($i){
    return array((int) ($i / 8), ($i % 8));
}

this is a little faster because there is no var declaration and affectation.

Answer 5

I think most of your performance is lost by returning array(...) at the end. Instead, I propose:
* define two functions, one for x and one for y
    or
* inline the bit arithmetic in code needing the calculation