Prime Number Generator

[laserlight]

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.

[zacs7]

What a cheat :-), oh well... just pick one of those values for the test and give him a big fat zero.

[laserlight]

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.

[abachler]

Originally Posted by zacs7

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.

Originally Posted by laserlight

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.

[Sfel]

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?

[brewbuck]

Originally Posted by laserlight

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)

[abachler]

Originally Posted by brewbuck

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

a = {2 , 7, 61 }

as those are the only values necessary to witness agaisnt composites below 4759123141

[abachler]

I think Sfel did even better ...

[Sfel]

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.

[laserlight]

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...

[Akkernight]

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...

[laserlight]

Originally Posted by Akkernight

Is it hard to make an algorithm for prime numbers

Not really. It depends on the requirements.

Originally Posted by Akkernight

I guess 1991 is a prime number! Or was it 1993...

1991 = 11 * 181, but 1993 is prime.

[abachler]

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.

[IceDane]

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.

[abachler]

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.