PureBasic Forums - English

Here's some translated code from the Euler forum

michaeled314,
should this: not be this: Paul.

dioxin wrote:I think to start with you need a much more efficient IsPrime() function and a more efficient find next prime function.

There is mention of a pseudo-prime test on the Project Euler forum, but to be honest I haven't been able to get my head around how that works yet.

Kind regards,

Francis.

Francis,
I get the impression that there are tests (Rabin-Miller? and similar) which tell you that a number is very likely to be prime and very quickly.
When searching lots of primes it might be an idea to first do the quick test which will probably give a good answer and then afterwards use the much slower brute force method to verify that answer.
That way the time consuming brute force method is only carried out on numbers which are very likely to be prime instead of all numbers in the range.


I've just had a quick look at such a test ..
http://aspn.activestate.com/ASPN/Cookbo ... /index_txt

and you're right. They take a bit understanding!

But, presumably, you need to use such a test to get anywhere near solving these problems in the time scale suggested.

Paul.

How on earth would you do #2 in ASM

I've managed to get problem 146 solved in about 3.5 minutes (and that's on a Pentium4 @ 1.6GHz, not my quad-core machine).

A simple trick to completing it really fast is to create a function that will check n^2 + 1, n^2 + 3, n^2 + 7, etc.. for primes simultaneously rather than doing them individually with IsPrime().

*** EDIT: I've just refined my routine so that it now completes in just over a minute!

Kind regards,

Francis.

Dreamland Fantasy wrote: A simple trick to completing it really fast is to create a function that will check n^2 + 1, n^2 + 3, n^2 + 7, etc.. for primes simultaneously rather than doing them individually with IsPrime().

Hi Francis,

have it also here on my notebook in about a minute now - except the precalculation time for the primes (but this should be done in about 10 seconds )

Just used my old code (seen in page 8 of the thread, so I also check all terms in the IsPrimeChain() at the beginning) - so the only real change is that I have removed the precalculation of primes (saved it to a file)

Thanks for all tips , so I can remove one more from my list...

Michael

PS problem 144 is maybe the only one which needs (?) to be solved with floating point variables, but on the other hand calculation time is nearly null...

Michael Vogel wrote:Just used my old code (seen in page 8 of the thread, so I also check all terms in the IsPrimeChain() at the beginning) - so the only real change is that I have removed the precalculation of primes (saved it to a file)

Yeah, I've saved the pre-calculated primes upto 150000000 on my computer at home, but it's quite a big file (too big for my memory stick)!

I redone the pre-calculations and saved them on this computer and redoing the problem it completes in 15.6 seconds (P4 @ 1.6GHz)! Pre-calculating to 79000 and doing the rest on the fly takes 64.4 seconds, so it's a big speed boost!

Kind regards,

Francis.

Dreamland Fantasy wrote:Yeah, I've saved the pre-calculated primes upto 150000000 on my computer at home, but it's quite a big file (too big for my memory stick)!

I redone the pre-calculations and saved them on this computer and redoing the problem it completes in 15.6 seconds (P4 @ 1.6GHz)! Pre-calculating to 79000 and doing the rest on the fly takes 64.4 seconds, so it's a big speed boost!

Hey Francis, you are #1! (not only because you started with this problem)

Never will get these results, precalculation takes about two or three minutes here! (Maybe you can PM me your code;), I saved the primes only, which takes about 33MB when using long values...

Again, 16 (and also 64) seconds are great!

Michael

michaeled314 wrote:How on earth would you do #2 in ASM

:roll:

Michael Vogel wrote:

Dreamland Fantasy wrote:Yeah, I've saved the pre-calculated primes upto 150000000 on my computer at home, but it's quite a big file (too big for my memory stick)!

I redone the pre-calculations and saved them on this computer and redoing the problem it completes in 15.6 seconds (P4 @ 1.6GHz)! Pre-calculating to 79000 and doing the rest on the fly takes 64.4 seconds, so it's a big speed boost!

Hey Francis, you are #1! (not only because you started with this problem)

Never will get these results, precalculation takes about two or three minutes here! (Maybe you can PM me your code;), I saved the primes only, which takes about 33MB when using long values...

Again, 16 (and also 64) seconds are great!

Michael

I was looking forward to trying out the code on my machine at home, but unfortunately I left my memory stick at work. Doh! :roll: In theory it should take about 2 seconds give or take on my quad-core system. Quite impressive I think considering my original approach took over 4 days!

I'll PM you my code tomorrow if I get the chance.

My saved list of primes takes up around 33MB too (too big for a 32MB stick!). You've probably just done the same as me and used WriteLong() to save the values to the file.

Kind regards,

Francis.

Are you guys doing some sort of group entry for this or are you all submitting independantly? This looks kind of fun.

I'm wondering if this is a collaborative effort or you are just sharing notes as you go

michaeled314 wrote:

michaeled314 wrote:How on earth would you do #2 in ASM

:roll:

:roll: :roll:

pdwyer wrote:Are you guys doing some sort of group entry for this or are you all submitting independantly? This looks kind of fun.

I'm wondering if this is a collaborative effort or you are just sharing notes as you go

I'm doing this independently, but I do try to help out others if I can as well as asking for help myself if I need a nudge in the right direction.

It's also good for sharing tidbits of information and code if someone has a better way of doing something.

Kind regards,

Francis.

michaeled314 wrote:

michaeled314 wrote:

michaeled314 wrote:How on earth would you do #2 in ASM

:roll:

:roll: :roll:

Try having a look at http://www.csn.ul.ie/~darkstar/assembler/.

Sorry I can't be of much more help than that, but x86 assembly really isn't my forte at present.

Kind regards,

Francis