Sieve Client Thread

[jimmy]

I've found the Dat-file (8025-8050) and will submit it this weekend.

Jimmy

[Joe O]

Version 1.25 running overnight averaged 37443 p/sec for a 6 hour run. This morning it had a sustained average of 37792 p/sec for a 90 minute run.
The console version got 37401 p/sec for a 3 hour run. The highest hour was only 37465 p/sec. There was no other activity during this hour, and only1 -2 minutes of Windows Explorer during the other 2 hours. All of this on a PIII/500 running Win98SE. I will have to recheck the Celeron/450 as well. My previous comments were for one hour runs, where the console version edged out the new release by .5%
Just to make it clear, version 1.25 edged out the console version for this timing test! Not by much, but every bit counts.

Originally posted by Joe O
I didn't check the memory usage, but on a PIII/500 and a Celeron/450 it's slower than the console version.
Any chance for a faster console version?

[MikeH]

More sieve sieve stats changes.

I'm now using the range information from the coordination threads to identify the factors that were submitted when users weren't logged in.

As a result we have 10 new users in the stats. Welcome. Sorry to anyone that's fallen a few places as a result

It also means I claim the number two spot from the pesky [unknown].

On the subject of hole finding, I'm sure you'll all be glad to hear that we are hole free right up to 7375G (Nuri, my fellow hole finder, do you agree?). Well done everyone.

[Nuri]

Hi Mike,

I just checked for holes yesterday, so I can clearly comment on that. I agree with you, but I want to rephrase it to something like, "even if there might be some tiny holes below 7375G, it won't be worth the effort to check for them".

To be more specific,

I'm pretty sure we've patched every hole below 7000G. There are two regions of strange characteristics (too many holes of 1G<p<2G very close to each other, with no factors) between 7000G and 7375G. Even if all of them were actual holes, there shouldn't be more than 30 new factors in total.

I am currently considering if it's worth the try. I'll let you know if I decide to give them a shot.

For 7375G<p, there were some ranges marked as [Complete], but that obviously lacked submitted factors as of yesterday. I am sure these were sieved but not submitted (like jimmy's case), and will be submitted soon.

Anyway, congratulations everybody. Keep up the good work.

[Nuri]

Originally posted by MikeH
I'm now using the range information from the coordination threads to identify the factors that were submitted when users weren't logged in.

But this is only for the factors with userid null, right?

[MikeH]

Nuri said
But this is only for the factors with userid null, right?

Correct.

[Moo_the_cow]

Mike, could you merge the last 2 sieve accounts
(Moo_the_cow and Mooeythecow) into the
Moothecow account? The last 2 sieve accounts were
test accounts that I used before I got my password.

P.S. Why did you id the unknown's? You made me drop
4 places (from 23rd to 27th)

[priwo]

thank you mike that i am in your sieve stats, i did not notice that i should be logged in while submitting factors

sorry for you moo

[MikeH]

Moo said
Mike, could you merge the last 2 sieve accounts

'Tis done. Sorry it hasn't improved your position.

I've also merged

54 peterzal 23.49 ( 0.01) 7 ( 0.00)

into

3 Antiroach (peterzal) 9732.91 ( 4.74) 2253 ( 0.73)

Is there anyone else? Either to merge, or who is not identified in the scores by their forum alias (where SB name is different)?

priwo said
thank you mike that i am in your sieve stats,

My pleasure.

[Moo_the_cow]

I also suggest merging account #54 (Reto) into
account #12 (biwema) since I'm guessing
that Reto Keiser's forum name is biwema
(Reto, please correct me if I'm wrong)
If you're wondering why I'm guessing that,
it's because I saw this in the "Sieve: Distribution
of Factors vd. p value" thread, page 2

quote:
_________________________________________________
Is there a p-1 factorer available which can handle 3Mbit siepinski numbers? I would be quite much fun to find huge factors.
Maybe I should concentrate on smaller p as it is quite much more effective. We will see.

biwema (Reto Keiser)
__________________________________________________

[MikeH]

Thanks Moo. I'd never have noticed that one.

Also done.

Mike.

[Joe O]

Well version 1.25 wins again. On one side of the dual there was a 1.32% improvement over the console version, and on the other side a 1.55% improvement. These were multi-day averages. Yes the memory usage is significantly higher (2596k vs 543k), but it is faster. The paging file is at 43MB, well below the recommended 203MB. There is 192MB of PC100 memory.

[paul.jobling]

Hi Joe,

I am interested in rthe extra speed in 1.25 ovewr the console version. I attach a console version of 1.25 - can you see if that is any faster?

Regards,

Paul.

[Joe O]

Paul, I've got the new one running on both sides of the Celeron. Memory usage is 1708KB/1664KB. I'll let it run for a couple of hours, maybe overnight, and see what happens. Joe.

[Mystwalker]

Just out of curiousity:
What happens when someone submits a factor for a k/n pair that is currently PRP tested? Will this test be aborted the next time the client tries to submit a block?

[Joe O]

Paul,
The new console version is faster than Version 1.25 by 1.53% on one side of the dual and 1.67% faster on the other side.

Averaging both sides we get:

New Console 97309.21869 1.60% improvement over
Version 1.25 95773.41405 1.44% improvement over
Old console 94417.23113


The New Console is 3.0% faster than the Old Console.

Joe.

ps Care to guess which one I will be using?

[paul.jobling]

Originally posted by Joe O
Paul,
The new console version is faster than Version 1.25 by 1.53% on one side of the dual and 1.67% faster on the other side.

The New Console is 3.0% faster than the Old Console.

ps Care to guess which one I will be using?

3%, so nothing amazing. I just noticed that I built it with the old optimizations, so here is another build using the new optimizations. Is this any faster?

Regards,

Paul.

[Mystwalker]

Well, on my P3-m, the new version is even a little bit slower than the old one.
I'm not sure how they compare on my Duron, as there are a bunch of programs running ATM, so there is no detailed speed testing possible...
On a first look, the speed is not that different, maybe a bit faster? I don't know for sure, though.

[Troodon]

On my Tualatin, the console version 1.25 (the first one) seems to be a bit faster than the console v 1.24.

[Joe O]

Paul, the preliminary results (2hr run) don't look good.

93689.61022 -3.7% Slower than the previous version.

This is the slowest one of all. Now I had inadvertantly left task manager running, so I'm going to run another 2 hours to see if that made any difference. If not, ....


The final results (3hr run) are not much better.

93962.34731 -3.44% Slower than the previous version.

[Troodon]

Originally posted by Mystwalker
Just out of curiousity:
What happens when someone submits a factor for a k/n pair that is currently PRP tested? Will this test be aborted the next time the client tries to submit a block?

I would like to see that question answered, too. For example, I'm sieving 10660-11000 and the last factor found is 10694103276187 | 22699*2^3000430+1 (and currently it's the smallest one found in that range).

[mklasson]

I'm curious as to how your sieving is actually done. I'm toying with a little siever myself, but it's quite slowish...

Do you try all p \equiv 1,3,7,9 (mod 10), or do you try to factor p for a while first or something like that?

After that, what do you do next? It seems to me you can't just brute-force your way through the ~660k n values and actually calculate the modulus for each, seeing as how you process somewhere around 100k p values per second. Speaking of which, how's that rate calculated? Do you count the p values actually tested, or is it p_max minus p_min, or something else?

I've also thought about calculating d and r, such that p | k*2^(d+r*t), t \in N, but I can't see how to do that fast enough either.

Could you share some information?

[paul.jobling]

Originally posted by mklasson
I'm curious as to how your sieving is actually done. I'm toying with a little siever myself, but it's quite slowish...

Do you try all p \equiv 1,3,7,9 (mod 10), or do you try to factor p for a while first or something like that?

A windowed Sieve Of Eratosthenes is used, and the p values that are generated are all primes. This can be done quickly, using a bitmap.

After that, what do you do next? It seems to me you can't just brute-force your way through the ~660k n values and actually calculate the modulus for each, seeing as how you process somewhere around 100k p values per second.

Find information on the "Giant steps-baby steps discrete logarithm algorithm". Basically, it finds those n values such that k.2^n+1 = 0 (mod p), but very quickly.

Speaking of which, how's that rate calculated? Do you count the p values actually tested, or is it p_max minus p_min, or something else?

It is indeed p_max - p_min.

I've also thought about calculating d and r, such that p | k*2^(d+r*t), t \in N, but I can't see how to do that fast enough either.

Could you share some information?

That is the algorithm that is used, which is why the time is proportional to the square root of n_max-n_min.

Okay, here are the details:

We want to find n such that p | k.2^n+1

Express n as nmin+a+b*arange, with 0<=a<arange; 0<=b<brange.

Then

p | k.2^(nmin+a+b*arange)+1 ==>

-k.2^(nmin+a+b*arange) = 0 (mod p) ==>

k. -2^(nmin+a) = (1/2)^(b*arange) (mod p)

So what I do is generate (1/2)^(b*arange), for b=0 to brange-1 (the RHS). These values are saved away.

Then for each k, I generate k.-2^(nmin+a) for a=0 to arange-1 (the LHS), and as I calculate each value I see if it was on the RHS. If it was then the a and b values tell me the n value to remove from the sieve.

This is all done using tight assembler for extra performance.

Regards,

Paul.

[Joe O]

Paul,
Any chance for a faster sieving program?

[paul.jobling]

Originally posted by Joe O
Paul,
Any chance for a faster sieving program?

LOL, I would if I could!

Regards,

Paul.

[mklasson]

Paul,

thanks for the info. I figured out the same scheme (more or less) later on, but it's good to hear the current approach is the same thing. Or bad... a new speedup would've been nice.

I suppose it's really pointless to ask, as I'm sure you've tried to optimize the living daylight out of your siever already. But anyway: you've selected optimal values for arange and brange, taking into consideration the different costs for one step of
"k.-2^(nmin+a) for a=0 to arange-1"
(fastest implemented by having 12 initial values and just leftshifting them by 1 and using sub for the mod?)
vs one step of
"(1/2)^(b*arange), for b=0 to brange-1"
and so on?

Again, I don't mean to belittle your effort, I'm just hoping you've forgotten something.

Cheers,
Mikael

[paul.jobling]

Originally posted by mklasson

you've selected optimal values for arange and brange, taking into consideration the different costs for one step of
"k.-2^(nmin+a) for a=0 to arange-1"

vs one step of

"(1/2)^(b*arange), for b=0 to brange-1"

Mikael,

The 'alpha' value is the ratio between arange and brange.

No, I do not double using a leftshift and sub; instead I use a 64 bit a=b*c mod d. That is because for these particular k values, the n values are sparse - if you look you will see that the remaining n values for a particular k are all =3 mod 24 (for example), or something similar. So I perform a multiply by 2^24 rather than performing 24 doublings that will not get rid of any n values. I can multiply by 2^24 or 2^48 or 2^36 faster than I can do 24/48/36 leftshifts and subtractions.

Regards,

Paul.

[mklasson]

Paul,

ok, I'll just shut up now then.

Cheers,
Mikael

[mklasson]

Paul...

say, have you thought about something like this:

we know 2 | p-1. Therefore calculate 2^((p-1)/2) mod p, and see if it's == 1. If it is, then for each k calculate (p-k^-1)^((p-1)/2) mod p and see if it's == 1. If it isn't, then you can safely ignore that k for this p.

You could then optimize arange and brange according to the number of k's left.

Assuming the cost of calculating the t^((p-1)/2) is negligible, and that arange and brange are optimized to minimize remaining_k*arange+brange (probably not a very optimal formulation), the speedup seems to land somewhere around 15%. About 25% of the k values are discarded on average.

It might even be worth trial factoring p-1 a little bit to get a potentially better estimate of order(2,p), and hence increase the chances of eliminating a k. When the order of 2 is known, the speedup hovers somewhere around 30% instead of 15.

Cheers,
Mikael

[paul.jobling]

Mikael,

Another thing that the code does is to perform a fast Kroneker test. For each k there are certain p values that can never divide any of the k.2^n+1 values, and this is based on the Kroneker symbol between the p and the k:

For odd n, p can divide k.2^n+1 iff Kroneker(-2k/p)=1.
For even n, p can divide k.2^n+1 iff Kroneker(-k/p)=1.

When that is combined with the observation that for these values of k, p=3 removes either all of the odd or all of the even values of n, we can perform just one Kroneker test per k per p.

Is this the equivalent of your observation, or have you spotted something more?

Regards,

Paul.

[Joe O]

Originally posted by mklasson
Paul...

say, have you thought about something like this:

we know 2 | p-1. Therefore calculate 2^((p-1)/2) mod p, and see if it's == 1. If it is, then for each k calculate (p-k^-1)^((p-1)/2) mod p and see if it's == 1. If it isn't, then you can safely ignore that k for this p.

<snip>

Cheers,
Mikael

2^((p-1)/2) == 1 mod p <=> 2 is a Quadratic residue of p
(p-k^-1)^((p-1)/2) == 1 mod p <=> (p-k^-1) is a Quadratic residue of p

So you are saying if 2 is a QR of p then (p-k^-1) must be a QR of p or we can ignore that k for this p.

What if 2 is not a QR of p, ie 2^((p-1)/2) == -1 mod p?
Then what? We can't eliminate the k for this p, or can we require that (p-k^-1) also not be a QR of p in order for us to have to consider that k for this p?

[Mystwalker]

:
I don't know if you heard about this new discovery concerning prime numbers (the reference is maybe more in-depth). What do you think about it?


Oh, btw:
What is the biggest n factored so far? I have 19998058 - though not submitted yet. I could look it up myself, but ATM I'm, too lazy to rewrite my programs to look after that.

[Joe O]

As of March 22, 19998825 was the largest N factored. Yours would have been the third largest.

[mklasson]

Paul,

For odd n, p can divide k.2^n+1 iff Kroneker(-2k/p)=1.
For even n, p can divide k.2^n+1 iff Kroneker(-k/p)=1.

The Kronecker symbol is just a Legendre when the denominator is prime, right?

Shouldn't it be
For odd n, p can divide k*2^n+1 iff Kronecker(-2*k^-1 / p)=1.
For even n, p can divide k*2^n+1 iff Kronecker(-k^-1 / p)=1.
? Or wait, I figure our expressions have to be equal due to the product of them being Kronecker(1 / p) = 1.

But also, is the "iff" really true? I thought you meant that:
For n even:
k*2^n+1 = 0 (mod p)
k*2^n = -1 (mod p)
-k*2^n = 1 (mod p)
so the invers of -k has to be a QR.
And for n odd:
-k*2*2^(n-1) = 1 (mod p)
so the invers of -2k must be a QR.
But I don't see why the other direction of your "iff" holds. Why does the QR-hood mean p _can_ divide some k*2^n+1?
Am I misunderstanding you?

Is this the equivalent of your observation, or have you spotted something more?

Don't know yet. We'll see once this is cleared up. Also, see my post to Joe O coming up soon.

Cheers,
Mikael

[mklasson]

Originally posted by Joe O
2^((p-1)/2) == 1 mod p <=> 2 is a Quadratic residue of p
(p-k^-1)^((p-1)/2) == 1 mod p <=> (p-k^-1) is a Quadratic residue of p

So you are saying if 2 is a QR of p then (p-k^-1) must be a QR of p or we can ignore that k for this p.

Yes, but what I'm really thinking is that for -k^-1 to have a chance of being in the cyclic subgroup generated by 2, the order of -k^-1 in Z_p* must be a factor in the order of 2 in Z_p*. I.e. order(-k^-1,p) | order(2,p).

What if 2 is not a QR of p, ie 2^((p-1)/2) == -1 mod p?
Then what? We can't eliminate the k for this p, or can we require that (p-k^-1) also not be a QR of p in order for us to have to consider that k for this p? [/B]

In that case order(2,p) = p-1 and 2 is a generator for the entire Z_p* group. That means -k^-1 _will_ equal some power of 2.

Cheers,
Mikael

[Joe O]

The Legendre symbol (n/m) is a number theoretic function which is defined to be equal to ± 1 depending on whether n is a quadratic residue modulo m where m is an odd prime.

The Jacobi symbol (n/m) extends the Legendre symbol (n/m) to m a positive odd integer.

The Kronecker symbol (n/m) extends the Jacobi symbol (n/m) to m an integer.

(n/m) == n^((m-1)/2) mod m, so 2^((p-1)/2) mod p could have been written (2/p) and (p-k^-1)^((p-1)/2) mod p could have been written ((-k^-1)/p).

So Mikael's statement could have been written:

Therefore calculate (2/p), and see if it's 1. If it is, then for each k calculate ((-k^-1)/p) and see if it's 1. If it isn't, then you can safely ignore that k for this p.

This statement is empirically true for our data, but it doesn't really add anything, and it doesn't tell us what to do when (2/p) is -1, as far as I can tell. Sorry, Mikael.

Paul's statements:

For odd n, p can divide k*2^n+1 iff Kroneker(-2k/p)=1.
For even n, p can divide k*2^n+1 iff Kroneker(-k/p)=1.

are also empirically true for our data and are conclusive. I haven't found the relevant theorems yet, perhaps Paul will supply them.

By the way, (2/m) = (-1)^((m^2-1)/8) =
1 for m == +/-1 (mod 8)
-1 for m == +/-3 (mod 8)
so it could easily be computed by looking at only 3 bits of m expressed as a binary integer. In our case m would be an odd prime, so we would only need to look at 2 bits since the third bit would alway be 1. If the two bits are equal the result is 1, if they are unequal the result is -1.

[mklasson]

Joe,

Originally posted by Joe O
(n/m) == n^((m-1)/2) mod m, so 2^((p-1)/2) mod p could have been written (2/p) and (p-k^-1)^((p-1)/2) mod p could have been written ((-k^-1)/p).

Yes, but that leads the thought away from the core idea. The fact that a^((p-1)/2) = Legendre( a | p ) is just a footnote and not the main issue. This is also true:
Find a factor r of p-1. Calculate 2^((p-1)/r) mod p, and see if it's == 1. If it is, then for each k calculate (-k^-1)^((p-1)/r) mod p and see if it's == 1. If it isn't, then you can safely ignore that k for this p.
Optimally, what you want to know is the order of 2 in Z_p*. Then you can substitute that for (p-1)/r and have an even better chance of wacking a k. Obviously, you won't have to calculate 2^order(2,p) then...

So Mikael's statement could have been written:
Therefore calculate (2/p), and see if it's 1. If it is, then for each k calculate ((-k^-1)/p) and see if it's 1. If it isn't, then you can safely ignore that k for this p.
This statement is empirically true for our data, but it doesn't really add anything, and it doesn't tell us what to do when (2/p) is -1, as far as I can tell. Sorry, Mikael.

It's not only empirically true. Did you miss my latest post? The order of an element in a group divides the order of the group. And like I said, if L( 2 | p ) = -1 then 2 is a generator for Z_p*, which means that all values 1..p-1 can be written as powers of two.

By the way, (2/m) = (-1)^((m^2-1)/8) =
1 for m == +/-1 (mod 8)
-1 for m == +/-3 (mod 8)
so it could easily be computed by looking at only 3 bits of m expressed as a binary integer. In our case m would be an odd prime, so we would only need to look at 2 bits since the third bit would alway be 1. If the two bits are equal the result is 1, if they are unequal the result is -1.

Nifty.

Cheers,
Mikael

[Joe O]

Mikael,

Find a factor r of p-1. Calculate 2^((p-1)/r) mod p, and see if it's == 1. If it is, then for each k calculate (-k^-1)^((p-1)/r) mod p and see if it's == 1. If it isn't, then you can safely ignore that k for this p.

While some people do not consider 1 a factor, r=1 will always work, i.e 2^(p-1) == 1 (mod p). In fact, it may be the only integer that will work when L( 2 | p ) = -1 which is the case that we are considering since you've already taken care of the case L(2|p) = 1 with the test for L((-k^-1)|p)=1.

Regards,
Joe.

[mklasson]

Joe,

Originally posted by Joe O
While some people do not consider 1 a factor, r=1 will always work, i.e 2^(p-1) == 1 (mod p). In fact, it may be the only integer that will work when L( 2 | p ) = -1 which is the case that we are considering since you've already taken care of the case L(2|p) = 1 with the test for L((-k^-1)|p)=1.

I think you're putting way too much focus on the Legendre symbol. Forget about that for a while. 2^(p-1) = 1 is a totally uninteresting case since we know that _every_ a^(p-1) = 1. r=1 not only _may_ be, but absolutely _is_ the only integer that will work when L( 2 | p ) = -1. That's because L( 2 | p ) = -1 tells you there are p-1 distinct powers of two modulo p.

The test I proposed for (-k^-1)^((p-1)/2) is a weaker test than the full (-k^-1)^order(2,p).

Anyway, here's an example:
p = 73
a = 3 (just a random integer we want to test. Imagine it's some -k^-1)

order(2,p) = 9 tells us that there are 9 distinct powers of two modulo p. They are:
2^0 = 1
...
2^6 = 64
2^7 = 55
2^8 = 37
2^9 = 1
and the pattern just repeats after that.

a^order(2,p) = 3^9 = 46 != 1 (mod p)
Tells us that 3 is not in the cyclic subgroup generated by 2, i.e. no power of two is equivalent to 3 mod p.

EDIT: Oh yeah, L( 3 | p ) = 1, so the simple (-k^-1)^((p-1)/2) test does not eliminate 3 in this case.

Here, http://mathworld.wolfram.com/GroupOrder.html, is a good place to start for more info.

Cheers,
Mikael

[Joe O]

Mikael, We're probably boring everybody else. I'll reply to you via PM.