Prime Number Generator

This is a discussion on Prime Number Generator within the Contests Board forums, part of the Community Boards category; Originally Posted by zacs7 the only problem is I need to understand how it works first... I think brewbuck implemented ...

  1. #46
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,727
    Quote Originally Posted by zacs7
    the only problem is I need to understand how it works first...
    I think brewbuck implemented Rabin-Miller, which is probabilistic and hence might return results that fail abachler's contest requirements.
    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

  2. #47
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    What a cheat :-), oh well... just pick one of those values for the test and give him a big fat zero.

  3. #48
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,727
    Quote Originally Posted by zacs7
    What a cheat :-), oh well... just pick one of those values for the test and give him a big fat zero.
    Actually, I think that brewbuck can get away with it. The trick is that the contest is not about coming up with the implementation of an algorithm that accurately determines if an integer greater than 2^32 is prime or composite in the shortest possible time. Rather, it is about producing 100000 primes greater than 2^32 in the shortest possible time. As such, as long as there is no unlucky run, brewbuck passes.

    In a way, this is similiar to the requirements of cryptographic algorithms that need large primes (say, produce any 2 primes that meet the size requirements, as fast as possible), hence the choice of the same commonly used algorithm is natural, in retrospect.
    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

  4. #49
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by zacs7 View Post
    Can we use CUDA (Compute Unified Device Architecture)?
    yes, both CUDA and OpenMP are available. Please specify which of cuda.lib or cudart.lib your submission requires. OpenMP is limited to version 2.0 as thats what 2008 supports.

    Quote Originally Posted by laserlight View Post
    I think brewbuck implemented Rabin-Miller, which is probabilistic and hence might return results that fail abachler's contest requirements.
    ah, i see now, so basically he is using a non-deterministic approach. If a number fails the test it is definately NOT prime (spectacular failure), but if it passes you cant be 100% sure that it IS prime (unconvincing success). This is an acceptable optimization since it could be applied as a definitive test to weed out many strong pseudo primes. It could then be made comprehensive by applying the modified Sieve of Eratosthenes in the base code. So we run the computationally inexpensive test first and only if it fails to prove a number composite do we apply the expensive test. Although I think i will perhaps switch to AKS for the verification routine.
    Last edited by abachler; 12-02-2008 at 09:06 AM.
    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. #50
    Registered User
    Join Date
    May 2006
    Posts
    50
    Here's mine. I hope I didn't break any rules; according to the first post I should have only one function, and I have 2 (+main). If it needs any modifications to be accepted let me know.

    Runs in 0.3 secs on my comp.

    According to my tests it's correct. If it doesn't work for you in any way, I can try again right?
    Attached Files Attached Files

  6. #51
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by laserlight View Post
    Actually, I think that brewbuck can get away with it. The trick is that the contest is not about coming up with the implementation of an algorithm that accurately determines if an integer greater than 2^32 is prime or composite in the shortest possible time. Rather, it is about producing 100000 primes greater than 2^32 in the shortest possible time. As such, as long as there is no unlucky run, brewbuck passes.
    I tuned the constant 'k' for performance at the risk of getting bad primes. Then I crossed my fingers and hoped abachler's rand() function didn't suck.

    In a way, this is similiar to the requirements of cryptographic algorithms that need large primes (say, produce any 2 primes that meet the size requirements, as fast as possible), hence the choice of the same commonly used algorithm is natural, in retrospect.
    This was basically my reasoning. If it's good enough for cryptographic security, it should be good enough here (although in crypto they iterate to a much higher k value)
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #52
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by brewbuck View Post
    I tuned the constant 'k' for performance at the risk of getting bad primes. Then I crossed my fingers and hoped abachler's rand() function didn't suck.

    This was basically my reasoning. If it's good enough for cryptographic security, it should be good enough here (although in crypto they iterate to a much higher k value)
    Well, its not so much that it is 'good enough' as it's 'the best they have'. Cryptosystems typically use primes that are at least 2^128 and typically as high as 2^2048 and some international banks use primes greater than 4096 bits. I believe there are commercial(restricted) systems available in the 16K bit range. Obviously these primes can never be deterministically proven prime by checking all possible prime factors, at least not with current computers. Generally even if these numbers arent prime, its good enough that they are not trivially factorable.

    I think you can actually reduce k further by choosing specific values for
    Code:
    a = {2 , 7, 61 }
    as those are the only values necessary to witness agaisnt composites below 4759123141
    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.

  8. #53
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    I think Sfel did even better ...
    Attached Images Attached Images  
    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.

  9. #54
    Registered User
    Join Date
    May 2006
    Posts
    50
    For those who are interested in the method, I used the sieve of eratosthenes in the following way:

    1. Figure out a maximum range (hi) such that the interval [lo = 2^31 + 1, hi] contains at least 100 000 primes.
    2. Generate prime numbers (using the sieve) up to sqrt(hi)
    3. For each of these primes, find its lowest multiple which is >= lo. Starting from that, mark all its multiples which are <= hi as not prime.
    4. All the numbers in the interval [lo, hi] that are not marked as not prime are definitely prime.

    So basically, the trick is figuring out how to generalize the sieve of eratosthenes to work for any interval [a,b].

    The only disadvantage would be the memory used (I think I use about 2 megs for one of the x arrays), so if you were to ask for, say, a million primes, I'd probably have to resort to using bitsets or bitwise operations to lower used memory.

  10. #55
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,727
    Quote Originally Posted by Sfel
    For those who are interested in the method, I used the sieve of eratosthenes in the following way:
    That's interesting. I implemented the exact same algorithm as an alternative to my "primes only" trial division adaptation, but my running time was even worse than trial division (I had to forcibly terminate the process). Maybe my implementation has a bug that caused an infinite loop, hmm...
    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

  11. #56
    Hail to the king, baby. Akkernight's Avatar
    Join Date
    Oct 2008
    Location
    Faroe Islands
    Posts
    717
    Is it hard to make an algorithm for prime numbers o.O? I know this dude in Gmod who made one using Wire... Didn't look comlicated at all :P
    Oh and I guess 1991 is a prime number! Or was it 1993...
    Currently research OpenGL

  12. #57
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,727
    Quote Originally Posted by Akkernight
    Is it hard to make an algorithm for prime numbers
    Not really. It depends on the requirements.

    Quote Originally Posted by Akkernight
    I guess 1991 is a prime number! Or was it 1993...
    1991 = 11 * 181, but 1993 is prime.
    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

  13. #58
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    so was 2003 and the next one will be 2011, but then so is 18446744073709551557

    there is a rather broad line between numerical analysis and numerology.
    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.

  14. #59
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    It was my intention to participate in this challenge, so I whipped up a modified version of the Sieve of Eratosthenes, where one byte represents 8 numbers. However, I have had some trouble making the code work in a specified range, but I haven't taken the time to look at it properly.

    It can primes ranging from 1 to 80 million or so in a matter of seconds so far, I'll just have to see if I can get it to work properly.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  15. #60
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    The smaller numbers (under 2^32) are generally very easy to prove prime or composite. 64 bit numbers are much slower, both because the math takes twice the bandwidth per variable, and because the proofs themselves are more expensive.
    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.

Page 4 of 6 FirstFirst 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