Optimizing PHP algorithm

Question

I have built a class that finds the smallest number divisible by a all numbers in a given range.

This is my code:

class SmallestDivisible
{

    private $dividers = array();

    public function findSmallestDivisible($counter)
    {
        $this->dividers = range(10, 20);

        for($x=1; $x<$counter; $x++) {

            if ($this->testIfDevisibleByAll($x, $this->dividers) == true) {
                return $x;
            }
        }
    }

    private function testIfDevisibleByAll($x, $dividers)
    {
        foreach($dividers as $divider) {
            if ($x % $divider !== 0) {
                return false;
            }
        }

        return true;
    }
}

$n = new SmallestDivisible();

echo $n->findSmallestDivisible(1000000000);

This class finds a number that is divisible by all numbers in the range from 1 to 20 ($this->dividers).

I know it works well as I tested it with other, lower ranges, but, unfortunately, it is not able to find the solution for range(10, 20) within 30 seconds - and this is the time after which a PHP script is halted.

A parameter that is fed to the findSmallestDivisible method is the ceiling of the group of numbers the script is going to inspect (e.i. from 1 to $counter (1000000000 is this execution)).

I would be grateful for suggestions on how I can optimize this script so that it executes faster.

Consider asking optimization questions for working code on codereview.stackexchange.com — kojiro
– kojiro, Commented Mar 5, 2015 at 14:41
(Also, the time after which a PHP script is halted is configurable) — kojiro
– kojiro, Commented Mar 5, 2015 at 14:42
@kojiro, I really wish for the script to execute within 30 seconds time limit. — luqo33
– luqo33, Commented Mar 5, 2015 at 14:50
@andy, I know only that the script doesn't find the sought after number within 30 seconds. — luqo33
– luqo33, Commented Mar 5, 2015 at 14:50

Niet the Dark Absol · Accepted Answer · 2015-03-05 14:51:33Z

3

Your solution is brute-force and simply horrible.

Instead, how about handling it mathematically? You're looking for the lowest common multiple of numbers in your range, so...

function gcd($n, $m) {
   $n=abs($n); $m=abs($m);
   list($n,$m) = array(min($m,$n),max($m,$n));
   while($r = $m % $n) {
      list($m,$n) = array($n,$r);
   }
   return $n;
}
function lcm($n, $m) {
   return $m * ($n/gcd($n,$m));
}

function lcm_array($arr) {
   while(count($arr) > 1) {
      array_push($arr, lcm(array_shift($arr),array_shift($arr)));
   }
   return array_shift($arr);
}

var_dump(lcm_array(range(10,20)));
// result int(232792560)

This means your original code would have had to do 232,792,560 iterations, no wonder it took so long!

answered Mar 5, 2015 at 14:51

Niet the Dark Absol

326k86 gold badges480 silver badges604 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

luqo33 Over a year ago

This is surely the way to go. I really need to practice my mathematical-thinking skills. I tend to write brute-force algorithms for problems that I encounter. They often work, but they are not I wish to write my name under :) Thank you!

luqo33 Over a year ago

@niet, could you possibly provide some explanation on what your code does in each step - maybe in the form of in-code comments?

axiac · Accepted Answer · 2015-03-05 15:08:23Z

1

Your goal is an easy mathematical calculation named the least common multiple but using brute force to compute it is totally wrong (as you already found out).

The Wikipedia page lists several reasonable algorithms that can be used to compute it faster.

The one explained in the section "A method using a table" is really fast and doesn't require much memory. You keep only the leftmost column of the table (the numbers you want to get the lcm for) and the rightmost column (the current step). If you implement it I suggest you hardcode a list of prime numbers into your program to avoid computing them.

edited Mar 5, 2015 at 15:08

answered Mar 5, 2015 at 14:59

axiac

73.4k11 gold badges120 silver badges150 bronze badges

Comments

luqo33 · Accepted Answer · 2015-03-06 16:08:22Z

Here is another solution I came up with.

In short, the algorithm will calculate LCM (lesast common multiple) for a group of numbers.

class Lcmx
{

    public $currentLcm = 0;

    private function gcd($a, $b)
    {
        if ($a == 0 || $b == 0)
            return abs( max(abs($a), abs($b)) );

        $r = $a % $b;
        return ($r != 0) ?
            $this->gcd($b, $r) :
            abs($b);
    }   

    private function lcm($a, $b)
    {
        return array_product(array($a, $b)) / $this->gcd($a, $b);
    }

    public function lcm_array($array = array())
    {
        $factors = $array;  
        while(count($factors) > 1) {

            $this->currentLcm = $this->lcm(array_pop($factors), array_pop($factors));
            array_push($factors, $this->currentLcm);
        }

        return $this;

    }
}

$l = new Lcmx;
echo $l->lcm_array(range(1, 20))->currentLcm;
//232792560

Collectives™ on Stack Overflow

Optimizing PHP algorithm

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related