Prime Spiral(Ulam's spiral) visualization

Sat, 05/05/2007 - 12:54 | by Mgccl

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);

Tags:

Comments

by Steve (not verified) | Sat, 05/05/2007 - 16:42

Interesting

Cool stuff, I like it :) I find it is weird that it takes 8.5 seconds though. To generate a 200x200 number spiral, using the original python code for the number spiral, takes roughly 200ms on my computer, and generating all the primes from 0 to 200^2 takes roughly 12ms, so one would think that the entire spiral generation could occur in under 1/4th of a second. Obviously there is overhead in the image generation, but 8.25 seconds seems a bit much. I haven't tried this in php, but I can't imagine the language choice being that large of a factor in the speed difference. It's just weird that the time is so high, any thoughts on why?

by Mgccl | Sat, 05/05/2007 - 18:12

In my script, the pointer is

In my script, the pointer is in the beginning of the map and run to each point, calculate the number for that point, and compare with the prime list, then go to next point.
But since you are using the same algorithm, I can only conclude PHP is very slow since it is a script language.
I'm working on a algorithm so the pointer starts from the center and spiral out, also jump over numbers when it can, I might finish it tomorrow. :)

Post new comment

If you liked this post, buy me a beer... I mean cookie.

Mgccl's blogI'm the standard deviAsian.

tags in Topics

Navigation

Most Popular

Misc