Jump to content

Challenge: Sieve of Eratosthenes, in PHP


ShadowMage

Recommended Posts

Ah! Eliminate the competitive side of this. Good idea. Naturally, my work is at home, and I am at work, so I can't post for a while. (I also have to port it to PHP.) I have a feeling these will look remarkably similar.

Link to comment
Share on other sites

  • Replies 55
  • Created
  • Last Reply

Well, I'll go ahead and post mine:

function SieveOfErat($n) {	//Construct the initial array	$arrSieve = array();	while (count($arrSieve) < $n-1)  {		array_push($arrSieve, count($arrSieve)+2);	}		//Filter out non-prime numbers	$index = 0;	while ($arrSieve[$index] <= sqrt($n)) {		$multiplier = 2;		$product = $arrSieve[$index] * $multiplier;		while ($product <= $n) {			foreach ($arrSieve as $i => $num) {				if ($num == $product) {					array_splice($arrSieve, $i, 1);					break;				}			}			$multiplier++;			$product = $arrSieve[$index] * $multiplier;		}		$index++;	}		return $arrSieve;}

Link to comment
Share on other sites

Shadow, I count more statements in yours than you count. But you can lose 7 of them if use the range() function as I do.If I'm counting correctly, with return statement, this comes to 21 statements.

function strike_multiples (&$arr, $denom) {   $len = count($arr);						  // 2   for ($i = $len - 1; $i >= $denom; --$i) {	// 5	  if ($arr[$i] % $denom == 0) {			 // 3		 array_splice($arr, $i, 1);			 // 1	  }   }}function getPrimes ($n) {   $i = 0;									  // 1   $p = 2;									  // 1   $primes = range($p, $n);					 // 1   while ($p * $p <= $n) {					  // 3	  strike_multiples ($primes, $p);		   // 1	  $i++;									 // 1	  $p = $primes[$i];						 // 1   }   return $primes;							  // 1}

Link to comment
Share on other sites

	function sieve($max) {		$numbers = range(2, $max); // 1		$k = 1; // 2		do {			$next_number = each($numbers); // 3			$next_number = $next_number[1]; // 4			$h = $k; // 5			$k++; // 6			do {				$j = $numbers[$h]; // 7				$remainder = $j % $next_number; // 8				$not_r = !$remainder; // 9				if ($not_r) { // 10					array_splice($numbers, $h, 1); // 11				}				$h++; // 12				$len = count($numbers); // 13				$more = $h < $len; // 14			} while ($more); // 15			$n_squared = pow($next_number, 2); // 16			$not_done = $n_squared < $max; // 17		} while ($not_done); // 18		return $numbers; // 19	}

Interestingly enough, my algorithm does not work for numbers under 17. Can you see why? :)

Link to comment
Share on other sites

I get 35 for your code:

function SieveOfErat($n) {	$arrSieve = array(); // 1	$count = count($arrSieve); // 2	$max_index = $n - 1; // 3	$more = $count < $max_index; // 4	while ($more)  { // 5		$sub_count = count($arrSieve); // 6		$to_push = $sub_count + 2; // 7		array_push($arrSieve, $to_push); // 8		$more = $count < $max_index; // 9	}	$index = 0; // 10	$current = $arrSieve[$index]; // 11	$root_n = sqrt($n); // 12	$more = $current <= $root_n; // 13	while ($more) { // 14		$multiplier = 2; // 15		$sub_current = $arrSieve[$index]; // 16		$product = $sub_current * $multiplier; // 17		$less = $product <= $n; // 18		while ($less) { // 19			do {				$e = each($arrSieve); // 20 (foreach loops are expensive)				if ($e) { // 21					$i = $e[0]; // 22					$num = $e[1]; // 23					$equal = $num == $product; // 24					if ($equal) { // 25						array_splice($arrSieve, $i, 1); // 26						break; // 27					}				}			} while ($e); // 28			$multiplier++; // 29			$sub_current = $arrSieve[$index]; // 30			$product = $sub_current * $multiplier; // 31			$less = $product <= $n; // 32		}		$index++; // 33		$more = $current <= $root_n; // 34	}	return $arrSieve; // 35}

Link to comment
Share on other sites

I get 35 for your code:
:) Ok, I think I lose! :)EDIT:I don't think you expanded that correctly, Synook. I copied your code from above, just to test it, and my script timed out. (I have the time limit set at 10 minutes) My original code runs in less than a second. (I'm testing using 15 as $n, so it should be fast)
Link to comment
Share on other sites

Ah whoops, I didn't write the while loops correctly. This is better:

<?phpfunction SieveOfErat($n) {	$arrSieve = array(); // 1	$count = count($arrSieve); // 2	$max_index = $n - 1; // 3	$more = $count < $max_index; // 4	while ($more)  { // 5		$sub_count = count($arrSieve); // 6		$to_push = $sub_count + 2; // 7		array_push($arrSieve, $to_push); // 8		$more = $sub_count < $max_index; // 9	}	$index = 0; // 10	$current = $arrSieve[$index]; // 11	$root_n = sqrt($n); // 12	$more = $current <= $root_n; // 13	while ($more) { // 14		$multiplier = 2; // 15		$sub_current = $arrSieve[$index]; // 16		$product = $sub_current * $multiplier; // 17		$less = $product <= $n; // 18		while ($less) { // 19			do {				$e = each($arrSieve); // 20 (foreach loops are expensive)				if ($e) { // 21					$i = $e[0]; // 22					$num = $e[1]; // 23					$equal = $num == $product; // 24					if ($equal) { // 25						array_splice($arrSieve, $i, 1); // 26						break; // 27					}				}			} while ($e); // 28			$multiplier++; // 29			$sub_current = $arrSieve[$index]; // 30			$product = $sub_current * $multiplier; // 31			$less = $product <= $n; // 32		}		$index++; // 33		$current = $arrSieve[$index]; //34		$more = $current <= $root_n; // 35	}	return $arrSieve; // 36}?>

Link to comment
Share on other sites

I can fix it thus:

	function sieve($max) {		$numbers = range(2, $max); // 1		$k = 1; // 2		do {			$next_number = each($numbers); // 3			$next_number = $next_number[1]; // 4			$h = $k; // 5			$k++; // 6			$len = count($numbers); // 7			$more = $h < $len; // 8			while ($more) { // 9				$j = $numbers[$h]; // 10				$remainder = $j % $next_number; // 11				$not_r = !$remainder; // 12				if ($not_r) { // 13					array_splice($numbers, $h, 1); // 14				}				$h++; // 15				$len = count($numbers); // 16				$more = $h < $len; // 17			}			$n_squared = pow($next_number, 2); // 18			$not_done = $n_squared < $max; // 19		} while ($not_done); // 20		return $numbers; // 21	}

But then it's 21 statements :).Edit: I wonder if it's possible to do the Sieve without nested loops?

Link to comment
Share on other sites

I wonder if it's possible to do the Sieve without nested loops?
I'm sure it is, though I would tend to think it'd be less efficient.BTW, your first expansion of my code killed our server. :) The script timed out but then IIS became non-responsive and we had to restart the server. :)
Link to comment
Share on other sites

I did a quick benchmark of all three versions. Not surprisingly, mine is the slowest one taking about 23 seconds to calculate primes less than 5000. Synook and DD both came in very, very close (11 secs and 10.9 secs respectively).Here's the code I used to benchmark:

$arrPrimeTest = array(13, 15, 7, 9, 42, 57, 120, 113, 101, 309, 547, 231, 670, 789, 843, 991, 1203, 1109, 2067, 4091, 5788, 9891, 10295, 11253);echo "<h3>Test 1:</h3>";rsort($arrPrimeTest); //sort the array in descending order so the largest number is at index 0echo "<table>\n<tr>";foreach ($arrPrimeTest as $val) {	echo "<th>".$val."</th>";}echo "</tr>\n";$starttime = gettimeofday(true);echo "<tr>";$arrPrimes = SieveOfErat(ceil(sqrt($arrPrimeTest[0])));foreach ($arrPrimeTest as $num) {	$blnPrime = true;	$index = 0;	while ($arrPrimes[$index] <= sqrt($num)) {		if ($num%$arrPrimes[$index] == 0) {			$blnPrime = false;			break;		}		$index++;	}	if ($blnPrime) {		echo "<td>Prime</td>";	} else {		echo "<td>Not</td>";	}}echo "</tr>\n";$endtime = gettimeofday(true);echo "<tr><td colspan='".count($arrPrimeTest)."'>Total time: ".($endtime - $starttime)." seconds</td></tr>\n";echo "</table>\n";echo "<h3>Test 2:</h3>";$num = 253;$starttime = gettimeofday(true);$arrPrimes = SieveOfErat($num);$endtime = gettimeofday(true);$str = '';foreach ($arrPrimes as $val) {	if ($str != '') {		$str.=", ";	}	$str.=$val;}echo "Primes for ".$num.":<br />".$str."<br />\n";echo "Total time: ".($endtime - $starttime)." seconds<br />";$num = 1000;echo "<br />Primes for: ".$num."<br />\n";$starttime = gettimeofday(true);$arrPrimes = SieveOfErat($num);$endtime = gettimeofday(true);echo "Total time: ".($endtime - $starttime)." seconds<br />";$num = 2500;echo "<br />Primes for: ".$num."<br />\n";$starttime = gettimeofday(true);$arrPrimes = SieveOfErat($num);$endtime = gettimeofday(true);echo "Total time: ".($endtime - $starttime)." seconds<br />";$num = 5000;echo "<br />Primes for: ".$num."<br />\n";$starttime = gettimeofday(true);$arrPrimes = SieveOfErat($num);$endtime = gettimeofday(true);echo "Total time: ".($endtime - $starttime)." seconds<br />";$arrPrimeTest = array(3, 8, 11, 27, 29, 111, 123, 117, 413, 203, 302, 441, 433, 432, 577, 571, 590, 529, 678, 666, 651, 657, 717, 727, 739, 779, 797, 811, 801, 891, 882, 843, 901, 997, 1120, 1201, 1397, 1446, 1338, 1111, 1290, 1487, 1491, 1429, 1572, 1551, 1529, 1577, 1588, 1599, 1601, 1607, 1629, 1637, 1669, 1788, 1792, 1821, 1849, 1901, 1923, 2041, 2289, 2488, 2572, 2717, 2933, 3477, 3427, 3589, 3922, 4510, 4899, 4177, 3329, 4999, 3718, 2988, 2716, 2719, 4096, 3117, 3819, 456, 4567, 2345, 4321, 3210, 2109, 2229, 1119, 4450, 4891, 3979, 4431);echo "<h3>Test 3:</h3>";rsort($arrPrimeTest); //sort the array in descending order so the largest number is at index 0echo "<table>\n<tr>";foreach ($arrPrimeTest as $val) {	echo "<th>".$val."</th>";}echo "</tr>\n";echo "<tr><td colspan='".count($arrPrimeTest)."'>Using while loop</td></tr>\n";$starttime = gettimeofday(true);echo "<tr>";foreach ($arrPrimeTest as $num) {	$blnPrime = true;	$index = 0;	while ($arrPrimes[$index] <= sqrt($num)) {		if ($num%$arrPrimes[$index] == 0) {			$blnPrime = false;			break;		}		$index++;	}	if ($blnPrime) {		echo "<td>Prime</td>";	} else {		echo "<td>Not</td>";	}}echo "</tr>\n";$endtime = gettimeofday(true);echo "<tr><td colspan='".count($arrPrimeTest)."'>Total time: ".($endtime - $starttime)." seconds</td></tr>\n";echo "<tr><td colspan='".count($arrPrimeTest)."'>Using in_array</td></tr>\n";$starttime = gettimeofday(true);echo "<tr>";foreach ($arrPrimeTest as $num) {	if (in_array($num, $arrPrimes)) {		echo "<td>Prime</td>";	} else {		echo "<td>Not</td>";	}}echo "</tr>\n";$endtime = gettimeofday(true);echo "<tr><td colspan='".count($arrPrimeTest)."'>Total time: ".($endtime - $starttime)." seconds</td></tr>\n";echo "</table>\n";

Link to comment
Share on other sites

I haven't tried it yet, but there might be a way of using array_filter to eliminate one of the loops, because the underlying mechanism of that function is a loop. Don't know yet if it would reduce the number of statements, because the callback function you pass it would probably look like the guts of our inner loops. But it might execute a little faster since the looping mechanism is compiled. Don't know.

Link to comment
Share on other sites

So I did experiment with array_filter (my first time, actually) and it's an interesting function. It takes an array reference, so any changes you make are to the actual array, and you can supply a callback function. What you can't do is pass it any other data. So if you wanted to compare a value to something else, it would have to be embedded in the callback, and if you want to use dynamic data, it has to be global. (Or I'm missing something.) This is not a problem per se, but it created enough extra statements that from the standpoint of our challenge, it provided no benefit.Then I tried array_walk, which accepts a callback AND additional data. At first I thought this was just what I was looking for. But it has a drastic limitation. The callback can receive an array value as a reference, which allows you to change the value in the array itself. But you cannot add or delete any members. Since deleting members it was the sieve is all about, I almost gave up on array_walk.So I tried something. Whenever I came to a member that needed to be removed, I set its value to false. I knew from my experiments with array_filter that when used without a callback, it simply removes any member whose value evaluates to false. So, one more statement, but I was still ahead. But the function still breaks. Even though we are working with a traditional array, not a hash array, when array_filter removes a member, it does not reset the indexes. So you end up with an array like$nums[0] => 2$nums[1] => 3$nums[3] => 5Which made my original algorithm useless. Cleaning up the array with array_values solved the problem just fine, and the code is clean looking, but now I was back to the same number of statements.A nice consequence of the challenge is that I'm exploring functions and techniques in ways I had no reason to explore previously.Maybe if I tweak that algorithm a little more . . .

Link to comment
Share on other sites

You can fix up the keys by calling array_merge() on the array - that basically copies over all the values to a new array with the keys in sequence again.

Link to comment
Share on other sites

Then I tried array_walk, which accepts a callback AND additional data. At first I thought this was just what I was looking for. But it has a drastic limitation. The callback can receive an array value as a reference, which allows you to change the value in the array itself. But you cannot add or delete any members. Since deleting members it was the sieve is all about, I almost gave up on array_walk.So I tried something. Whenever I came to a member that needed to be removed, I set its value to false. I knew from my experiments with array_filter that when used without a callback, it simply removes any member whose value evaluates to false. So, one more statement, but I was still ahead. But the function still breaks. Even though we are working with a traditional array, not a hash array, when array_filter removes a member, it does not reset the indexes. So you end up with an array like$nums[0] => 2$nums[1] => 3$nums[3] => 5Which made my original algorithm useless. Cleaning up the array with array_values solved the problem just fine, and the code is clean looking, but now I was back to the same number of statements.
I too tried this. But it seems to execute far slower than even my original algorithm. :) Did you have that problem too or did I not do something correctly?
A nice consequence of the challenge is that I'm exploring functions and techniques in ways I had no reason to explore previously.Maybe if I tweak that algorithm a little more . . .
:) Yea, it is kinda nice. I've learned a lot of things from this challenge. (Like just how much code a foreach statement actually saves! [or uses, however you want to look at it] :) )
Link to comment
Share on other sites

I didn't bother to benchmark the array_walk technique, since we're counting statements. Obviously I would have if time were critical to the app.
I didn't really run a benchmark. I just tried finding the primes for 15 and it took forever to complete. EDIT: actually I never let it complete. I closed the page before it did.BTW, with the array_filter function could you do something with a class? That way you wouldn't have to make any extra data global to use it in the callback. Although, I guess you would probably still have to make it a property of the class...so I guess that doesn't really help, does it?
Link to comment
Share on other sites

The problem is passing data to the callback function. It receives one value each time it's called, and that's it. With array_walk, you can pass a piece of data, and array_walk passes that data to the callback.

Link to comment
Share on other sites

Just curious, how did you write your version with array_walk?This doesn't seem to work:

function strike_value (&$val, $key, $denom) {   if ($val) {	   if ($val % $denom == 0) {		  $val = false;	   }   }}function getPrimes_walk ($n) {   $i = 0;   $p = 2;   $primes = range($p, $n);   while (($p * $p <= $n) && ($i < count($primes)-1)) {	  array_walk($primes, 'strike_value', $p);	  $i++;	  $p = $primes[$i];   }   $primes = array_filter($primes);   $primes = array_values($primes);      return $primes;}

Everything gets removed. I think I know what the problem is I just don't know how to fix it.

Link to comment
Share on other sites

You pretty much have it, with 2 differences. The conditional looks like this:

if ($value % $denom == 0 && $value != $denom) {

So that the denominator doesn't delete itself. And the sequence of array function calls is like this:

array_walk($primes, 'strike_value', $p);$primes = array_filter($primes);$primes = array_values($primes);$i++;$p = $primes[$i];

So that I'm cleaning up the array immediately after I flag the values to be removed. Otherwise, $i targets the wrong element.It actually took me a second to see how yours was different from mine, since it's pretty darned close. :)

Link to comment
Share on other sites

So that I'm cleaning up the array immediately after I flag the values to be removed. Otherwise, $i targets the wrong element.
Ah, so that's the key. :)I've been playing around with this a little bit and this seems like it could work:
function strike_value (&$val, $key, &$arr) {   if ($val > $arr[0]) {	   if ($val % $arr[0] == 0) {		   array_splice($arr[1], $key, 1);	   }   }}function getPrimes_walk ($n) {   $i = 0;   $p = 2;   $primes = range($p, $n);   $bound = count($primes);   while (($p * $p <= $n) && ($i < $bound)) {	  array_walk($primes, 'strike_value', array($p, &$primes));	  $i++;	  $p = $primes[$i];   }      return $primes;}

Only problem is it doesn't seem to walk through all the values like I would expect it to.

Link to comment
Share on other sites

The challenge of array splice is that every element after the deleted element gets reindexed. So if you're using a counter as an index, elements are no longer where you think they are. That's why my original technique looped through the array backwards. Your original technique avoided the problem by breaking out of the loop every time array_splice was called.In your new experiment, I think you're also breaking the array_walk rules. You are changing the structure of the array, and this will lead to unpredictable results. So says the manual. I suspect it just iterates like 0, 1, 2, 3 and doesn't make the allowances that array_filter does.

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.


×
×
  • Create New...