PHP is too powerless for PE?

In this forum members can discuss topics about specific programming languages.
Post Reply
s0ul-child
Posts: 1
Joined: Sun Jan 30, 2011 2:25 pm

PHP is too powerless for PE?

Post by s0ul-child »

I usually solve project euler(PE) problem using C++,
after I have learned some php basics,I tried to solve same PE problem with PHP.
take problem 3 as an example,
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
I can solve this with C++ but with the same code on php, the execution time takes too long until fatal error occur, which means no output.
I also find out there is no member with level higher than 2 who is using PHP as their programming language.

So the question here is, do PHP has the ability to solve and compute all the problem of PE? I doubt it..
genious999
Posts: 53
Joined: Mon Oct 20, 2008 10:48 pm

Re: PHP is too powerless for PE?

Post by genious999 »

There is nothing about PHP which, in and of itself, makes PHP infeasible for Project Euler problems. It is, for the most part, much slower than compiled languages like C and C++, so some algorithms that in C++ would take less than a minute will run in much more than a minute in PHP. I do believe, though, that the Project Euler problems are designed in such a way that there exists an algorithm that will run in less than a minute in almost any modern language on fairly recent hardware. So, I think the problem is your algorithm is just too slow, not that something's wrong with PHP. I would suggest looking in the forum thread for problem 3 for some hints on how to speed up your algorithm.
User avatar
euler
Administrator
Posts: 4138
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: PHP is too powerless for PE?

Post by euler »

This has certainly been one of the on-going discussion points of the team during development. Although my background is in BASIC I have now almost exclusively migrated to PHP since I developed the website.

It is true that there always exists an algorithm which can solve the problems in less than one minute in a language like PHP on an old machine. My own PC is low powered and about seven years old and I can confirm that most problems I've solved takes less than one second. There are some problems though which take longer, but I've never come across a problem yet taking more than 20 seconds on my machine. Sadly the same algorithm using a compiled language on a newer machine could take milliseconds to solve.

This unfair aspect is amplified when you don't discover that neat algorithm in the first place and you develop a less efficient algorithm. Then members using a better language seem to "get away with it" and have no idea their algorithm is not as good as it could be. It might take several minutes using their language, but it would never solve in a sensible time using PHP.

In cases like this be assured that the team always set limits of problems such that the efficient algorithm should solve in the blink of an eye, but there exist at least one or two alternative approaches that will still solve in less than one minute using interpreted languages on older machines. As genious999 says, if it is taking a long time then there really are other approaches that will solve it quicker.

However, I understand your frustration s0ul-child, as on occasion the lightning quick times posted in the forums are less an indication of the efficiency of the algorithm as much as the speed of the machine and programming language. To add insult to injury I too have encountered those "fatal-errors" using PHP which other languages would not throw out. However, I can assure you that each problem has been extensively tested and with a little rethink of your current algorithm (or a complete rethink!) they can be overcome. At the end of the day it becomes more of a challenge to yourself. You have to accept that all things are not equal using a language like PHP, but that adds to the fun and will make you into a more critical and experienced problem solver. 8-)
Image
impudens simia et macrologus profundus fabulae
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: PHP is too powerless for PE?

Post by TripleM »

For reference, it's more than likely the bug with your code is that you are using a 32-bit system where intval(600851475143) == -443946297.
Mr.Wizard
Posts: 26
Joined: Sun Jan 02, 2011 9:20 am

Re: PHP is too powerless for PE?

Post by Mr.Wizard »

euler wrote:It is true that there always exists an algorithm which can solve the problems in less than one minute in a language like PHP on an old machine. My own PC is low powered and about seven years old and I can confirm that most problems I've solved takes less than one second. There are some problems though which take longer, but I've never come across a problem yet taking more than 20 seconds on my machine. Sadly the same algorithm using a compiled language on a newer machine could take milliseconds to solve.
Would you please send, or direct me to, such a solution for problem #211?
ImageImage
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: PHP is too powerless for PE?

Post by stijn263 »

daniel.is.fischer was able to solve that problem for a limit of 64,000,000,000.

Jaap and Daniel explain their fast method on the first and second page of the forum :)
Mr.Wizard
Posts: 26
Joined: Sun Jan 02, 2011 9:20 am

Re: PHP is too powerless for PE?

Post by Mr.Wizard »

Thanks, I'll read the thread again, looking for those names. I probably missed the good solutions do to my general incomprehension of procedural programming.
ImageImage
mikeac
Posts: 5
Joined: Sat Jan 15, 2011 12:16 am

Re: PHP is too powerless for PE?

Post by mikeac »

Just wanted to point out that it's usually possible to increase the timeout limit for PHP scripts, by creating/editing files such as php.ini or php5.ini. For example, here's the php5.ini file I use on one of my (remotely hosted) websites. The parameter max_execution_time is set in seconds, so in this case the limit is 5 minutes. The ini file should override any of these parameters set in parent directories, and apply to scripts in this and all subdirectories, until a new php5.ini is encountered.

Code: Select all

date.timezone = "Europe/London"
upload_max_filesize = 50M
post_max_size = 50M
max_execution_time = 300
max_input_time = 300
memory_limit = 50M
upload_tmp_dir = /home/sites/MYDOMAIN/public_html/
However, another problem with using PHP (especially running on a remote web server) is that you don't generally get any output until the program has terminated. This is obviously a massive disadvantage for monitoring/debugging. Another reason why I generally stick with Java. :)
mikeac
Posts: 5
Joined: Sat Jan 15, 2011 12:16 am

Re: PHP is too powerless for PE?

Post by mikeac »

BTW, I often find the lightning-fast solutions are way beyond the comprehension of my high-school maths, so I tend to stick with "common sense" approaches and just try to make the code as efficient as possible. In other words, obsessive doggedness and ridiculously late nights, in place of mathematical genius. :lol:
Spura
Posts: 8
Joined: Mon May 16, 2011 4:49 pm

Re: PHP is too powerless for PE?

Post by Spura »

I, in a true developer fashion, will try to bruteforce everything since I adhere to an old adage that my time is worth more than computer time.
Problem 12 I coded in 2 minutes. I connected to my company machine over remote desktop connection and I executed it there and let it run overnight. It had to run around 3 hours to give me the result.

Pdf states that it takes 1 ms to solve the problem with the proper algorithm. :lol:
quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: PHP is too powerless for PE?

Post by quilan »

The brute force approach will work for some of the earlier problems; god knows it helped me more than once when I was beginning this site & didn't understand a lot of the more advanced mathematical / algorithmic methods one can use in later problems. You'll find that the numbers for the later problems have been carefully tuned such that any brute force approaches will be absurdly ineffectual. It's actually one of the reasons I like this site so much :D.
ex ~100%'er... until the gf came along.
Image
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

Re: PHP is too powerless for PE?

Post by Svartskägg »

stijn263 wrote:Jaap and Daniel explain their fast method on the first and second page of the forum :)
Jaap says his code takes 53 seconds. That's not fast.
And daniel.is.fischer says his code takes 1.8 seconds, but doesn't show his code.
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
Post Reply