# Prime Number Generator

Show 80 post(s) from this thread on one page
Page 5 of 6 First 123456 Last
• 12-06-2008
IceDane
Quote:

Originally Posted by 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.

Yes, of course, I wasn't trying to say that it would beat the challenge, but that it did at least look somewhat promising. My previous implementation of the sieve of eratosthenes' memory complexity was O(n), where n is the maximum in the range, while this one's is O(n/8) (I am using the O notation correctly, am I not?), and the previous could generate primes under 10 million(Limit due to the heavy memory usage) in 10 or so secs, while the current can do so in .. 3 secs.
• 12-07-2008
SirNot
I made this probably a year ago or so, and to be honest I can't really be bothered converting it's interface to the specifications. however, it may be of interest: it can easily calculate >200000 primes above 2^32 in less than 0.4 seconds. it compiles on gcc fine, using the unsigned long long type; not sure about visual c++.

run it like: segprime2 minimum_value maximum_value output_file
eg. segprime2 4294967296 4300000000 outfile.txt will generate 227027 primes

http://sirnot.110mb.com/c/?f=segprime2.c

it uses a 'work array' to maximize its range/number size while minimizing memory usage.
• 12-08-2008
Daved
>> while this one's is O(n/8) (I am using the O notation correctly, am I not?)

Not exactly. O(n/8) is equivalent to O(n). In big-O notation all constants are ignored. As n increases, an O(n) running time will increase at the same rate as an O(n/8) running time would, which is why they are considered equivalent.
• 12-09-2008
IceDane
Quote:

Originally Posted by Daved
>> while this one's is O(n/8) (I am using the O notation correctly, am I not?)

Not exactly. O(n/8) is equivalent to O(n). In big-O notation all constants are ignored. As n increases, an O(n) running time will increase at the same rate as an O(n/8) running time would, which is why they are considered equivalent.

Ah yes, I see. Thank you.
• 12-09-2008
abachler
Quote:

Originally Posted by Daved
>> while this one's is O(n/8) (I am using the O notation correctly, am I not?)

Not exactly. O(n/8) is equivalent to O(n). In big-O notation all constants are ignored. As n increases, an O(n) running time will increase at the same rate as an O(n/8) running time would, which is why they are considered equivalent.

Thats not entirely true, since when comparing two algorithms, O(n/8) would be faster than O(n). In cases where the running times are being compared (which is often) the constants cannot be ignored. Only when it is specifically comparing the complexity to the size n of an arbitrary input can the constants be ignored.
• 12-09-2008
matsp
Right, O(n) ~= O(n/8), it's more a case O(n) != O(log2 n) or O(n^2) - if n is 10000, and you divide by 8, you get 1250. Not a huge number, not a small number. O(log2 n) for n=10000 is about 13, O(n^2) is 100000000.

And more importantly, if we double n, O(n) also doubles. O(n^2) is 4x larger, O(log2 n) is one larger.

So the point about big-O is the ability to predict from a small run (low n), how a larger n will behave - this is a bit more difficult in modern machines with caches, virtual memory and other aspects, but we can still predict with some accuracy what will happen if we for example double the amount of data - will the time double or increase more/less than double?

--
Mats
• 12-09-2008
Daved
>> Only when it is specifically comparing the complexity to the size n of an arbitrary input can the constants be ignored.

But is that not what big-O notation is intended for? If you want to compare running times (which of course is often a relevant endeavor), you shouldn't be using big-O notation.
• 12-09-2008
abachler
Except you arent always comparing actual runnign times, but computational complexity. So one algorithm may solve the problem in O(n log n) time, while another algorithm may solve it in O(n/2 log n) by discarding half the test cases based on some trivially computable feature. e.g. an algorithm that finds all prime numbers between 3 and n > 3 by testing every number, versus the same algorithm that only tests odd numbers between 3 and n > 3.
• 12-09-2008
brewbuck
Quote:

Originally Posted by abachler
Except you arent always comparing actual runnign times, but computational complexity. So one algorithm may solve the problem in O(n log n) time, while another algorithm may solve it in O(n/2 log n) by discarding half the test cases based on some trivially computable feature. e.g. an algorithm that finds all prime numbers between 3 and n > 3 by testing every number, versus the same algorithm that only tests odd numbers between 3 and n > 3.

Except that by definition O(n/2 log n) == O(n log n). Nobody's saying there's no difference in run time, it's just not right to talk about it using big-O.
• 12-19-2008
CrazyNorman
If I remember, O(f(x)) = g(x) if there exist constants c, d, and e such that c * f(x) + d >= g(x) for all x > e. Thus, O(n / 8) = O(n), because 8 * (n / 8) + 0 >= n, for all x > 0. (c = 8, d = 0, e = 0)
• 12-19-2008
brewbuck
Quote:

Originally Posted by CrazyNorman
If I remember, O(f(x)) = g(x) if there exist constants c, d, and e such that c * f(x) + d >= g(x) for all x > e. Thus, O(n / 8) = O(n), because 8 * (n / 8) + 0 >= n, for all x > 0. (c = 8, d = 0, e = 0)

Another way to put it is that lim [n -> infinity] f(n)/g(n) = k where k is some positive constant.
• 10-21-2009
deluge01
Greetings, folks.
Congrats on the terrific submissions. I can't find who won - or abachler's source test code. Will someone help me out, please?

Thanks!
• 10-22-2009
laserlight
Sfel, probably.
• 10-23-2009
abachler
Nothing like bumping a year old thread.
• 12-01-2009
deluge01
I know, but the code's still good :)
Can anyone hook me up? Trying to do a primality program for school on the GPU and I'm currently not winning...

Thanks!
Show 80 post(s) from this thread on one page
Page 5 of 6 First 123456 Last