Thread: Prime Number Generator

  1. #46
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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,195
    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 10:06 AM.

  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?

  6. #51
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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,195
    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

  8. #53
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    I think Sfel did even better ...

  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
    28,413
    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...
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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,195
    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.

  14. #59
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    477
    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,195
    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.

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, 10:34 PM
  5. Random number generator
    By Caze in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2002, 08:10 AM