Prime

Array_shift() is slower than I thought

Posted May 11th, 2007 by Mgccl
in

If you remember my prime spiral generator, you would remember it cost over 1 hour to generate a 2000*2000 prime spiral.
But after I did the simple diffusion limited aggregation script1, prime spirals' speed seems impossibly long.
Thx to Edd for pointing out array_shift() is über slow, after I slightly changed the code from

while($n<$size){
        if($prime[0]<=$sn){
                $p = array_shift($prime);

to
$i = 0;
while($n<$size){
        if($prime[$i]<=$sn){
                $p = $prime[$i++];

The 2000*2000 prime spiral is generated in 12 seconds!
This script will make everything more clear:
$array= range(1,10000);
$timeparts = explode(' ',microtime());
$starttime = $timeparts[1].substr($timeparts[0],1);
while($i<10000){
	$array[$i];
++$i;
}
$timeparts = explode(' ',microtime());
$endtime = $timeparts[1].substr($timeparts[0],1);
echo 'Native array loop:',bcsub($endtime,$starttime,6),'<br />';
$timeparts = explode(' ',microtime());
$starttime = $timeparts[1].substr($timeparts[0],1);
$i= 0;
while($i<10000){
	array_shift($array);
++$i;
}
$timeparts = explode(' ',microtime());
$endtime = $timeparts[1].substr($timeparts[0],1);
echo 'array_shift():',bcsub($endtime,$starttime,6);

The result:

Native array loop:0.003198
array_shift():2.128530

The native loop is over 650 times faster, don't you think it's too much? What could possibly turn array_shift so inefficient? array_splice($array,0,1) is 7 times slower than array_shift(). So, don't use those functions unless you absolutely have to2.

  1. 1. in theory, much slower than prime spiral
  2. 2. I can't think of any time that you need to use array_shift(). Because it can always be simulated by a native array loop.

If anyone need the 2000*2000 prime spiral, download it here

Posted May 10th, 2007 by Mgccl
in

I used 1 hour 26 minute and 48 seconds to generate this image, and I haven't find anyone online made one this big yet. If anyone found this useful, just download though the attachment.

UPDATE: Also include a 5000*5000 prime spiral created in 78.825353 seconds with my small optimization that make it 650 times faster.

The most optimal PHP prime spiral generator yet

Posted May 7th, 2007 by Mgccl
in

Note: there is a new update make it 650 times faster
A HUGE success from Mgccl the great
500*500 prime spiral can easily use more than 60 seconds with the previous code about spiral generation, but this one, only 12!
As a tradition, I have to introduce to you the "how" did I make it so fast so it produce the picture below:

1. Find all the primes with the PHP implementation of sieve of Eratosthenes
2. For each prime number, find where the a number locates1
3. Draw the point.

one and three are simple, 2 is HELL lot of work.
I first use some of my precious spear time2 on checking how to divide the spiral into pieces that I can operate on. Soon, I got it where all the perfect squares are going to locate, and the number's relationship to it.

So now I successfully divide the board into small half rings.
Then, I further break the half rings into two smaller pieces, one with the same x position, the other with the same y position. To find the difference, which is where the number lay related to the origin (0,0) point (where 1 is). I have to find each piece's point that lay on either x axis or y axis, so I can use simple add and subtraction to get the relative coordinates, which is the location we wanted 

$size = 500;
$prime = esprime($size*$size);
$image = imagecreate($size,$size);
imagecolorallocate($image,255,255,255);
$color = imagecolorallocate($image,0,0,0);
$size2=$size/2;
 
$n = 2;$t = true;$sn=4;
 
$midu=2;$midl=4;$midd=6;$midr=8;
 
while($n<$size){
	if($prime[0]<=$sn){
		$p = array_shift($prime);
		if($t){//even
			if($p <= $sn-$n){
				$x = $n/2;
				$y = $midu - $p;
			}else{
				$x = $midl -$p;
				$y = -$n/2;
			}
		}else{//odd
			if($p <= $sn-$n){
				$x = (-$n/2)+0.5;
				$y = $p - $midd;
			}else{
				$x = $p - $midr;
				$y = ($n/2)-0.5;
			}
		}
		imagesetpixel($image,$x+$size2,$y+$size2,$color);
	}else{
		++$n;
		$sn = $n * $n;
		$t = !$t;
		if($t){
			$midu = $sn-$n*1.5+1;
			$midl = $sn-$n*0.5+1;
 
		}else{
			$midd = $sn-$n*1.5+1.5;
			$midr = $sn-$n*0.5+0.5;
		}
	}
}
header("Content-type: image/png");
imagepng($image);
  1. 1. This is the inverse of the Number Spiral algorithm from Steve Krenzel, where it find the number in a particular location.
  2. 2. Every minute of my day...

Faster Prime Spiral

Posted May 5th, 2007 by Mgccl
in

I promised in my last post about make something faster for create the basic prime spiral graph, and I finally made it.
I modified Christopher David Lane's spiral generator class by adding a method of jump though primeless gaps1.Although I made one myself but it is too confusing to read.

Behold, this generates a prime number spiral in 2.5 seconds on my machine!

$n = 200;
$image = imagecreate($n,$n);
imagecolorallocate($image, 255,255,255);
$color = imagecolorallocate($image, 0,0,0);
$sn=$n*$n;
$prime = esprime($sn);
$y=$x=$n/2;
$color2 = imagecolorallocate($image, 255,0,0);
imagesetpixel($image,$x,$y,$color2);
$remain = 2;
$distance = 1;
$direction = 1;
		for ($count = 2; $count <= $sn; ++$count) {
			if (--$remain == 0) {
				switch ($direction) {
					case 0: $distance++; $direction = 3; break;
					case 2: $distance++;
					default: $direction--; break;
				}
				$remain = $distance;
			}
			switch ($direction) {
				case 3: --$x; break;
				case 1: ++$x; break;
				case 0: --$y; break;
				case 2: ++$y; break;
			}
			if($prime[0] == $count){
				array_splice($prime, 0, 1);
				imagesetpixel($image,$x,$y,$color);
			}
			if(isset($prime[0])){
 
				if($prime[0]-$count+1<$remain){
					switch ($direction) {
						case 3: $x-=$prime[0]-$count-1; break;
						case 1: $x+=$prime[0]-$count-1; break;
						case 0: $y-=$prime[0]-$count-1; break;
						case 2: $y+=$prime[0]-$count-1; break;
					}
					$remain -= $prime[0]-$count-1;
					$count +=$prime[0]-$count-1;
				}elseif($prime[0]-$count+1>=$remain){
					switch ($direction) {
						case 3: $x-=$remain-1; break;
						case 1: $x+=$remain-1; break;
						case 0: $y-=$remain-1; break;
						case 2: $y+=$remain-1; break;
					}
					$count +=$remain-1;
					$remain = 1;
				}
			}
		}
header("Content-type: image/png");
imagepng($image);

  1. 1. the speed increase is so small I don't even think it is worth a mention

Prime Spiral(Ulam's spiral) visualization

Posted May 5th, 2007 by Mgccl
in

Prime Spiral are fun Look at it and tell me what do you think:

I have to say thx to Steve Krenzel's number spiral script, I ported his code from python to PHP, and without it, this could never be done.
Krenzel's algorithm is only good for printing things out in text format and when the number for $n is even, else you get a reversed output. Because I can work on a image, I should get my own algorithm that run from the the origin point and spiral outside, so it does not need to do a LOT of calculation. Currently, a 200*200 Prime Spiral uses 8.5 seconds, it could be greatly decreased if I figure out the spiraling out logic.

You need my function that does Sieve of Eratosthenes for my code to work.

function base($x,$y,$n){
    return $n - 2*min($x>=$y?$y:$x,$n-$x>=$n-$y?$n-$y:$n-$x);
}
 
function delta($x,$y,$n){
    $d = $x>=$y?$y:$x;
    if ($x + $y > $n){
    	$d = $n-($x>=$y?$x:$y);
    }
    if ($y > $x){
    	return -($x + $y - 2*$d);
    }
    return $x + $y - 2*$d;
}
 
$n = 100;
$n*=2;
$image = imagecreate($n,$n);
imagecolorallocate($image,255,255,255);
$color = imagecolorallocate($image,0,0,0);
$primes = esprime($n*$n);
  for($i=0;$i<$n;++$i){
     for($j=1;$j<$n+1;++$j){
        $num = pow(base($i,$j,$n),2) + delta($i,$j,$n)+ 1;
        if (in_array($num, $primes, true)) {
        	imagesetpixel($image, $i, $j, $color);
		}
    }
}
header("Content-type: image/png");
imagepng($image);
Syndicate content
Honey Pot that kill bots