Optimizing Base Conversion Loop

Question

So, for my Cryptography Library, I have a base converter that I use quite often. It's not the most efficient thing in the world, but it works quite well for all ranges of input.

The bulk of the work is done by the callback loop:

    $callback = function($source, $src, $dst) {
        $div       = array();
        $remainder = 0;
        foreach ($source as $n) {
            $e         = floor(($n + $remainder * $src) / $dst);
            $remainder = ($n + $remainder * $src) % $dst;
            if ($div || $e) {
                $div[] = $e;
            }
        }
        return array(
            $div,
            $remainder
        );
    };
    while ($source) {
        list ($source, $remainder) = $callback($source, $srcBase, $dstBase);
        $result[]                  = $remainder;
    }

Basically, it takes an array of numbers in $srcBase and converts them to an array of numbers in $dstBase. So, an example input would be array(1, 1), 2, 10 which would give array(3) as a result. Another example would be array(1, 0, 0), 256, 10 which would give array(1, 6, 7, 7, 7, 2, 1, 6) (each element of the array is a single "digit" in the $dstBase.

The problem I'm now facing, is if I feed it 2kb of data, it takes almost 10 seconds to run. So I've set out to optimize it. So far, I have it down to about 4 seconds by replacing that whole structure with this recursive loop:

    while ($source) {
        $div       = array();
        $remainder = 0;
        foreach ($source as $n) {
            $dividend  = $n + $remainder * $srcBase;
            $res       = (int) ($dividend / $dstBase);
            $remainder = $dividend % $dstBase;
            if ($div || $res) {
                $div[] = $res;
            }
        }
        $result[] = $remainder;
        $source   = $div;
    }

The problem I'm facing, is how to optimize it further (if that's even possible). I think the problem is the shear number of iterations it takes for the large input (for a 2000 element array, from base 256 to base 10, it takes 4,815,076 iterations in total).

Any thoughts?

Answer 1

Yes, it can be optimized a little:

$source_count = count($source);
while ($source) {
    $remainder = $i = 0;
    foreach ($source AS &$n) {
        $dividend = $n + $remainder * $srcBase;
        $remainder = $dividend % $dstBase;
        $res = ($dividend - $remainder) / $dstBase;
        if ($i || $res)
            $source[$i++] = $res;
    }
    for ($j=$i; $j < $source_count; $j++)
        unset($source[$i]);
    $source_count=$i;
    $result[] = $remainder;
}

or even faster, but more obscure:

$source_count = count($source);
while ($source) {
    $remainder = $i = 0;
    foreach ($source AS &$n) {
        if (($res = ($dividend - ($remainder = ($dividend = $n + $remainder * $srcBase) % $dstBase)) / $dstBase) || $i)
            $source[$i++] = $res;
    }
    for ($j=$i; $j < $source_count; $j++)
        unset($source[$i]);
    $source_count=$i;
    $result[] = $remainder;
}

You will get some memory and CPU usage reduction and it is much more fun but of cource unreadable (:.

But personally I think you are doing it the wrong way. I think you should use some fast C code for this kind of task(by using system call or writing/installing existing PHP module). And I think that code optimizers/compilers like Hip-Hop PHP,Zend Optimized etc. can dramatically increase performance in this case.

Answer 2

99.9% of the time taken to execute this script originates from the inherent need to iterate through an input. Since the code inside the foreach is very basic, the only way of decreasing execution time is to reduce the number of iterations. If that is not possible, then you have the most efficient version of this function.

Answer 3

I'm not sure, but

$dividend  = $remainder * $srcBase + $n;

could be a little bit faster...