Home

Prime

Primeth prime

Wed, 03/25/2009 - 22:49 | by Mgccl

a_1 = 2
a_k = p_{a_{k-1}}
where p_k is the kth prime number.
I thought of this sequence today...
Numbers I calculated before it take up way to much time...
1, 2, 3, 5, 11, 31, 127, 709, 5381, 52711,
648391, 9737333, 174440041, 3657500101,
88362852307, 2428095424619, 75063692618249
In fact it is A007097.
Nice.

Tags:

Array_shift() is slower than I thought

Fri, 05/11/2007 - 22:59 | by Mgccl

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.
Tags:

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

Thu, 05/10/2007 - 19:12 | by Mgccl

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.

Tags:

The most optimal PHP prime spiral generator yet

Mon, 05/07/2007 - 17:23 | by Mgccl

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;
$x_adj = ~ $size & 1;
$prime = esprime($size*$size+1);
$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-$x_adj,$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...
Tags:

Faster Prime Spiral

Sat, 05/05/2007 - 21:25 | by Mgccl

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
Tags:
Honey Pot that kill bots