Calculating Primes

[Thermistor]

From 0 to n, we multiply X by Y and store the results in an array. If X and Y are the range of integers from 0 to n, the result will give prime numbers from 0 to n.

Optimizations:
X and Y may only be odd numbers. The product of an even number and an integer may only be even. Even numbers are not prime.
Y may never be less than X, as X * Y == Y * X.
X may never be greater than sqrt(n) and Y may never be greater than n/2, as results greater than n are not needed.


How could the event (X * Y > n) be predicted?


Pseudo code:

while(X<=sqrt(n))
{
i=n/X;
while(Y<=i)
{
q[X*Y]=1;
Y+=2;
}
X+=2;
Y=X;


if(X%3==0)
{X+=2;}

}

The section in bold increases calculation speed a bit. Why is this? When/which other numbers may be divided to increase performance?

 

[Pulsar]

I'm curious. Is this a question, or a homework problem?

 

[Peter]

Classic homework problem. This is as highly technical a question as "where's my library pass?" Erathostenes' Sieve it is. Highschool math for 13-year-olds, at least here in Germany.

 

[DrPizza]

Originally posted by: Peter
Classic homework problem. This is as highly technical a question as "where's my library pass?" Erathostenes' Sieve it is. Highschool math for 13-year-olds, at least here in Germany.

I wish U.S. math was on a par with some other countries

-Tom
(math/physics teacher)

 

[Peter]

Just google for "prime sieve" for some ... ummm ... prime examples

 

[Thermistor]

>homework problem

No.

The last question was the are area of interest. If too many primes are divided, performace decreases and the results are inaccurate.
I was wanting to know how to optimize this section.

 

[eigen]

Abandon hope all ye who search for primes this way. If you are serious about finding primes, you need to learn about the the Number field sieve and asscociated weapons.

 

[Sahakiel]

Pseudo code:

int seed[5] = [0x444F2079, 0x6F757220, 0x6F776E20, 0x686F6D65, 0x776F726B];
int size = 2;
int* result = new int [size];
int* previous;
char *printout;

while(X<=sqrt(n))
{
i=n/X;
while(Y<=i)
{
q[X*Y]=1;
Y+=2;
previous = result;
result = new int [size+2];
for(i=0;i<size;i+=2)
result[ i ] = previous[ i ];
size+=2;
result[ i ]=X*Y;
}
if(result != previous)
result=&seed[0];
X+=2;
Y=X;
if(X%3==0)
{X+=2;}
}

printout = result;
i=0;
do {
cout<<printout[ i ];
++i;
while(printout[ i ] != 0);

 

[Peter]

Originally posted by: Thermistor
>homework problem

No.

The last question was the are area of interest. If too many primes are divided, performace decreases and the results are inaccurate.
I was wanting to know how to optimize this section.

Then why don't you follow my advice and google around a bit - the Sieve is about the most often used example for teaching programming beginners about optimization. Plenty of reading out there.

 

[Thermistor]

>Pseudo code

No, that isn't what I was doing.

>google around a bit

I had a very specific question.

 

[Thermistor]

x%3 was just an example.
Adding if(X%3==0){X+=2;} ensures that the program neglects to multiply at this value of x, saving processor cycles.
I could turn the if into a while, and include 7, 11, and 13 to increase performace further. I can continue adding x%r, where r is some prime number less than n to increase calculation speed up to a point. Eventually, performance decreases and the result are wrong. How can I calculate how far this can go?

 

[malone1234]

It's hard to tell. What you have to consider is the processor cycles used by the modulus operation itself in your if statements, verses how many times these if statements will be true, causing X to be increased by 2 which consequently skips over the current number. Apparently, testing for (x%3==0) is true in a significant number of cases (ie it skips over enough numbers so that it speeds up the program). Conversely, if you test for a lot of numbers, x%7, x%11, x%13, etc, through each iteration of the loop then the penalty incurred by executing those modulus operations outweighs the benefit of skipping over a few numbers. I don't know of a mathematical way to figure out the best optimization, but I would just do trial and error. Intuition tells me that testing one or two low primes, like 3 and 7, each iteration might be beneficial. More than that is probably overkill and will degrade performance.

 

[Peter]

Ah well, there is SO much more potential for optimization.

For example, your while() expression calculates sqrt(n) in every iteration of the outer loop. Do that once outside the loop, store result in a variable R, then make that while (X<=R).
In the inner loop, you're calculating X*Y every iteration. You can change that to an addition as well, accumulating an index I into the array in every iteration.

Those things are what optimization is about. Leave the algorithm alone, just implement it better.

 

[Thermistor]

>your while() expression calculates sqrt(n) in every iteration of the outer loop

No, that was done for clarity. Pseudocode.

>you're calculating X*Y every iteration. You can change that to an addition

How? Would that be faster than the processor's buillt-in multiply function?

>if you test for a lot of numbers, x%7, x%11, x%13, etc, through each iteration of the loop then the penalty incurred by executing those modulus operations outweighs the benefit of skipping over a few numbers.

For primes up to 40000000, adding 17, 19, and 23 causes numbers such as 515 to be incorporated in the results (as it is a very crude optimization). Including numbers up to 59 decreases performance.
Yet only adding 3, 7, 11, and 13 increases speed by about 50%, which is quite a bit. So calculating this performance curve is critical.

I'll try a few numbers with sqrt(sqrt(n))*2.

 

[Peter]

Adding is always faster than multiplying. Lots faster. Also, directly moving a pointer over the array is even faster than doing (static pointer)+(offset) in every iteration.

Also, your array still contains all numbers. Just do the odd ones,

such that array[ i ] contains the tag for X=(2i+3), and X is represented in array[(X-3)/2]

That saves you the (most expensive) first run where half the array gets tagged. Start the array at 3. Apart from saving an entire run, this makes the algorithm use half as much memory as before, which isn't a bad thing either. Dividing by two is inexpensive, since it can be represented as a bit shift.


That'll be about like this (pseudo-C):

char array[n/2-1];

e=(int)sqrt(n);
endp = array+n/2;

for (x=3; x<=e; x+=2)
{
s=x>>1;
for (p=array+((x-3)>>1); p<endp; p+=s)
{
*p=1;
}
}
and that's it. There may be "+-1" type bugs in the above. Figuring that out is up to the student