Thread: Prime Number Generator

  1. #31
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by laserlight View Post
    Right, I misread the rubric. Looks like you still have zero valid entries, heh.
    yeah, I just made the req'd numbers large enough that it was non-trivial to test for primality, because there arent that many small prime numbers and I wanted optimizations that only pay off for large primes to have a fighting chance. I am actually going to update my baseline entry to include some of your code. I want to see if pregenerating the possible divisors improves performance over testing a few extra composite divisors.

  2. #32
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by abachler
    yeah, I just made the req'd numbers large enough that it was non-trivial to test for primality, because there arent that many small prime numbers and I wanted optimizations that only pay off for large primes to have a fighting chance.
    Just to see how brute force will fare I modified my entry such that it only generates all the prime factors for all composites less than the 100000th prime larger than 2^32, and it took just under 30 seconds to run on my computer (which is a little less powerful than yours, but not enough ).
    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

  3. #33
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    That would definately beat the baseline, which takes 143 seconds using all odd factors less than the root. The assumption of course is that checking compsite odd numbers is completely worthless because if the number being tested where divisible by a composite, then it woudl be divisible by a prime smaller than that composite which has already been checked. So the actual check of the composite itself does nothing but waste compute cycles. Especially for larger primes where the majority of composite numbers are proven composite in fewer than 256 calculations (a naive assumption) but primes take over 32768 calculatons, so reducing the workload for verifying that a prime is in fact prime will have a significant impact on total throughput.

  4. #34
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    I made a simple one for under 2^32 which finishes in 132 seconds. Over 2^32 requires some thinking though.

    Edit: Oh wait! When I used square root (dumb of me to forget that) I got 100,000 under 2^32 in 0.7sec and 1,000,000 under 2^32 in 18sec. Still no help when doing over 2^32 though.
    Last edited by maxorator; 12-01-2008 at 09:42 AM.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  5. #35
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Well, generating a list of primes less than the maximum root you expect to encounter should allow for an optimized check of the numbers larger than 2^32 as laserlight and i discussed. I am currently adding LL's code to my own to increase the speed of the base algorithm, which should allow for faster throughput.

  6. #36
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    My submission. Takes 3.8 seconds on my system.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #37
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by brewbuck View Post
    My submission. Takes 3.8 seconds on my system.
    It doesnt compile, rand() apparently isnt defined in cmath, so ill include it and also, typedefing __int64 to bignum doesnt work, as the test program expects the actual function declaration to be PrimeFunc(__int64*), not PrimeFunc(BigNum*); ill fix that as well.

  8. #38
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by abachler View Post
    It doesnt compile, rand() apparently isnt defined in cmath, so ill include it and also, typedefing __int64 to bignum doesnt work, as the test program expects the actual function declaration to be PrimeFunc(__int64*), not PrimeFunc(BigNum*); ill fix that as well.
    Okie dokie.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #39
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    process terminated after 15 minutes, no results returned...

    the only changes I made to your code are -
    Code:
    #include <math.h>
    #include <stdlib.h>
    
    //typedef __int64 Bignum;
    #define Bignum __int64
    I am assuming you are doing somethign that implicitly requires the actual bignum type, so perhaps you could rewrite your code so it will compile using the following main (modified from your intrnal one.

    Code:
    #ifdef USE_BUILTIN_MAIN
    int main()
    {
    	__int64 output[100000];
    
    	PrimeFunc(output);
    	return 0;
    }
    #endif
    Last edited by abachler; 12-01-2008 at 06:43 PM.

  10. #40
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    ok, here is the base code updated to use laserlights routine to generate the divisors, it then specifically uses the divisors to test primality. The original took 146 seconds, this version took 35, 5 times faster, so definately a worthwhile optimization.

    Code:
    #define DWORD unsigned __int32
    #define OFFSET 2
    extern void laserlight(__int64*);
    
    void abachler(__int64* PrimeList){
        __int64 Prime = 4294967297;
        __int64 Root = 1;
        __int64 PrimeCount = 0;
        __int64 Divisors[100000];
     
        laserlight(Divisors);
     
    prime_start:
        while(PrimeCount < 100000){
            Prime += OFFSET;
            while((Prime / Root) > Root) Root++;
            for(DWORD Test = 1;Divisors[Test] <= Root;Test++){ // skips the 2
                if(Prime &#37; Divisors[Test] == 0) goto prime_start;
                }
            PrimeList[PrimeCount] = Prime;
            PrimeCount++;
            }
        return;
        }
    Last edited by abachler; 12-01-2008 at 07:51 PM.

  11. #41
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by abachler View Post
    process terminated after 15 minutes, no results returned...
    Stupid signed integer math... Try this:
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #42
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by brewbuck View Post
    Stupid signed integer math... Try this:
    ahem, PrimeFunc(__int64*) not PrimeFunc(Bignum*), but I went ahead and added this fix

    Code:
    void PrimeFunc(__int64* data){
        PrimeFunc((Bignum*) data);
        return;
        }
    4.625 seconds, thats impressive, would you explain your method in detail?

  13. #43
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by abachler View Post
    ahem, PrimeFunc(__int64*) not PrimeFunc(Bignum*), but I went ahead and added this fix

    Code:
    void PrimeFunc(__int64* data){
        PrimeFunc((Bignum*) data);
        return;
        }
    Bleh. Thanks.

    4.625 seconds, thats impressive, would you explain your method in detail?
    It's fast because I'm cheating
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #44
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by abachler
    4.625 seconds, thats impressive, would you explain your method in detail?
    Impressive? I thought that "a non-optimized test program was run and completed within the alloted time", which sounds even more impressive
    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

  15. #45
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Can we use CUDA (Compute Unified Device Architecture)?

    Otherwise what's the point of saying you have a 8600GT? ... there's a horse sitting in the stable and I want to play with him! Basically my plan is to adapt brewbuck's code and win :-) the only problem is I need to understand how it works first...
    Last edited by zacs7; 12-02-2008 at 01:28 AM.

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