I think brewbuck implemented Rabin-Miller, which is probabilistic and hence might return results that fail abachler's contest requirements.Originally Posted by zacs7
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 ...
I think brewbuck implemented Rabin-Miller, which is probabilistic and hence might return results that fail abachler's contest requirements.Originally Posted by zacs7
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
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.Originally Posted by zacs7
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
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.
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.
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?
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)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.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
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 foras those are the only values necessary to witness agaisnt composites below 4759123141Code:a = {2 , 7, 61 }
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.
I think Sfel did even better ...
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.
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.
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...Originally Posted by Sfel
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
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
Not really. It depends on the requirements.Originally Posted by Akkernight
1991 = 11 * 181, but 1993 is prime.Originally Posted by Akkernight
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
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.
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."
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.