Prime Number Generator

[abachler]

Originally Posted by laserlight

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.

[laserlight]

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

[abachler]

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.

[maxorator]

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.

[abachler]

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.

[brewbuck]

My submission. Takes 3.8 seconds on my system.

[abachler]

Originally Posted by brewbuck

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.

[brewbuck]

Originally Posted by abachler

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.

[abachler]

process terminated after 15 minutes, no results returned...

the only changes I made to your code are -

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

#ifdef USE_BUILTIN_MAIN
int main()
{
	__int64 output[100000];

	PrimeFunc(output);
	return 0;
}
#endif

[abachler]

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.

#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 % Divisors[Test] == 0) goto prime_start;
            }
        PrimeList[PrimeCount] = Prime;
        PrimeCount++;
        }
    return;
    }

[brewbuck]

Originally Posted by abachler

process terminated after 15 minutes, no results returned...

Stupid signed integer math... Try this:

[abachler]

Originally Posted by brewbuck

Stupid signed integer math... Try this:

ahem, PrimeFunc(__int64*) not PrimeFunc(Bignum*), but I went ahead and added this fix

void PrimeFunc(__int64* data){
    PrimeFunc((Bignum*) data);
    return;
    }

4.625 seconds, thats impressive, would you explain your method in detail?

[brewbuck]

Originally Posted by abachler

ahem, PrimeFunc(__int64*) not PrimeFunc(Bignum*), but I went ahead and added this fix

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

[laserlight]

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

[zacs7]

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