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 (http://perso.wanadoo.fr/yves.gallot/papers/weight.pdf) 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...