2

2

Can the algorithm we use for generating the prime numbers initially
know that 2 is a prime number, or do we need to discover this fact each time
we run the program?

10 post / 0 nuovi
Ultimo contenuto
Per informazioni complete sulle ottimizzazioni del compilatore, consultare l'Avviso sull'ottimizzazione

Hi,
Do what best you can which helps you solve the problem in the fastest time possible.

Thanks
-Rama

Quoting Rama Kishan Malladi (Intel)
Do what best you can which helps you solve the problem in the fastest time possible.

This is an interesting question that deserves careful consideration by the judges. Some algorithms to generate prime numbers rely on a small set of seed numbers. My current prime generator uses four magic numbers: three primes (including 2) and one composite. I assume this is allowed.

In last year's Threading Challenge there was a problem called "Prime Array". The second place winner (archie314) used a pre-calculated array of the first 48 primes (2 through 223). Would that be okay this year?

If so, how about a table of all 32-bit primes calculated at compile time? The contest rules don't explicitly address the use of pre-calculated tables or external data files. Note that I'm not talking about pre-calculating solutions for all inputs to the problem (start, end, and maxpower). That would be huge and impractical.

Having a complete prime table would save only a modest amount of initialization time which might then be lost due to file I/O and page faults. For example, I just ran a test that took 30 seconds. Only 100 milliseconds were spent on all initialization including the generation of necessary primes. The winner of this problem will not be determined by who can generate primes the fastest.

- Rick

I had a similar table in last years prime array problem. (First 55 primes).
In fact any one that makes the optimisation that all even number (2 being the exception) do not need to be checked are also doing a similar thing. I think your 4 value should be safe.

In the past it has been ok in moderation to have some precomputed data but if your program required a file containing all pre-computed 32 bit primes, I suspect you might not get any points. But if you calculate all the values from scratch during your run time that is been fine in the past.

How long does it take you algorithum to calculate all 32 bit primes? I tried it and it took 6+ minutes. There is normally a timeout of 5 or 10 minutes for each problem run, so make sureyou do not take too long calculating stuff.

I suspect you can limit the table size to just what is needed. Saves some time.
And also the first part of the problem requires you to calculate primes, re-using these result should not be a problem.

if I undersood you correct, even if the code contain data e.g. hardcoded prime numbers, that will be okay.

Thanks
Hitesh

It has been ok in the past.
But there will still be a limit. Hardcoding all 32 bit values into the code might be an issue. It would also make some very BIG source files.

Can we get an official ruling on this, Rama? I've been following Duncan's advice that we should calculate primes from scratch while "on the clock", using hardcoded values only in moderation. We're all going to be upset if someone comes along with a pre-calculated file of all 32-bit primes and wins first place.

If it's within the rules to generate data files at compile time, please let us know. I can go either way. Thanks,

- Rick

Hi,
To keep it uniform and fair for all participants, we would need the participant to compute the primeson the fly with a moderation of using first few primes as pre-computed. I really can't put a limit on how many first few primes can be pre-computed but i would suggest a limt of first 20 primes or so. So, if any entry has all the primes read from a file, that entry would be discarded.

Hope this clarifies.

Thanks
-Rama

Thank you for the clear and prompt answer. 5 stars.

- Rick

Quoting duncanhopkins
How long does it take you algorithum to calculate all 32 bit primes? I tried it and it took 6+ minutes. There is normally a timeout of 5 or 10 minutes for each problem run, so make sureyou do not take too long calculating stuff.

Sorry for the delay in answering your question, Duncan. To calculate all 32 bit primes my program takes 30 seconds on the MTL login node. On a more "realistic" test like VoVanx86's last 100 million integers, it's right around 1 second (only to spend another 23 minutes actually solving that huge problem).

Like I said before, the winner of this problem will not be determined by who can generate primes the fastest. I don't know why I made a big deal about it...

- Rick

Accedere per lasciare un commento.