Prime Number Generator

This is a discussion on Prime Number Generator within the Contests Board forums, part of the Community Boards category; OK, the contest is to generate 100 thousand unique Prime numbers from 2^32 to 2^64-1 in the shortest time possible. ...

  1. #1
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189

    Prime Number Generator

    OK, the contest is to generate 100 thousand unique Prime numbers from 2^32 to 2^64-1 in the shortest time possible. There are some limits of course.

    1. You cannot load any values from external files.
    2. Your entire program must be contained in a single cpp file of less than 64K named PrimeFunc.cpp with a function named PrimeFunc(__int64*) which will be called by the test program.
    3. You may use no more than 10 'seed' values none of which may be greater than 2^32-1
    4. All code must compile under visual studio 2008 express as a win32 console program. Default optimzation settings will be used.
    5. All results must be placed into the __int64* array supplied by the test program.
    6. You may not use any file or network access functions.
    7. You may use inline assembly, OpenMP, threads, even the GPU as long as you limit GPU code to HLSL.
    8. There can be no composite numbers returned
    9. You must return exactly 100 thousand primes, no more no less.
    10. Programs that crash are disqualified.
    11. Programs that take more than 5 minutes to complete are disqualified.
    12. Entries should be made public.
    13. This contest is open ended so further optimizations should be submitted as a new entry.
    14. (Optional)The solution should be general enough so that it could in theory be applied to build a comprehensive list of all primes.
    15. You may not include any header files other than <math.h>, some exceptions may be made to this ask first.

    The test system is a Pentium 4HT 3.2 GHz with 2GB of 800MHz dual channel memory. The GPU is an 8600 with 1GB of ram. A non-optimized test program was run and completed within the alloted time.
    Last edited by abachler; 11-26-2008 at 02:36 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    How will you be verifying the correctness of the returned values?

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,623
    >> 3. You may use no more than 10 'seed' values none of which may be greater than 2^32-1

    Does it not make sense to start from the first number in the range you require?

  4. #4
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    the test program will verify the values in the array after the PrimeFunc() returns.. It will test every value both for uniqueness and for primality.

    The testing phase of the program is not counted against the runtime of the function.

    Starting from 2^32+1 is fine, since it is not prime. By seed value I mean specifically prime numbers or precalculated values used to circumvent doign the actual calculations. Some algorithms require seedign with known primes to operate efficiently, so I allow the use of 10. The rule is to prevent someone from just writing a huge array with all the values and returnign it.
    Last edited by abachler; 11-26-2008 at 03:23 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #5
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Do we have to write it in C++?

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by zacs7 View Post
    Do we have to write it in C++?
    as stated, you can also use inline assembly or HLSL. No C# python or java if thats what you mean.

    here is an example of one possible solution.
    Attached Files Attached Files
    Last edited by abachler; 11-26-2008 at 04:35 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #7
    Registered User
    Join Date
    Aug 2008
    Location
    Belgrade, Serbia
    Posts
    163
    I think he wanted to ask can we do it in plain C.
    2. - Can't we use unsigned long long instead of int64? I'm somehow safer with it.
    4. - Why not use mingw? And what's with the optimizations?
    Vanity of vanities, saith the Preacher, vanity of vanities; all is vanity.
    What profit hath a man of all his labour which he taketh under the sun?
    All the rivers run into the sea; yet the sea is not full; unto the place from whence the rivers come, thither they return again.
    For in much wisdom is much grief: and he that increaseth knowledge increaseth sorrow.

  8. #8
    Nor
    Nor is offline
    h ֆhr s Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    RSA Encryption
    Your Going Down baby
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  9. #9
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by hauzer View Post
    I think he wanted to ask can we do it in plain C.
    2. - Can't we use unsigned long long instead of int64? I'm somehow safer with it.
    4. - Why not use mingw? And what's with the optimizations?
    yeah plain C is fine.

    you can recast the function call internally if you want, but the test program is already written and the test procedure will just invovle drag drop compile and run.
    Code:
    void YourFunc(long long*);
     
    void PrimeFunc(__int64* blah){
       YourFunc((long long*) blah);
       return;
       }
     
    void YourFunc(long long* blah){
       return;
       }
    is fine

    and im not using mingw because I use VS. I stated what compiler so that you know what compiler specific extensions you can and cant use.

    The default optimizations on my compiler are compile for speed and it uses the static multithreaded runtimes if thats important, it shouldnt be.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  10. #10
    Nor
    Nor is offline
    h ֆhr s Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    Where do we need to send our entrys?
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  11. #11
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    just post them here, its an open ended contest, so no need to keep secrets
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  12. #12
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Can we use the network card, if you catch my drift? :-)

  13. #13
    Registered User
    Join Date
    Aug 2008
    Location
    Belgrade, Serbia
    Posts
    163
    @abachler: Ok, all good.
    Vanity of vanities, saith the Preacher, vanity of vanities; all is vanity.
    What profit hath a man of all his labour which he taketh under the sun?
    All the rivers run into the sea; yet the sea is not full; unto the place from whence the rivers come, thither they return again.
    For in much wisdom is much grief: and he that increaseth knowledge increaseth sorrow.

  14. #14
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by zacs7 View Post
    Can we use the network card, if you catch my drift? :-)
    Sure as long as you follow rule #1 and #6, by all means use teh PIC on the NIC to crunch numbers

    and good luck accessign it without breakign rule #15 or #2 part b

    oh as far as teh earlier statement that plain C is ok, its OK as long as it will compile as C++ code. So make sure you use explicit recasts. Im not going to edit your code to get it to compile.
    Last edited by abachler; 11-26-2008 at 09:14 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,311
    Quote Originally Posted by abachler
    2. Your entire program must be contained in a single cpp file of less than 64K named PrimeFunc.cpp with a function named PrimeFunc(__int64*) which will be called by the test program.
    5. All results must be placed into the __int64* array supplied by the test program.
    Instead of __int64, I suggest that you go with something like sqlite3_int64.

    Quote Originally Posted by abachler
    15. You may not include any header files other than <math.h>, some exceptions may be made to this ask first.
    In C++ that should be <cmath>. Actually, why not just allow the C and C++ standard libraries?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 6 123456 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  3. Prime Number stops after 29, but why?
    By Daveo in forum C Programming
    Replies: 22
    Last Post: 09-17-2004, 10:55 AM
  4. Replies: 3
    Last Post: 01-14-2003, 09:34 PM
  5. Random number generator
    By Caze in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2002, 07:10 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21