Prime finding function

[Cogman]

I thought it might be fun. for my CS class I created a prime finding function (to aid in reducing a fraction) and slowly I have been trying to shave off the extra milliseconds. I cannot use Euclid's algorithm btw. Below is what I have as a prime finding function.

As a note, "primes" is static. num represents the number of primes to find and the extra comments where given more to satisfy the grader.

BTW, one of the problems I ran into is finding some meaningful way to implement some sort of rate control (I big numbers need more primes to reduce then small numbers do) currently I just find the 5 new primes each time the function is called.

So, any tips for a faster function?

void findPrime(int num)
{
int lastPrime;
int i;
bool valid;
int count = 0;
unsigned int* fPrime;
fPrime = new unsigned int[size + num];
for (i = 0; i < size; i++)
fPrime = primes;
delete[] primes;
primes = NULL;
lastPrime = fPrime[size - 1];

while (count < num)
{
valid = true;
// Skip 2 because no prime after 3 is next to another
lastPrime += 2;
i = 1; // start at 3 rather then 2 because of the last statement
while (i < size && valid)
{
// lastPrime isn't prime if it can be divided evenly by a prime
if (!(lastPrime % fPrime))
valid = false;
++i;
}
// If all went well, add the prime to the prime list.
if (valid)
{
fPrime[size] = lastPrime;
++size;
++count;
}
}
primes = fPrime;
fPrime = NULL;
}

(don't use the "attach code" button, it is unreadable. also, the best way to get a spaced copy of the code is to quote me and then copy the stuff in the quotations.)

 

[QuixoticOne]

http://en.wikipedia.org/wiki/Primality_test

http://cr.yp.to/primegen.html

 

[Cogman]

I would rather not take from prime gen, rather I would like to just see what Ideas you guys can come up with for improved code.

That said, the Primality test from wikipedia was something I handn't read yet, very helpful. Just searching up to the square root of the number has drastically improved speed.

 

[FP]

Are you sure this isn't your homework assignment?

 

[Net]

i wouldn't mind playing with it. but it's incomplete. you need to declare size. paste a working code snip, with a main function, and if i have time i'll look at it.

 

[Cogman]

Originally posted by: binister
Are you sure this isn't your homework assignment?

Pretty sure, it is part of an already completed homework assignment (CS165). We are just discussing objects in this class and not profiling or anything like that (I'm just nuts and like tweaking things like that). here is a link to the homework assignments (this comes from number 10. (warning, PDF ahead).

i wouldn't mind playing with it. but it's incomplete. you need to declare size. paste a working code snip, with a main function, and if i have time i'll look at it.

Ahh, woops, forgot that size is a static member of the class. Tell ya what, Ill send you a PM of the full code, but because it is a homework assignment, I am reluctant to post the full program to the public (don't want the CS teacher getting 1000 copies of my code next semester )

It should be noted that the function does work, all that is needed is a dynamically allocated primes array containing 2, 3, 5 and a variable out side of scope containing the size of the array (named size) it initially contains the value of 3.

Anyways, net YGPM

 

[Net]

lol, this is more then i want to do. sorry. i have my homework too.

I didn't really look at your code but this is the general strategy.

reduce the amount of times you reference memory. Look at the conditions in your loops and see if you can remove obvious things that would slow down your program.

example:

while (checkValue()){ ... }
each time your loop iterates its calling a function (placing the return value on the stack, changing stack pointer and frame pointer, etc...)

better:

int cValue = checkValue()
while (cValue){ ... }

and of course the best optimization, improve your algorithm.

we had to do a lot of speed optimizations in one of my classes. it was fun.

 

[Cogman]

luckily I have avoided calling functions as parameters in while loops. When the program is actually running the largest time consumer for large numbers is the prime finder. algorithm improvement is currently the stage I'm at in optimization. Really, as long as we have 2 objects and no giant copied chunks of code (and it does what its supposed to) we will get an A in the class. But if you just go for an A in this class you will never learn how to really program.

 

[degibson]

Suggestions --
1) Depends on the compiler and architecture, but try using conditional assignment instead of an if statement -- ifs (forward pc-relative branches) are hard to predict, and if the architecture supports partial or full predication, it could be a win. You could probably get rid of valid altogether with this approach.
2) If you're on SPARC, then bear in mind there isn't a hardware modulus option. You'd be better off with a test of the flavor ( prime * N == something )
3) Speaking of which, if you insist on the loop-and-check algorithm, you could try multiplication instead of modulo division -- its often a little faster than division because of compiler checks and such.
4) register allocate count, size, i, and maybe valid