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 abachler The smaller numbers (under 2^32) are generally very easy to prove prime or composite. 64 bit ...

  1. #61
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Quote Originally Posted by abachler View Post
    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.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  2. #62
    -AppearingOnThis..........
    Join Date
    May 2005
    Location
    Netherlands
    Posts
    44
    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.
    Last edited by SirNot; 12-07-2008 at 05:57 AM.

  3. #63
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  4. #64
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Quote Originally Posted by Daved View Post
    >> 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.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  5. #65
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by Daved View Post
    >> 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.
    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.

  6. #66
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #67
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  8. #68
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    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. #69
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by abachler View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #70
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    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)
    Programming Your Mom. http://www.dandongs.com/

  11. #71
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by CrazyNorman View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #72
    Registered User
    Join Date
    Oct 2009
    Posts
    2
    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!

  13. #73
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    Sfel, probably.
    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

  14. #74
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Nothing like bumping a year old thread.
    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.

  15. #75
    Registered User
    Join Date
    Oct 2009
    Posts
    2
    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!

Page 5 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