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 laserlight Right, I misread the rubric. Looks like you still have zero valid entries, heh. yeah, I ...

  1. #31
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    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.

  2. #32
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    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 ).
    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

  3. #33
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    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.

  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 08: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,189
    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.
    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. #36
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    My submission. Takes 3.8 seconds on my system.
    Attached Files Attached Files
    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,189
    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.
    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.

  8. #38
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    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,189
    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 05:43 PM.
    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.

  10. #40
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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 06:51 PM.
    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.

  11. #41
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by abachler View Post
    process terminated after 15 minutes, no results returned...
    Stupid signed integer math... Try this:
    Attached Files Attached Files
    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,189
    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?
    Attached Images Attached Images  
    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.

  13. #43
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    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
    21,310
    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
    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

  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 12:28 AM.

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