New quickie contest - A Prime Example

[BuzzLY]

Yeah, weedpacket's is pretty damned fast, eh? too bad it currently does not return all valid primes 😉

[piersk]

Well... to be fair, he IS a mathematician rather than a comp sci person

isn't he??

[Mordecai]

A quick fix to Weedpacket's:

if($num==2 || $num==3 || $num==5 || $num==7 || $num==11 || $num==13)

[BuzzLY]

I thought of that too, Mordecai... but I wanted to wait for him to give me his fix. The way his mind works, I didn't want to take anything for granted 🙂

[LordShryku]

Hey Buzz, can you update mine to onion's change?

function check_prime($num) {
   if(($num % 2) == 0) {
      return false;
   }
   $s = sqrt($num);
   for($i=3;$i<=$s;$i+=2) {
      if(($num % $i) == 0) {
         return false;
      }
   }
   return true;
}

[onion2k]

Originally posted by piersk
Well... to be fair, he IS a mathematician rather than a comp sci person

Which is the fundamental flaw in this challenge. Its got fuck all to do with your PHP, instead its entirely down to how good your maths is. Theres no way in a million years I'd be able to write something to compete with the thing Weedpacket has come up with despite being reasonably competent with the language.

When theres a competition thats actually about PHP give me a call.

[Weedpacket]

Originally posted by BuzzLY
nice... but for some reason, 5, 7, 11, and 13 are not showing up as prime numbers.

Funny ... could've sworn.... actually I did just now.

[i]diff[/i]
<    if($num==2 || $num==3)
<        return true;

   if($num==2 || $num==3)
       return true;
   if($num==5 || $num==7 || $num==11 || $num==13)
       return true;

Yeah, it's Mordecai's. Gimme a couple of minutes and I see if I can improve it.

onion2k: the maths I'm using could be a bit more powerful; but the programming overhead looks like it would exceed the savings. Hey, look! Programming issues!

BuzzLY: I would like a bit of clarification re: what you consider a "number" in this context? Do I really need to keep the round() in there or can I join everyone else in leaving it out?

[BuzzLY]

Originally posted by Weedpacket
BuzzLY: I would like a bit of clarification re: what you consider a "number" in this context? Do I really need to keep the round() in there or can I join everyone else in leaving it out?

No, you can assume that I will pass an integer into the equation. However, you must assume that it is a positive integer from 3 on up. So, your first conditional statement can disappear entirely.

[bad76]

ouch! The previous version was faster (I've deleted the post...)(~15000!), but don't works so fine...

This is the latest, at half-speed:

 
function check_prime ($num) {
	static $myprimes=Array(3);

if($num==2 || $num==3) return true;
if(($num&1)==0) return false;

foreach($myprimes as $val)
	if(!($num%$val)) return false;
reset($myprimes);


$sq=sqrt($num);

for($j=($val+2); $j<=$sq; $j+=2)
{
	$x=true;
	foreach($myprimes as $val)
		if(!($j%$val)) { $x=false; break;}
	if($x)
	{
		$myprimes[]=$j;
		if(!($num%$j)) return false;
	}
	reset($myprimes);
}
return true;
}

[Weedpacket]

Oooh, so that's how to do it! I tinkered with the idea of a static array to store already-found primes as well but ran into problems and gave up: it was getting just too clunky for my taste (possibly because I tried storing the numbers themselves; and then I thought of bitfields, but at 32 bits per int, which meant bit fiddling to properly address them; oh, and assigning the arrays dynamically, and it was time to insert a new smiley: :queasy: ).

Using static arrays means the same code might at different speeds on different runs with the same input. Changing $x+=2; in BuzzLY's test code to $x=rand(1,1000000); made mine bark like a dog (I think at best I only got it finding a few hundred primes).

There, onion2k: is that enough like programmer talk for you :evilgrin:?

[laserlight]

hmm... but mine is still slower than yours, which puzzles me.

At first I thought that was because my overhead of 3 iterations to first create an array of potential primes, then applying the sieve of Erasthosthenes, and then filtering the result took too much time in the given 3 seconds.

I increased the timeframe to 10 seconds, but your code was still faster.

I thought that trial division by primes was the fastest trial division possible.
Is that true, or am I missing something (e.g. you are actually using a number sieve, and being a non-mathematician I dont know it from a form of trial division)?

[AstroTeg]

Challenges like these are fun. I was fiddling with this yesterday off and on and spent a few minutes today on it. I think I may revisit this code to benchmark it and several different approaches. I just don't have much time right now to go into it fully.

function check_prime($num)
{
	if($num == 2 || $num == 3)
		return true;
	if($num > 4 && $num & 0x01)
	{	
		$sq = sqrt($num);			
		if(floor($sq) != $sq)
		{
			for($a = 5; $a <= ($num >> 1); $a += 2)		
				if($num % $a == 0)
					return false;
			return true;
		}  // end if(floor($sq) != $sq)
	}  // end if($num > 2)
	return false;		
}  // end function check_prime($num)

[dalecosp]

Originally posted by BuzzLY
You might not think so... but there's a lot more to this than you might think. There is almost ALWAYS room to optimize.

3 seconds is a lifetime for a computer to run code. I am not going to enter the contest, but I can tell you right now that my code is about 6 times faster than yours (when taking into consideration the number of times it must loop). Your function returns around 1000 prime numbers, and mine returns over 6000.

Darn tootin' ... the only function I've written that actually works does just under 4000 in 3 seconds, I think ... gotta either write code or do a visual diff to be sure.

The fast one (that doesn't work) is top secret, of course. 🙂

Hey, when did we get new smileys?

[Merve]

Originally posted by BuzzLY
As it is, my php code only passes in odd numbers, which makes your code work.

If you only pass odd numbers into your code, aren't you forgetting that 2 is a prime number, or is there something I didn't catch? (I'm assuming it's the latter.)

[Moonglobe]

it's that he starts at three.

[BuzzLY]

small glitch... the shell php script, primes.php, got corrupted, and my backup is a bit old. I have to rewrite it. It'll be done shortly, but for now, you can't look at the page. Sorry!

Keep those submissions coming, though!

[dalecosp]

Heh, got corrupted while I was looking at it...

The only one I've got working:

function check_prime($n) {

if ($n==3 || $n==5|| $n==7) return true;
if ($n%3==0) return false;
if ($n%5==0) return false;
if ($n%7==0) return false;
if (!(1&$n)) return false;
$sq=ceil(sqrt($n));
$x=3;
while ($x<$sq) {
	//if (is_int($n/$x)) return false;
	if ($n%$x==0) return false;
	$x=$x+2;
	}
return true;
}

About the same as the other lower scoring ones, I expect. (Must ... reject ... trial ... division ....)

I've got much else to do and don't know that I'll be able to better myself before Friday, though....

[Weedpacket]

Originally posted by laserlight
hmm... but mine is still slower than yours, which puzzles me.

At first I thought that was because my overhead of 3 iterations to first create an array of potential primes, then applying the sieve of Erasthosthenes, and then filtering the result took too much time in the given 3 seconds.

I increased the timeframe to 10 seconds, but your code was still faster.

I do think it's the initialisation overhead (which is why I tried to populate my arrays dynamically) - I haven't tried to find out just where, but I'm sure yours will pull out in front eventually; loop performance seems curiously slow in PHP for some reason. I suspect it's the whole "copy-on-write" thing of the Zend engine. I think everytime the loop index is incremented a new value is created somewhere in memory, the variable is pointed to it, and the old one is gc'd. But I haven't looked at the code at all to verify this.

Um, another legalistic niggle: "6/11/2004, midnight". That's 2004-11-06 00:00:00? Which timezone? Not that I care that much (I doubt I'll do any better than

function check_prime($num) {
    if($num==2 || $num==3)
        return true;
    if($num==5 || $num==7 || $num==11 || $num==13)
        return true;
    if(abs($num%6-3)!=2)
        return false;
    if(!($num%5 && $num%7 && $num%11 && $num%13))
        return false;
    $sqrt = ceil(sqrt($num))+6;
    for($i=18; $i<=$sqrt; $i+=6)
    {
        if(!($num%($i+1) && $num%($i-1)))
            return false;
    }
    return true;
}

before then, but, hey), we're programmers here. We have to be pedantic 😃

ps: I think the above is my final entry.

[BuzzLY]

Actually... as long as your post (and edit 😉) time stamp says "6/11/2004" on my computer, you're in the clear. So, that means Eastern Daylight Time. I'm not going to niggle over a few hours. I may not judge until Monday anyway, so I'm not too concerned about late entries.

[bad76]

Hi,
nice new testing page, BuzzLY, but there is something...

I don't know if there are too many request on your server, but now the number of discovered primes are very different beetween two try. The value even for weedpacket's routine are 6200 down to 4000...

[edit]
... ooops!:queasy: the background is changing, so may be you are working on...
my bad.
[/edit]