Client question next prime etc...

[vjs]

I had a simple question about the client:

Since we are testing for 11 primes currently if we find a prime and start sieving for the remaining 10, will we actually see a 9% increase in speed??? Or are there other factors etc.

The reason why I ask is there was a 1-2% speed loss in seive file 300K-20m vs 3m-20m if I'm not mistaken, wondering if this is simply due to the dat file/size number of entries etc.

Also the sieve client seems to only use 25 MB max memory would there be any benifit to higher resource demands etc.

[Mystwalker]

There will be a significant speed increase, though it will be a bit lower than 9%, as effort seems not to linearly scale with the amount of k's: Riesel has to sieve for 8 times as many k's (and uses even a slightly bigger range), but one only gets a slowdown to 1/5.

Beneath the amount of k's, the n range has an influence on sieving speed. I think it was ~ sqrt(n range), thus quadrupling the sieving range halves sieving speed. Again, it is even a bit less to my experience.

The amount of k/n pairs in the dat file is said to be unimportant when it comes to sieving speed, although some ppl claim a performance increase of 1-2% with newer dat files which have been cleaned from already found factors.

Concerning memory vs. performance considerations, mklasson is the man. But I doubt there is a way to feasibly sacrifice some memory for more performance...

[vjs]

Thanks Mystwalker,

I think this answers all of my questions, I was pretty sure sieve was pretty much processor dependant, but I couldn't really tell if the memory had much of an issue.

Reason being my dual channel board does about 10% more kps than my single channel (both 2500 bartons) but there are alot of other factors as well, I was just curious.


How did you come up with the prime estimates in your other thread??

[wblipp]

*

Originally posted by vjs
How did you come up with the prime estimates in your other thread??

I think this question is meant for me.

For a "random" integer of value "x", the Prime Number Theorem tells us the probability the number is prime is about 1/ln(x). But 1/2 of random numbers are divisible by 2, 1/3 by 3, 1/5 by 5 etc. Our numbers have similar divisiblity properties, but with different values. For example, when k=67607, x is never divisible by 2 or 7, but 3/4 of the values are divisible by 3 or 5. This effect results in a adjustment known as the "proth weight." Yves Gallot has paper online that discusses these things.

From Table 5 of Yves' paper, for k=67607 the probability "x" is prime is 0,07/ln(x). There are some standard tricks that allow me to accumulate all those probabilities over all those exponents to find the probability of exactly "m" primes by a particular exponent.

The ElevenSmooth project was originally started to help estimate the proth weights. Later I learned better ways to calculate the proth weights, but the project lives on.

William

[Mystwalker]

Originally posted by vjs
Reason being my dual channel board does about 10% more kps than my single channel (both 2500 bartons)

Well, memory speed of course makes a different as well (as CPU speed), only size doesn't matter.
Especially for P4s, memory bandwidth is crucial for sieving. With 800 MHz, they are almost as fast as Athlons. With slower memory, they fall behind by a considerable amount...