Paloş::Code.Blog()

Hey there people! After viewing (and being enticed by) Leonardo’s post (and also Peteris’) I decided to take a shot at this problem… using PHP. That’s right, I wanted to see how fast I can make a PHP script solve this darn thing. Because I (also) wanted to make use of the pregenerated list of primes, I made a preparation script first that downloads a specified amount of 1 million prime numbers chunks and inserts them into an SQLite database for easier (and faster) access from PHP (this script is called google_th_4_prepare.php). I only called this script for just 1 million primes since all numbers I tried fit within that, but you can do more if you want (see the defined constants)!

Then came the main script that did the actual computing (called google_th_4.php).

Here is the result for the numbers I was given:

time php -f google_th_1.php 

Solving for inputs 25, 129, 139, 1087, 1199…
Found prime number: 9256873

real	0m0.490s
user	0m0.452s
sys	0m0.036s

When I first saw the assigned numbers I almost fell off my chair! I thought they were horrible and that the scripts may even crack! I was wrong; to my surprise, this was the shortest execution time of all the numbers I tried :D. And after a while, Google also confirmed that the result was correct!

As for the numbers mentioned at the links above I got:

time php -f google_th_1.php 

Solving for inputs 7, 17, 41, 541…
Found prime number: 7830239

real	0m1.264s
user	0m1.216s
sys	0m0.044s

I should say, in all fairness, that the computer I used is pretty fast (Intel Core 2 Duo) but still, this is PHP scripting and even more so, about 51% of the execution time was spent on database access (I profiled the script with xDebug and kCacheGrind)! Here are the scripts if you want to check them out (you will need curl, sqlite and the sqlite PHP extension for these scripts to work properly).

I did a pretty looking OO version too but I gave up on it because it was slower, and also because OO is not really justified for pure computational stuff.

google_th_4_prepare.phps

google_th_4.phps

Cheers!

Enjoyed this post?, why not subscribe to the RSS feed!