Archive - May 5, 2007

Date

Faster Prime Spiral

Posted May 5th, 2007 by Mgccl
in

Note: There is something even faster.
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

Note: This is slow, try this one.
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);
Honey Pot that kill bots