Sieve Client Thread

[paul.jobling]

Just to be on the safe side, could somebody check that the new 1.26 SoBSieve removes the same values in a known range as 1.25 did? I am 99% sure that it will, but it would be nice to have confirmation.

[Mystwalker]

It found the one (and only) factor I still have saved locally...
Speed increase was ~15% respectively ~25% - once again, you've bet yourself! :cheers:

One bug report:
The help page still states version 1.24 :D


btw: The optimal (well, at least better) alpha setting on my machines are:

900 MHz Duron: 1.5
1 GHz P3-m: 2.0

If someone finds better values, just post them or send me a pm...

[Troodon]

I got a ~30000 p/s increase! BUT there is a problem. Currently I'm sieving the range 10660-11000. The two first factors found by SoBSieve 1.25 are:
10660848993103 | 19249*2^5172926+1
10661083508609 | 55459*2^15208654+1

The first one was found by 1.26, but the second one was NOT FOUND (tried with both, console and GUI, versions).

This is the SoBStatus.dat file I used for the second test:
pmax=11000000000000
pmin=10661082500000

[Joe O]

Originally posted by ceselb
If anybody need a test range here's one:
25 - 25.34G. Done by SoBSieve 1.06, so it should be accurate.

Do you recall what sob.dat file you used for this test range?

[mklasson]

Originally posted by Troodon
[B]I got a ~30000 p/s increase! BUT there is a problem. Currently I'm sieving the range 10660-11000. The two first factors found by SoBSieve 1.25 are:
10660848993103 | 19249*2^5172926+1
10661083508609 | 55459*2^15208654+1

The first one was found by 1.26, but the second one was NOT FOUND (tried with both, console and GUI, versions).
Fortunately the math checks out ok, so it seems to be some code bug.

Regards,
Mikael

[Xrillo]

Good work Paul, and especially good math Mikael!... :thumbs:

I hope the bug isn't fatal..

v1.26 runs at ~110kp/s on my machine now, I'd say about 30% faster than the previous version.

[paul.jobling]

Well, I see exactly the same problem as Troodon - thanks for testing it. I'll remove the download and ask you all not to use version 1.26 until I have fixed it.

[Joe O]

Subscript? There are more than 65536 n's for k=55459. I tested it on
pmax=8791000000000
pmin=8790622787860
8790622787861 | 55459*2^14523346+1 and it worked, so it's not the k value.

[mklasson]

Originally posted by Joe O
Subscript? There are more than 65536 n's for k=55459. I tested it on and it worked, so it's not the k value.
Say, Joe, what's going on here? That's the second post I've seen from you that quotes something I've never seen before. In your previous post you quoted ceselb. I'd never seen his post either.

Am I missing some posts for some strange reason, or are you quoting from other threads or something?

Regards,
Mikael

[Joe O]

Mikael,
Ceselb's quote was from another thread, one of the original sieving threads. Since he posted all the results for that range, it would have been a good test if we knew which sob.dat file he originally used. It wouldn't do to use a newer sob.dat file and get fewer factors since they had been removed. Debugging is hard enough without looking for a problem that isn't there.

The second quote was just a way of formatting the data, I was quoting myself.

[jjjjL]

10661083508609 | 55459*2^15208654+1 is the only known factor for that number (according to the database) so Troodon's observation is not simply caused by the use of an updated sob.dat file... there really must be an error in the computations.

hope it's something minor. thanks for all the hard work paul. :)

-Louie

[paul.jobling]

Well, I had a look at the code and found a small bug- a 64 bit a*b mod p was returning p+1 rather than 1. On investigation, this is a very rare occurrence, so we were lucky to see it.

I have fixed the code so that this is sorted out, and the corrected version is attached. Again, I don't have any set of test cases to try this out with, so if somebody could try this out it would be good.

It is attached.

Regards,

Paul.

[Nuri]

I'll test it on some of my completed ranges (both on normal and DC sieves) for a couple of hours and give some feedback.

[priwo]

the new version of 1.26 has successfully passed the Trodoon-test

pmax=10662000000000
pmin=10660839000000
10660848993103 | 19249*2^5172926+1
10661083508609 | 55459*2^15208654+1

speed increase to version 1.25 is 22% on my Duron 1500+

[Troodon]

After some testing, SoBSieve 1.27 seems to work correctly (same results as with 1.25). On my computer (it's a Tualatin), SoBSieve 1.27 is just a bit faster than 1.25 and much slower than 1.26. I'll try to do some apha value testing.

Thanks Paul!

[Mystwalker]

I switched back to the old version right after Trodoon's posting - hope I haven't missed a factor now. :)

I think we should use a reference range as test bed - like caselb did. Ideally, it would be a low range, as the factor density is higher there, so there's a much greater chance to quickly miss a factor. ;)

Paul:
I'm not familiar with the sieving algorithm (I surrendered after reading your discussion for a minute or two :crazy: ). Are there different factors (pun not intended) that come into play when determining whether or not the current p is a factor? I seems so, as the p+1 problem only affects very few factors, as you've said.
Would it be possible to create a variant of the sieving program that additionally saves the way the factor was found. That way, one could search for a small test range which has all (or at least much) of the "different factor types" in it...


:|ot|: :

Duron 1500+
Durons also have quantispeed measuring? I thought only Athlons have it...

[Troodon]

Celeron Tualatin @ 142x10, Windows 2000, 1.27:

Alpha | ~p/s
------------------
2.000 | 148500
2.500 | 148500
3.000 | 147000

For the console version:
1.27 is ~15% slower than 1.26 on my computer. 1.27 is ~5% faster than 1.25. Anyone else is getting these performances?
Haven't done "detailed" comparision of the GUI version because is slower (and always was slower) than the console version.

Edit: added details.

[priwo]

tested range
13007417126519 | 10223*2^12492989+1
13008326296387 | 21181*2^13984292+1
13009218296443 | 5359*2^9325182+1

same result with 1.25 and 1.27
1.27 is 22% faster than 1.25
1.27 is 12 % slower than 1.26

148.500 with Duron 1500+(real clock is 1300) alpha=2,500

[Nuri]

And these are my test results:

First, there seems to be no problem with finding factors.

The machine used for testing is P4-1700, and system Win 2000.

Versions 1.25 and 1.26 were not faster than 1.24 on my machine, so I tested 1.27 vs. 1.24.

All tests are made in default alpha values.

Tested three different ranges:

1- A range of 0.01G at around 780G.
SoBSieve 1.24: 53.5k p/sec
SoBSieveConsole 1.24: 53.8k p/sec
SoBSieve 1.27: 61.0k p/sec
SoBSieveConsole 1.27: 62.5k p/sec 16% faster

2- A range of 0.01G at around 12350G.
SoBSieve 1.24: 55.6k p/sec
SoBSieveConsole 1.24: 58.8k p/sec
SoBSieve 1.27: 66.2k p/sec
SoBSieveConsole 1.27: 67.1k p/sec 14% faster

3- (for DC Sieve) A range of 0.11G at around 1500G
SoBSieve 1.24: 133.7k p/sec
SoBSieveConsole 1.24: 134.5k p/sec still faster than 1.27, as well as 1.25 and 1.26
SoBSieve 1.27: 111.8k p/sec
SoBSieveConsole 1.27: 131.3k p/sec

It seems to me like, relative performances change wrt. the hardware and system used as well as the p and "n" ranges for the sieve (normal vs. DC etc.).

Thanks again Paul. Your contributions to the sieving effort are very valuable for us.

Regards,

Nuri

[priwo]

results from a Celeron 1300@1560

range:
17907000000000
17909503000000

same factors found by 1.25 and 1.27

1.27 is 13% faster than 1.25 (all my results are with the GUI version)

[Slatz]

Just another data point, I got an 11 % increase from 1.27 over 1.24 on a PIII 1 ghz machine

Slatz

[Joe O]

Version 1.25 GUI 80633 p/sec
Version 1.27 GUI 85333 p/sec 5.83 % increase on a PIII/500 under Win98SE.

[paul.jobling]

Hi all,

I have got a version 1.28 in development that is faster that 1.27. I have managed this by consolidating the new functions that were written for the 1.27 tests together, and by making them all assembler (instead of C code that called assembler code to do the work).

To make sure that things are working, if any7body has got a body of test data that they can use (particularly for large values of p) that they can give to me or they can use to test themselves, please send me a pm.

Regards,

Paul.

[Joe O]

Your PM mailbox is full. I've tried to send you a test range, and volunteer to test the new versions. Even though there is a new version coming, you might find the following results interesting:



Version 1.27 Console 86882
Version 1.27 Gui 88903
Version 1.25 Console 92827


This is on a Celeron/450 running Windows NT. These are ~ 12 hr averages.

So the winner and still champion is Version 1.25 console dated 3/19/2003. Note not the one dated 3/20/2003, but the prior one dated 3/19/2003 with the "old" optimizations!

[Nuri]

Hi Joe,

Are these results based on DC sieve, or normal sieve?

1.27 performs worse on my machine at DC sieve, but better at normal sieve (see above).

And another benchmark on 1.24 vs 1.27:
I've changed to 1.27 on my three machines at work, all three working on 19T-20T range. One has got 10% speed increase, but no significant speed change (~1% increase) in other two.

It's interesting to see different versions perform better on different occasions.

[Joe O]

Nuri,
These are all on DC(Double Checking) Sieve (101 < n < 3M). In the past, I've obtained consistent results for both sieve ranges on my machines. I'll test the 3M < n < 20m range, when V 1.28 gets here, if not before. It depends on RL.

Joe.

[Troodon]

Originally posted by Joe O
So the winner and still champion is Version 1.25 console dated 3/19/2003. Note not the one dated 3/20/2003, but the prior one dated 3/19/2003 with the "old" optimizations!

What are the differences between them? I was using the 19 March version and didn't knew about the 20 March version.

[Joe O]

Originally posted by paul.jobling
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.

[Troodon]

Thanks Joe! Re-reading the thread I realised that I knew about it, but I forgot there were two 1.25 versions :D .

[paul.jobling]

Hi all,

Attached is a 1.28 client. This is about 10% faster than the 1.27 release (on this PC).

This speed-up is due to moving more code to pure assembler, and also by performing a fast Kronecker test before seeing if 'a' is a t-th power (see previous discussion with MKlassen).

If anybody has got code for performing a similar fast test to the Kronecker test for 4th powers I would be interested.

Thanks to the beta testers.

I think my PM inbox is broken - it is empty but people say they cannot send me messages as it is full...

Regards,

Paul.

[ceselb]

Originally posted by paul.jobling
I think my PM inbox is broken - it is empty but people say they cannot send me messages as it is full...


Maybe you have a lot of sent items. Try removing some of those.

PIV 1.5 goes from ~55kp/s (1.27) to ~60kp/s. Very nice :D .

[alexr]

V1.28 GUI

Max of 75Kp/Sec on an very idle p3-600 (67kp/Sec when i'm using it normally)

[Mystwalker]

Version 1.28 is almost at the pace of the (faulty) 1.26 for me.
Still some slight cosmetic error: The help page still states Jan 20th.

If half a year ago I had told someone I achieve >100K p /sec with a CPU <1 GHz for all 12 k's, I'd be put into a nuthouse. :crazy:

[Slatz]

PIII 1 ghz from 104 to 116 with v 1.28...very nice indeed

Slatz

[Troodon]

I think is better to use Pentium 4 for PRP testing and Pentium III for sieving.
When sieving, my Tualatin@1420 MHz is almost 3X times faster than ceselb's Pentium 4 1500, and I'm sure in PRP testing the Pentium 4 is much faster than the Pentium III.

[Nuri]

Originally posted by Troodon
I think is better to use Pentium 4 for PRP testing and Pentium III for sieving.
When sieving, my Tualatin@1420 MHz is almost 3X times faster than ceselb's Pentium 4 1500, and I'm sure in PRP testing the Pentium 4 is much faster than the Pentium III.

That's true in the sense that P4 machines should be switched from sieving to prp testing earlier than others. But, at even 20T, P4 still performs much better at sieving wrt. prp testing.

I think the decision on each machine should be based on it's unique performance at sieve vs. prp, not wrt. other machines.

Just a quick stat.

My P4-1700 tests a n=~3m test in 2 days. (0.5 test per day)

If finds 7 factors per day with sieving at 19,000G.

So, it removes roughly 14 times more candidates at sieving wrt. prp testing. (this figure was roughly 11 times a week ago, just before SoBSieve version 1.27 and 1.28)

It seems to me like, P4 boxes will still perform better at sieving wrt. prp testing even at 100T (yes, may be not 14 times anymore, but my guess is it will be at least 3-4 times).

I'd be happy to hear any other P4 user if you have different benchmark ratios.

PS: But, this does not change the fact that it's still psychologically depressing to run my P4-1700 at home at a sieve speed ~40% slower than my PIII-1000 at work. :(

[Joe O]

Originally posted by Joe O
Version 1.25 GUI 80633 p/sec
Version 1.27 GUI 85333 p/sec 5.83 % increase on a PIII/500 under Win98SE.
Version 1.28 GUI 90999 p/sec 6.64 % increase on a PIII/500 under Win98SE - Low P range on the Double Check Sieve Project

[jjjjL]

i recommend that everyone with a pentium4 run the SB client as opposed to sieving.

even though on a number vs number ratio, sieving appears better, it is far more beneficial to the project to find a new prime and eliminate all 50,000 possible remaining values for a given k.

pentium4's are incredibly efficient at doing prp tests. leave them on SB. in fact, i'd leave any 1GHz+ system on SB if at all possible. sieving is great, but in the end, SB has to find the primes.

-Louie

[Nuri]

Thanks for the comment Louie. You have a good point there, which made me change my mind.

I'll switch my P4 to prp testing as soon as it finishes it's pending sieve ranges at DC sieve.

[Joe O]

Version 1<n<3M 3M<n<20M
V125 Console 100000 40624
V127 Console 91083 45944
V127 Gui 93080 48744
V128 Console 107091 49985
V128 Gui 116803 54713



Windows NT on Celeron/450
P around 12800000000000

Looks like we have a new champion!

[Mystwalker]

What is the highest sieving speed someone achieves?

I present a Duron 1.3 GHz weighting in at 151Kp/sec. using SoBSieve 1.28. :thumbs:
Anyone beats me? :p

[priwo]

as you requested
200kp/sec on a P3-Celeron 1500

[wblipp]

Originally posted by jjjjL
i recommend that everyone with a pentium4 run the SB client as opposed to sieving. ... it is far more beneficial to the project to find a new prime and eliminate all 50,000 possible remaining values for a given k.

-Louie

Originally posted by Nuri
[B]
Just a quick stat. ... So, it removes roughly 14 times more candidates at sieving wrt. prp testing.

Here's a quick calculation that suggests it might still be premature. Using what I think are the best estimates avaiilable, the expected number of primes from n=3 million to n=4 million is 0.82. According to the latest Sieve Statistics, there are 36,320 candidates left in that range, so the probability of any single test finding a prime is about 1 in 44,000. Also based on the Sieving Report, there are about 616,000 candidates left above n=3 million - finding a prime would remove one twelfth of these, about 51,000. One chance in 44,000 of taking out 51,000 candidates is only 1.1 on average. So one PrP test will on average, remove 2.1 candidates. If the same effort Sieving removes 14 candidates, it's still more efficient to sieve.

If I've misunderstood these numbers, please jump in with corrections.

I'll admit, though, that I'm not positive this is the right framework for answering the question. There's a pool of diverse resources to be allocated over time, not just at this instant. Some of those resources will be better suited for sieving always - should P4's be switched earlier to preserve sieving work for the slower machines?

[Nuri]

Originally posted by wblipp
If I've misunderstood these numbers, please jump in with corrections.

There's a pool of diverse resources to be allocated over time, not just at this instant. Some of those resources will be better suited for sieving always - should P4's be switched earlier to preserve sieving work for the slower machines?

Hi wblipp,

First, a small correction:

The server is currently distributing ranges at 3,430,000. So, there are roughly 36230*(1-0,43) = 20650 tests below n=4 million that was not yet distributed for prp testing.

Add the number of currently pending tests (2645), and substract the number of pending tests below n=3 million (44) to that number, so, there are roughly 23250 candidates for 3m<n<4m that we don't know the results yet.

Sieving report does not take into consideration the number of tests that have been already prp tested. The Remaining tests n > 3000000 (http://www.seventeenorbust.com/stats/) stat at the SoB web site gives a better idea of the number of remaining candidates below n=20m that are not yet distributed by the server. It's updated every 30 minutes, and includes both the data for prp tests and sieve submissions.

Regarding the issue of using my P4 for prp testing, I agree with you that it might still be considered for sieving. One reason I changed my mind is that I want to have a chance (even if it's very little, that's still better than none) in finding a prime too. :D My other three PIII's at work are already doing roughly 85% of my sieving work, and they will continue to do so for at least for the following couple of months, provided that I'll keep my job.

And, a last note, yes P4's should be switched to prp testing earlier than other machines. Sieve speed at my PIII-1000's are roughly 60% faster than my P4-1700 (126k/sec vs. 67 k/sec), whereas P4 performs much better at prp speed.

[Nuri]

Originally posted by Joe O


Version 1<n<3M 3M<n<20M
V125 Console 100000 40624
V127 Console 91083 45944
V127 Gui 93080 48744
V128 Console 107091 49985
V128 Gui 116803 54713

Looks like we have a new champion!

Joe, thanks for the benchmarks. As far as I see, they are in line with my figures.

One pleasant surprise that came with the new algorithm (apart from the speed increase) is that, the change in speed of the client is not proportional to the square root of the change in the size of range anymore (up to version 1.25, it was something like => DC sieve speed = Sieve Speed * (20/3^0.5) Alternatively, we could put 2.7 instead of 3 for the ratio after DC sieve SoB.dat changeover).

The proportion is less now after 1.27. That means, the extra benefit that might be gained from changeovers is less than it might with the earlier algorithms.

[smh]

And, a last note, yes P4's should be switched to prp testing earlier than other machines. Sieve speed at my PIII-1000's are roughly 60% faster than my P4-1700 (126k/sec vs. 67 k/sec), whereas P4 performs much better at prp speed.

So i'm not the only one who noticed that P4's are unexpectedly slow with SOBSieve.

Paul, can you explain why this is so? one would expect that a P4-1700 is at least faster then a P3-1000

[mklasson]

Paul,

a small note on biquadratic residues.

If p = 3 (mod 4) then b is a biquadratic residue iff b is a QR.

Proof <=:
Assume primitive root g.
b is QR gives b = g^(2m) for some m.

Case 1, m even:
c = g^(m/2)
c^4 = b

Case 2, m odd:
g^(2m) = g^(2m+phi(p)) = g^(2m+4k+2)
4 | 2m+4k+2
c = g^((2m+phi(p))/4)
c^4 = b

Regards,
Mikael

[mklasson]

Originally posted by smh
So i'm not the only one who noticed that P4's are unexpectedly slow with SOBSieve.

Paul, can you explain why this is so? one would expect that a P4-1700 is at least faster then a P3-1000
afaik the P4's [regular, not sse2] fpu is horribly slow. I'm guessing Paul is using it to do modular multiplication, which is where most of the work goes. Of course, that's just a guess and I'd be most pleased to get confirmation on that... I'm having trouble writing a really fast mod_mul myself.

Regards,
Mikael

[wblipp]

Originally posted by Nuri

First, a small correction:


Thanks, Nuri

Changing the open range requires also changing the expected number of primes, so I don't think that changes the results. My error in the number of remaining tests appears to be a few percent, so that doesn't make much difference, either. Good Luck on finding a prime!

[Mystwalker]

Originally posted by MikeH
Reserving

14000 - 14020 MikeH

(and yes this is correct - same range as in 3M<n<20M)

Mike touched an interesting point here. Why not combine the two sieving efforts (for those who like)?
According to my calculations, this would save almost 14% computing power.
All we need is a new SoB.dat file with both ranges, right?

[mklasson]

Originally posted by Mystwalker
Mike touched an interesting point here. Why not combine the two sieving efforts (for those who like)?
According to my calculations, this would save almost 14% computing power.
All we need is a new SoB.dat file with both ranges, right?
The thing is that my latest idea (t power residues) depends on the n values being sparse. Including lots of n below 3M would very likely be bad for performance.

Regards,
Mikael

[MikeH]

The thing is that my latest idea (t power residues) depends on the n values being sparse. Including lots of n below 3M would very likely be bad for performance.
For information, I see a 12% reduction in speed using a 300k<n<20M sob.dat in place of a 3M<n<20M sob.dat. 12% is close to the performance gain we've seen with SobSieve recently, so I (kind of) see it as DC sieve comes for free.

Looked at another way, it's only a 55% reduction in using a 300K<n<3M dob.dat, and main sieving comes for free!

I'll probably move in the direction of using this alternative sob.dat. Currently I still use NbeGone_010 for most of my normal sieving, because the last time I compared NbeGone with SieveConsole the difference didn't seem to warrant changing. I have done some tests today, and I now find that SieveConsole 1.28 is ~60% faster than NbeGone on one of the P3s I use for the bulk of my sieving. Maybe the difference wasn't so big on AMD XP+ (which I use for testing). Anyhow, when I switch over, rather than a 60% increase, I'll get 50% plus free DC sieving.

For anyone else that's interested, I'll upload the alternative sob.dat, and give a link to it in the DC thread in a short while.

Mike.

[Nuri]

I agree with you Mike. As I mentioned above, with the latest algorithm change, it makes more sense to sieve larger ranges now. However, I have two concerns:

With the alternative sob.dat file, there will be three different sob. dats. So, there is the danger of confusion, and more importantly, the problems that might arise from using a wrong sob.dat file is much more than that might have happened if we made a changeover (in the context that I previously discussed before version 1.28). We should be very careful publicizing the alternative sob.dat file.

Secondly, the number of factors found really drops significantly for n<3m at p~20T to something like 1 factor per 5G. On the other hand, at normal sieve project everything below 14T is already reserved. Also, I'm not really sure if it would make any sense to sieve n<2m for 20T<p. So, there is a window opportunity only.

Anyhow, if you will make the alternative sob.dat file available, I'm planning to reserve double ranges as you and Joe did, for p<20T.

[jjjjL]

Originally posted by wblipp
Here's a quick calculation that suggests it might still be premature. Using what I think are the best estimates avaiilable, the expected number of primes from n=3 million to n=4 million is 0.82. According to the latest Sieve Statistics, there are 36,320 candidates left in that range, so the probability of any single test finding a prime is about 1 in 44,000. Also based on the Sieving Report, there are about 616,000 candidates left above n=3 million - finding a prime would remove one twelfth of these, about 51,000. One chance in 44,000 of taking out 51,000 candidates is only 1.1 on average. So one PrP test will on average, remove 2.1 candidates. If the same effort Sieving removes 14 candidates, it's still more efficient to sieve.

That's an interesting way to look at it. A few ideas:

I don't know how correct it is to discuss the efficiency of sieving 3M-20M vs the testing from 3M-4M. This model sorta assumes away a lot of the work we're doing in the sieving. Another way to look at it is that every number we sieved that is higher than where we find a prime is "wasted" since we didn't need to sieve that high. So if you estimates assume we're going to find a prime before 4M, they should also assume the fact that ~90% of the sieving for that k is worthless.

It will also be nice when the sieve speeds improve because we stop sieving a k. The speed of the sieve is still basically linear with the number of k's. And due to how spare the possible factors are in such large ranges (>10T) for these numbers, we may expect a slightly larger than proportional increase in speed since the kronecker/t'th power optimizations will "blank out" more p values for every k.

mklasson - you could probably comment on hard numbers for this kind of thing. do you know the proper way to calculate the increase in "blanking" based on each single prime being removed and leaving the other 11? it'd be cool to know in advance how each k might effect things before the next prime is found.

There are also a few intangibles that you may not be considering that come from finding a prime too. Increased user participation comes to mind. Sad to say, but no one at Anandtech is writing stories about how awesome our sieving is. "3rd largest prime discovered" makes a better headline than "about a dozen people run a program that involves numbers on their computers and stuff."

Another random thought I just remembered too is that the weight of each k is not constant, that it is more likely that when a prime is found, it will be found for a k value with the most n, not the least. so basically, to correct the equation i'd do something like the following:

change the expected # of primes from 0.82 --> ~6 (so it is comparing 3-20 vs 3-20 instead of 3-4), increase the # of eliminated tests from 50k-->70k. add in some sort of boost for permanantly doubling the speed of the rest of the factoring, and you'd have to include some good-will bonus for attracting new users and resources. I don't have time right now to calculate how that would effect the ratio between sieving and prp, but my ballpark estimate tells me that it is much higher than 10.

I'd still stick with my rule of thumb that says all machines over 1GHz should be running SB and sieve with the rest. Another way to look at it is that if your machine is running over 100k/s on the sieve, it'd probably be better used helping the find the next prime by runing SB.

-Louie

[Nuri]

Originally posted by jjjjL
Another way to look at it is that if your machine is running over 100k/s on the sieve, it'd probably be better used helping the find the next prime by runing SB.
-Louie

That's kind of tricky. If I used that as the rule of thumb, then I'd have to use my P4-1700 for sieve, and PIII-1000s for prp.

All other comments, I agree. Finding a prime of 1 million+ digits would definitely boost the project participation, which will become increasingly important as we go up in n values in our prp tests.

In the end, we've alredy done a pretty good job at sieving and cleared the way for prp testing pretty much. What we do from now on at sieving will still help the project, but not as much as up to now. Most of the remaining candidates will have to be prp tested anyway. If the formula I am using for factors vs p value is correct, then we should expect roughly 47,000 candidates more to be eliminated by sieving for 20T<p<200T (plus, roughly 10,000 up to 20T, both figures for 3m<n). 47,000 candidates means roughly 7-8% of the remaining candidates. So, more than 90% of the remaining candidates will be removed by prp testing.

To put it in other way, the first prime we will find will probably remove more candidates than sieving going forward.

Still, this does not mean we should stop sieving. Because, slower machines are still eliminating significantly more candidates by sieving (by a ratio much higher than x10). Also, sieving does not need the machine to be connected to the internet. Although it is a personal decision, I think the idea of using prp efficient machines (especially P4's) at prp testing, and prp inefficient machines (especially those are slower than 1GHz + those not connetted to the internet) at sieving makes sense at the p levels we are at.

[Troodon]

Originally posted by Nuri
Although it is a personal decision, I think the idea of using prp efficient machines (especially P4's) at prp testing, and prp inefficient machines (especially those are slower than 1GHz + those not connetted to the internet) at sieving makes sense at the p levels we are at.

I second that. My Tualatin needs more than 100 hours to complete a +3M PRP test, plus it's relatively more efficient at sieving (sieve depends less on memory bandwidth and cache size than PRP testing).
I think using P4's for sieving it's just a waste of energy.

[smh]

Another random thought I just remembered too is that the weight of each k is not constant, that it is more likely that when a prime is found, it will be found for a k value with the most n, not the least.

Just wondering, is the weight of each K still an issue after sieving this deep?

Disregarding factors below 5T (or 10T), is there still a significant difference in factors found for each K ?

Sieving upto a couple of T removed more candidates from K's with a low weight, thus leaving less candidates to be removed when sieving deeper compared to K's which had less candidates removed in the beginning of the sieving process

[mklasson]

Originally posted by jjjjL
mklasson - you could probably comment on hard numbers for this kind of thing. do you know the proper way to calculate the increase in "blanking" based on each single prime being removed and leaving the other 11? it'd be cool to know in advance how each k might effect things before the next prime is found.


While I don't know how to calculate it theoretically, I can always run a few tests. Doing just that for a section of 3000 primes in the 11T neighbourhood gives you the following.

Database used:
k: 4847. All remaining n = 15 (mod 24).
k: 5359. All remaining n = 6 (mod 8).
k: 10223. All remaining n = 5 (mod 12).
k: 19249. All remaining n = 14 (mod 36).
k: 21181. All remaining n = 20 (mod 24).
k: 22699. All remaining n = 46 (mod 72).
k: 24737. All remaining n = 7 (mod 24).
k: 27653. All remaining n = 33 (mod 36).
k: 28433. All remaining n = 1 (mod 24).
k: 33661. All remaining n = 0 (mod 24).
k: 55459. All remaining n = 10 (mod 12).
k: 67607. All remaining n = 3 (mod 8).
Database initialized. 624935 unfactored.
4847 has 61872 unfactored 3000000<=n<=20000000
5359 has 76825 unfactored 3000000<=n<=20000000
10223 has 71384 unfactored 3000000<=n<=20000000
19249 has 26086 unfactored 3000000<=n<=20000000
21181 has 61055 unfactored 3000000<=n<=20000000
22699 has 25069 unfactored 3000000<=n<=20000000
24737 has 64509 unfactored 3000000<=n<=20000000
27653 has 35943 unfactored 3000000<=n<=20000000
28433 has 34684 unfactored 3000000<=n<=20000000
33661 has 60512 unfactored 3000000<=n<=20000000
55459 has 85357 unfactored 3000000<=n<=20000000
67607 has 21639 unfactored 3000000<=n<=20000000

When all 12 k values are tested:
348 p values are discarded

When 4847 is skipped:
383 p values are discarded, 3% practical speedup

5359: 456 p, 19%
10223: 395 p, 13%
19249: 383 p, 1%
21181: 380 p, 9%
22699: 379 p, 7%
24737: 385 p, 9%
27653: 392 p, 9%
28433: 383 p, 4%
33661: 383 p, 10%
55459: 391 p, 13%
67607: 431 p, 23%

With that said, I must add that this is with my siever. Sobsieve's numbers ought to be similar though. These results are without using the order(2,p) idea. I get a small performance increase from using it in my siever, but judging from Pauls comments that doesn't seem to be the case for sobsieve.

Sooo, let's hope we kill off 5359 or 67607 next. :) An idea is of course to focus on prp-testing solely 67607 until either a prime is found or all n values less than 20M are eliminated. Considering how "few" n values there are left below 20M for 67607, this may actually be a good idea. Then we could take care of the other k values, with that juicy 23%-ish (assuming that's valid for sobsieve as well) speedup to go... What do you think?

Oh, and Louie, while I have you on the line... is there any way I could find out exactly which n candidates are left? I'm reading /sieve/results.txt right now, but it'd be good to see the n values eliminated by prp tests as well.

Regards,
Mikael

[wblipp]

Originally posted by jjjjL
I don't know how correct it is to discuss the efficiency of sieving 3M-20M vs the testing from 3M-4M ... There are also a few intangibles that you may not be considering that come from finding a prime too. Increased user participation comes to mind.

-Louie

I think this amounts to saying that flexible resources should be allocated in the manner that minimizes the time until finding the next prime. The previous calculation was based on the premise that flexible resources should be allocated in the manner that most rapidly removes candidates from the sieving report. In both cases there are many resources that will ignore our discussion and continue to do whatever they do - we are only concerned with the effect of moving a small number of computers.

It's possible that sieving is still best - If the sieve removes 2 candidates that are higher than the last assigned value but lower than the next prime, then sieving would be more effective. If on average sieving removed less than 1 from this range, then prime testing is the quickest way to the next prime. If the next prime is already assigned, then it doesn't matter what we do.

We can model this. Use the Proth Weights and Poisson model to calculate the probability of no primes between 3.4 million and "x", and take the negative inverse to get the probability density the next prime is "at x." Fit a cubic spline to the total number of candidates remaining, and use this to calculate the fraction of candidates between 3.4 million and x - this is the probability an eliminated candidate is in the right range to speed up the next prime. Multiply by 14 because we can detect 14 candidates through sieving in the same time we can do on prime test. Numerically integrate over all values of x.

The reullt is that on average, the 14 sieving results will remove 1.15 that come before the next prime. Technically this says that sieving is a tiny bit more effective than prime testing. Practically, it says they in a dead heat for effectiveness in getting to the next prime.

[Troodon]

I have tried sobsieve 1.28 in Windows 98 SE and the console version is ~10000 p/s slower than in Windows 2000 but the GUI version is ~21000 p/s faster (159000 p/s versus 180000 p/s). The buggy 1.26 GUI does 190000 p/s!

[paul.jobling]

Originally posted by mklasson
[B]Paul,

a small note on biquadratic residues.

If p = 3 (mod 4) then b is a biquadratic residue iff b is a QR.


I have been thinking a lot about biquadratic residues recently, as I know that a faster implementation will speed up the program slightly. Ditto for octic and sextic. I thought that I had something last week and saw a dramatic increase in speed - infortunately it turned out to be a bug :( However, should I manage to get a speed up I will let you know.

It turns out that for the values of k that we are interested in, we only perform a biquadratic test when p=1 mod 4. Think about gcd(p-1,4): it is 2 when p=3 mod 4.

However, I know that if I can find a fast test for biquadratic residues (using bit-twiddling, in the same way as the Kronecker symbol can be evaluated) I can make the code a little faster.

Regards,

Paul.

PS Last Wednesday night I was scribbling away and my partner asked what I was doing, so I replied to her that it was to do with "biquadratic reciprocity". You don't get to say that very often!

[paul.jobling]

EDIT: I was seeing an artifact. Ignore!

[paul.jobling]

Originally posted by mklasson
afaik the P4's [regular, not sse2] fpu is horribly slow. I'm guessing Paul is using it to do modular multiplication, which is where most of the work goes. Of course, that's just a guess and I'd be most pleased to get confirmation on that... I'm having trouble writing a really fast mod_mul myself.

Regards,
Mikael

Yes, the P4 is not too hot when it is given 'normal' integer and FPU computations rather than SSE2-optimised code. And Mikael says, most of the work in SoBSieve is modular multiplication, and to do that efficiently SSE2-specific code should be used (which I do have in NewPGen, but I have not put it in SoBSieve yet).

Regards,

Paul.

[AlanSimpson]

hi, just looked through some of my sieving results. I have found one factor:
11817166171171 | 22699*2^3317518+1
where the exponent is below the largest exponent tested.

There are a few others (in the 3,500,000's) which are getting close too.

My interval should be complete within 10 days, which wondering if I should report some of the factors now.

Alan

[Mystwalker]

My interval should be complete within 10 days, which wondering if I should report some of the factors now.

Depends on the answer to the question raised in this thread:

http://www.free-dc.org/forum/showthread.php?s=&threadid=2870

In every case it's advisable to submit factors close to the maximum of the current test window immediately, as there is no need to do a PRP test on that k/n pair.

If tests gets deleted ASAP, then it would be better to report factors within the current test window, too. For the individual computing that test at that time it might be unsatisfying to have the test aborted, but maybe he can be credited for the full test anyway.

[Troodon]

I have been sending immediately the factors found for 3M<n<4M for the reason Mystwalker has said.

[mklasson]

Originally posted by paul.jobling
It turns out that for the values of k that we are interested in, we only perform a biquadratic test when p=1 mod 4. Think about gcd(p-1,4): it is 2 when p=3 mod 4.
Doh... :)

Regards,
Mikael

[Mystwalker]

I usually report factors whose n's are max. ~100,000 bigger than the current test window immediately - so now it would be all below a little over 3.5M...

[Joe O]

This is what WinTop reports for V1.28 after running 4 days:

[MikeH]

Along the same lines of "why don't we increase the base n above 3M to increase the sieve speed", here's another slightly more controversial idea.

Why not eliminate the three k with the lowest densities of remaining factors (19249, 22699, 67607) from the sieve? Each of these k have about 1500 candidates remaining for each band of 1M n. Compare this with k=55459, where there are about 5000 candidates per 1M n.

Removing these three k would increase the sieve by an apparent 25% (measured), but because there would then be fewer candidates, 12% fewer candidates to be precise, the actual increase in removal of candidates would therefore reduced to 10%.

125% * 0.88 = 110%

Don't think for one second that I am suggesting we do this. After all I am one of a small number promoting the 300K-20M sob.dat file. Just thought it worth sharing.

[Moo_the_cow]

Speaking of controversial ideas, i have another one:

Why don't we just design a sieve program to skip a 0.1G
p range every time that it finds a factor? What may result
is that we eliminate 90% of the candidates in 75% of the time,
which is obviously beneficial. At p ranges above 12T, factors
are rarely found within 0.1G of each other, so why not give it
a try?

[Mystwalker]

At p ranges above 12T, factors
are rarely found within 0.1G of each other

I'm not sure if there is a correlation between a factor and the next one. Maybe one of the "stats guys ;)" can take a look?

[Joe O]

The thing that all of you are forgetting/ignoring in your calculations is the cost of going back to do what you skip. There was one change in the double checking that "saved" less than 5% of the sieving time. If we have to go back to do the skipped work it will cost us 36% more to do it, i.e. more than 7 times what was "saved". You have to figure in the possibility that the skipped work will have to be done eventually. Pay the piper now, or later. It's your choice.

We'd be better off encouraging Paul Jobling to look at ways of enhancing the sieve. Look what happened when Mikael Klasson came up with some ideas!

[MikeH]

Maybe one of the "stats guys " can take a look? Here are the minimum differences over a selection 1T ranges of p.

Smallest gap between factors: 5814 (1112144709023 - 1112144703209)
Smallest gap between factors: 2352 (2429644969993 - 2429644967641)
Smallest gap between factors: 1750 (3186291025847 - 3186291024097)
Smallest gap between factors: 18912 (4993736964001 - 4993736945089)
Smallest gap between factors: 52134 (5791106798381 - 5791106746247)
Smallest gap between factors: 199444 (6226308522947 - 6226308323503)
Smallest gap between factors: 20120 (7489455177481 - 7489455157361)
Smallest gap between factors: 103896 (8274777839579 - 8274777735683)
Smallest gap between factors: 259314 (9463657064353 - 9463656805039)
Smallest gap between factors: 715040 (10182622395157 - 10182621680117)
Smallest gap between factors: 18990 (11769159751249 - 11769159732259)
Smallest gap between factors: 125420 (12449624067607 - 12449623942187)
Smallest gap between factors: 6780 (13377644922461 - 13377644915681)

Anything above this doesn't have too much meaning because the ranges are insufficiently complete.

So what this tells us is that the 0.1G skip would result in a loss of factors, but that's to be expected. This idea is really worth exploring. I'll see if I can produce some numbers to indicate what the gaps would be for various percentages of factor loss (say 1%, 2%, 5% and 10%). Then maybe figure out the real gains and maybe even what the optimum gaps would be for historical data.

[Nuri]

I know this does not happen very often, but here's an interesting distribution of factors at one of my ranges at around 19T.

19016946840989 | 27653*2^15416169+1
19016969629631 | 4847*2^6942063+1 => Difference: 0.02G
19019974377619 | 4847*2^11680287+1 => Difference: 3.00G
19021239524363 | 21181*2^10694372+1 => Difference: 1.27G
19021334180477 | 24737*2^12571087+1 => Difference: 0.09G
19021500951391 | 55459*2^18215866+1 => Difference: 0.17G
19021576935329 | 19249*2^2223122+1 => Difference: 0.08G

PS: The range is being sieved with 0.3m-20m sob.dat, and includes all factors for the 19016946840989 - 19021576935329 range.

Ok, this might be by chance, but I just wanted to share it because I found it intersting.

So, here's the analysis for the results.txt data, dated 27 April 03.

There are 9879 factors for n>3m, and p>10T. Of these 9879 factors, there are 1667 cases (~17%) that the difference between two factors is less than 0.1G (100 million). The same figure is 898 (~9%) for 0.05G (50 million), and 458 (~5%) for 0.025G (25 million).

There are 5822 factors for n>3m, and p>12T. Of these 5822 factors, there are 902 cases (~15%) that the difference between two factors is less than 0.1G (100 million). The same figure is 485 (~8%) for 0.05G (50 million), and 248 (~4%) for 0.025G (25 million).

There are 2187 factors for n>3m, and p>15T. Of these 2187 factors, there are 288 cases (~13%) that the difference between two factors is less than 0.1G (100 million). The same figure is 161 (~7%) for 0.05G (50 million), and 87 (~4%) for 0.025G (25 million).

And finally,

There are 728 factors for n>3m, and p>18T. Of these 728 factors, there are 81 cases (~11%) that the difference between two factors is less than 0.1G (100 million). The same figure is 44 (~7%) for 0.06G (50 million), and 25 (~3%) for 0.025G (25 million).

PS: I'm not for or against Moo's idea. Just wondered what the current actual figures were, and wanted to share.

[Moo_the_cow]

Are those unique factors only or are they unique AND duplicate
factors?

[wblipp]

Originally posted by Nuri

There are 9879 factors for n>3m, and p>10T. Of these 9879 factors, there are 1667 cases (~17%) that the difference between two factors is less than 0.1G (100 million).

I was wondering if these 9879 factors are all between 10T and 12T, or if this is the full range above 10T. I thought I'd look at result.txt and see, but I can't find a link to result.txt, either. I tried searching the Forum for result.txt and I tried looking on the Download and FAQ pages.

Shouldn't result.txt be readily accessible, perhaps from the FAQ page or the Download page?

[MikeH]

Then maybe figure out the real gains and maybe even what the optimum gaps would be for historical dataOK, here are some numbers for 9T<p<10T.

Factors in range: 2511
Gap size for 1% factor loss: 4291504, range removed: 10664387440.00, 1.07%
Gap size for 2% factor loss: 8917860, range removed: 21937935600.00, 2.19%
Gap size for 3% factor loss: 14069398, range removed: 34258984130.00, 3.43%
Gap size for 4% factor loss: 17247906, range removed: 41567453460.00, 4.16%
Gap size for 5% factor loss: 21804834, range removed: 52004529090.00, 5.20%
Gap size for 6% factor loss: 25912522, range removed: 61153551920.00, 6.12%
Gap size for 7% factor loss: 29248662, range removed: 68295625770.00, 6.83%
Gap size for 8% factor loss: 32346614, range removed: 74720678340.00, 7.47%
Gap size for 9% factor loss: 36129178, range removed: 82555171730.00, 8.26%
Gap size for 10% factor loss: 41560170, range removed: 93884424030.00, 9.39%
Gap size for 11% factor loss: 46399060, range removed: 103655500040.00, 10.37%
Gap size for 12% factor loss: 50562036, range removed: 111691537524.00, 11.17%
Gap size for 13% factor loss: 54926660, range removed: 119959825440.00, 12.00%
Gap size for 14% factor loss: 60403518, range removed: 130411195362.00, 13.04%
Gap size for 15% factor loss: 64717536, range removed: 138107221824.00, 13.81%
Gap size for 16% factor loss: 69257006, range removed: 146063025654.00, 14.61%
Gap size for 17% factor loss: 74217638, range removed: 154669557592.00, 15.47%
Gap size for 18% factor loss: 78974830, range removed: 162609174970.00, 16.26%
Gap size for 19% factor loss: 83430462, range removed: 169614129246.00, 16.96%
Gap size for 20% factor loss: 87802918, range removed: 176308259344.00, 17.63%

I've done the same thing for a few other slices of p, and it looks about the same - usually the range removed will not make up for the factors lost, therefore a net loss rather than gain.

One more thing I'd like to try is the same analysis but with all duplicates removed. Too late now, I'll try that tomorrow.

[MikeH]

Shouldn't result.txt be readily accessible, perhaps from the FAQ page or the Download page? The results.txt file can be found here (http://www.seventeenorbust.com/sieve/results.txt)

[wblipp]

Originally posted by MikeH
The results.txt file can be found here (http://www.seventeenorbust.com/sieve/results.txt)

Thanks, Mike.

My intuiton was that the scarcity of factors shortly after other factors was an illusion - factors are just plain scarce, it's just that we happen to look more often after finding one than in the other scarce regions. My intuition is supported by the following analysis that says factors are no scarcer in the regions shortly after factors.

Looking at the region from 10T to 12T, 4057 factors were found. The next closest factor was withing 0.1G for 765 of them. How many should we have expected?

Well, suppose we throw down 4057 numbers at random over a 2G range. If we pick one of them - say the 42nd on the random list, and ask "What's the probability another particular one, say the 3512th on the random list. is not in the next 0.1G?, that's 1.999/2T = 0.99995.

If we ask "What's the probability that none of the other 4056 in in the next 0.1G?", that probability is (0.99995)^4056 = 0.816

If we ask "What's the probability there IS a factor in the next 0.1G?", it's 1-0.816 = 0.184.

If we ask "If factors are distributed randomly, how often should we expect to find a factor in the next 0.1G?", the answer is 4057 * 0.184 = 745.

So the observed frequency of factors in the next 0.1G (765) is in pretty good agreement the randomly expected occurance (745), and there is no empirical support for the idea of skipping 0.1 G after finding a factor.

[Moo_the_cow]

I agree with your analysis that "there is no empirical support for the idea of skipping 0.1 G after finding a factor" ONLY IF factors
are randomly distributed among p ranges like you assumed.
However, factors are not distributed randomly, or there would
be an equal amount of factors in the p range of 1T to 1.1T as
the range 100T to 100.1 T. Additionally, you need to consider
duplicate factors, which account for ~ 10-12% of the factors
in the results. txt file.

P.S. Everyone out there, please think about this tomorrow
morining when your minds are fresh ;)
It's been a long day for me, so I'll go off and get a 15 hour
nap :o

[wblipp]

Originally posted by Joe O
We'd be better off encouraging Paul Jobling to look at ways of enhancing the sieve. Look what happened when Mikael Klasson came up with some ideas!

Is there a description of the current algorithm? Reading this thread makes it clear that sophisticated and clever things are being done, both in the conceptual algorithm and in the code implementing the algorithm - but it doesn't provide much detail about the sophistication and cleverness.

[wblipp]

Originally posted by Moo_the_cow
I agree with your analysis that "there is no empirical support for the idea of skipping 0.1 G after finding a factor" ONLY IF factors
are randomly distributed among p ranges like you assumed.
However, factors are not distributed randomly, or there would
be an equal amount of factors in the p range of 1T to 1.1T as
the range 100T to 100.1 T. Additionally, you need to consider
duplicate factors, which account for ~ 10-12% of the factors
in the results. txt file.

The point of the analysis is to show that empirically factors are uniformly distributed on the fine grain scale. We know that over large scales we can see the 1/p effect. I limited the investigated range to 10T-12T to keep this effect small. It's possible to take this effect into account, but it complicates the analysis more than it improves the insight.

For the skipping idea to work, factors must be scattered further apart than random scattering. Around 100T factors will be 10 times scarcer than around 10T - but there isn't any reason to think they become less random.

[Joe O]

Originally posted by Moo_the_cow

However, factors are not distributed randomly, or there would be an equal amount of factors in the p range of 1T to 1.1T as the range 100T to 100.1 T.


Don't confuse "distributed randomly" with "A constant Probability Distribution Function". The factors are distributed randomly, even though the PDF is proportional to 1/P. It just means that the "gaps" will get bigger as P gets bigger. But, as has been empirically shown, the gaps are not yet big enough to be useful, and may never be.
If you have been following the recent discoveries about the occurrance of prime pairs, you will know that gaps between primes have been shown to be arbitrarily small as the primes get larger. That is even though the primes are "less dense" as we look at larger numbers, it is still likely to find primes only 2 apart.
The implication for us is that even as the factors get less dense, they will still "bunch up", i.e. we can have them "arbitrarily close", one after the other, even if there has been a large gap since the last one. So even as the gaps get bigger, there will be many small gaps as well!
Random is Random.

[MikeH]

One more thing I'd like to try is the same analysis but with all duplicates removed. Too late now, I'll try that tomorrow. OK, here's the same range 9T<p<10T with duplicates removed.

Factors in range: 2152
Smallest gap between factors: 259314 (9463657064353 - 9463656805039)
Gap size for 1% factor loss: 5311112, range removed: 11312668560.00, 1.13%
Gap size for 2% factor loss: 11879568, range removed: 25042129344.00, 2.50%
Gap size for 3% factor loss: 16724332, range removed: 34903680884.00, 3.49%
Gap size for 4% factor loss: 21734678, range removed: 44882110070.00, 4.49%
Gap size for 5% factor loss: 25473506, range removed: 52067846264.00, 5.21%
Gap size for 6% factor loss: 29248662, range removed: 59140794564.00, 5.91%
Gap size for 7% factor loss: 32815372, range removed: 65663559372.00, 6.57%
Gap size for 8% factor loss: 38326158, range removed: 75847466682.00, 7.58%
Gap size for 9% factor loss: 44504090, range removed: 87139008220.00, 8.71%
Gap size for 10% factor loss: 49749696, range removed: 96315411456.00, 9.63%
Gap size for 11% factor loss: 54509928, range removed: 104386512120.00, 10.44%
Gap size for 12% factor loss: 60069066, range removed: 113710741938.00, 11.37%
Gap size for 13% factor loss: 64997382, range removed: 121675099104.00, 12.17%
Gap size for 14% factor loss: 70237644, range removed: 129939641400.00, 12.99%
Gap size for 15% factor loss: 75847726, range removed: 138725490854.00, 13.87%
Gap size for 16% factor loss: 81380094, range removed: 147053829858.00, 14.71%
Gap size for 17% factor loss: 84828528, range removed: 151503751008.00, 15.15%
Gap size for 18% factor loss: 90557064, range removed: 159742660896.00, 15.97%
Gap size for 19% factor loss: 98158960, range removed: 171091067280.00, 17.11%
Gap size for 20% factor loss: 104504390, range removed: 179852055190.00, 17.99%

So basically no change to that with duplicates. Ah well, it was worth a try.:rotfl:

[wblipp]

Originally posted by mklasson
Closer inspection of the remaining n values for each k yields the following.

for k=4847, all n values are equivalent modulo 24... Table:
k t (all remaining n equiv mod t)
4847 24
5359 8
10223 12
19249 36
21181 24
22699 72
24737 24
27653 36
28433 24
33661 24
55459 12
67607 8

Regards,
Mikael

I don't really understand if the power of this idea comes from having large t values. Just in case it does, I want to point out that for k=5359 and t=24, all remaining candidates are equivalent to 6 or 22 modulo 24 - these collapse to the single 6 modulo 8. This happens from the divisibility of 4 primes:
n=1 mod 2 is divisible by 3
n=0 mod 4 is divisible by 5
n=2 mod 12 is divisible by 13
n=2 mod 8 is divisible by 17

Similarly, for k=67607, all remaining candidates are equivalent to 3 or 11 mod 24. The remainder are removed by the same primes
n=0 mod 2 is divisible by 3
n=1 mod 4 is divisible by 5
n=7 mod 12 is divisible by 13
n=7 mod 8 is divisible by 17

So if large t-values are really helpful, then the remaining candidates for these two k's could be split into two subsets, each with t=24.

[mklasson]

Originally posted by wblipp
[B]I don't really understand if the power of this idea comes from having large t values. Just in case it does, I want to point out that for k=5359 and t=24, all remaining candidates are equivalent to 6 or 22 modulo 24 - these collapse to the single 6 modulo 8.
[...]
Similarly, for k=67607, all remaining candidates are equivalent to 3 or 11 mod 24.
I've actually thought of this, but hadn't posted it here... You can do the same thing with varying degrees of advantage with all of the k values. It's definitely not a bad idea either, it gave me about a 30% boost.

k: 4847 t: 120(5*24) : 3 diff. t/diff: 40 factor: 1.66667
k: 5359 t: 120(15*8) : 6 diff. t/diff: 20 factor: 2.5
k: 10223 t: 96(8*12) : 5 diff. t/diff: 19.2 factor: 1.6
k: 19249 t: 720(20*36) : 9 diff. t/diff: 80 factor: 2.22222
k: 21181 t: 264(11*24) : 8 diff. t/diff: 33 factor: 1.375
k: 22699 t: 360(5*72) : 4 diff. t/diff: 90 factor: 1.25
k: 24737 t: 120(5*24) : 3 diff. t/diff: 40 factor: 1.66667
k: 27653 t: 144(4*36) : 3 diff. t/diff: 48 factor: 1.33333
k: 28433 t: 360(15*24) : 6 diff. t/diff: 60 factor: 2.5
k: 33661 t: 360(15*24) : 9 diff. t/diff: 40 factor: 1.66667
k: 55459 t: 180(15*12) : 7 diff. t/diff: 25.7143 factor: 2.14286
k: 67607 t: 360(45*8) : 4 diff. t/diff: 90 factor: 11.25

are the t-values that seems to give the best empirical results. diff is the number of residues you get mod t. factor is new_t/diff / old_t. Essentially the best speedup you can hope for.

Regards,
Mikael

[Joe O]

21181 is the only k that has a factor of 11 in your table. If we ignore this 1 value, or handle it separately somehow in the sieve client, we could use a t-value of 720 for all of the k. If you need the valid values modulo 720 for all the k please check the attached file. Could you please run a test and show what the improvement would be using a t value of 720 for all of the k?

The counts of values are:


K #Values
4847 18
5359 36
10223 36
19249 9
21181 24
22699 8
24737 18
27653 15
28433 12
33661 18
55459 28
67607 8

The sum of the values is 230, but 14 of these are valid for 2 different k, so there are only 216 distinct values. This means that we would be looking only at .3 of all possible values for p mod 720. There should be some advantage of only having to compute p mod 720 instead of p mod 7 different values.

[Joe O]

Although implementing the MOD720 suggestion includes this, I thought that I would state this separately, since it stands on its own and could be implemented if the MOD720 solution proves to be too computationaly intensive.

The program already disallows k==0 (mod 3) to cut in half the number of candidates. Since
k==1 (mod 3) and n==1 (mod 2) => (k*2^n+1) == 0 (mod 3)
k==2 (mod 3) and n==0 (mod 2) => (k*2^n+1) == 0 (mod 3)

If the program disallowed k==0 (mod 5) it would cut in half again the number of candidates. Since
k==1 (mod 5) and n==2 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==2 (mod 5) and n==1 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==3 (mod 5) and n==3 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==4 (mod 5) and n==0 (mod 4) => (k*2^n+1) == 0 (mod 5)


See also:
this thread. (http://www.free-dc.org/forum/showthread.php?s=&threadid=2994)

[mklasson]

Originally posted by Joe O
[B]21181 is the only k that has a factor of 11 in your table. If we ignore this 1 value, or handle it separately somehow in the sieve client, we could use a t-value of 720 for all of the k. If you need the valid values modulo 720 for all the k please check the attached file. Could you please run a test and show what the improvement would be using a t value of 720 for all of the k?
I finally did that now, but the results were bad. The overhead from having so many residues more than eats up the performance gain from having a single t.

Regards,
Mikael

[mklasson]

Originally posted by Joe O
Although implementing the MOD720 suggestion includes this, I thought that I would state this separately, since it stands on its own and could be implemented if the MOD720 solution proves to be too computationaly intensive.

The program already disallows k==0 (mod 3) to cut in half the number of candidates. Since
k==1 (mod 3) and n==1 (mod 2) => (k*2^n+1) == 0 (mod 3)
k==2 (mod 3) and n==0 (mod 2) => (k*2^n+1) == 0 (mod 3)

If the program disallowed k==0 (mod 5) it would cut in half again the number of candidates. Since
k==1 (mod 5) and n==2 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==2 (mod 5) and n==1 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==3 (mod 5) and n==3 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==4 (mod 5) and n==0 (mod 4) => (k*2^n+1) == 0 (mod 5)

See also:
this thread. (http://www.free-dc.org/forum/showthread.php?s=&threadid=2994)
But this is just a subset of the general t-power idea, right? Specifically, it's the case with t = 4 and one remaining residue.

Regards,
Mikael

[jjjjL]

anyone who wants to weigh in on the war, i moved your comments here (http://www.free-dc.org/forum/showthread.php?s=&postid=27572) so you can continue to enjoy your enriching discussion.

-Louie

[Joe O]

I don't think that the following has yet been implemented:


If the program disallowed k==0 (mod 5) it would cut in half again the number of candidates. Since
k==1 (mod 5) and n==2 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==2 (mod 5) and n==1 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==3 (mod 5) and n==3 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==4 (mod 5) and n==0 (mod 4) => (k*2^n+1) == 0 (mod 5)

This could also be implemented in NewPGen, since it does not rely on the specific K values, except for excluding k==0 (mod 5).
This could also be generalized to k*b^n+1 as long as b==0 (mod 5) is excluded.

[mklasson]

Originally posted by Joe O
I don't think that the following has yet been implemented:


If the program disallowed k==0 (mod 5) it would cut in half again the number of candidates. Since
k==1 (mod 5) and n==2 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==2 (mod 5) and n==1 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==3 (mod 5) and n==3 (mod 4) => (k*2^n+1) == 0 (mod 5)
k==4 (mod 5) and n==0 (mod 4) => (k*2^n+1) == 0 (mod 5)

If you look at the other thread (http://www.free-dc.org/forum/showthread.php?s=&threadid=2994) you linked to, what it amounts to is that all n must be equivalent to a single value mod 4 for a given k. Those values are what you get if you take:


k: 4847. All remaining n = 15 (mod 24).
k: 5359. All remaining n = 6 (mod 8).
k: 10223. All remaining n = 5 (mod 12).
k: 19249. All remaining n = 14 (mod 36).
k: 21181. All remaining n = 20 (mod 24).
k: 22699. All remaining n = 46 (mod 72).
k: 24737. All remaining n = 7 (mod 24).
k: 27653. All remaining n = 33 (mod 36).
k: 28433. All remaining n = 1 (mod 24).
k: 33661. All remaining n = 0 (mod 24).
k: 55459. All remaining n = 10 (mod 12).
k: 67607. All remaining n = 3 (mod 8).

and limit the modulo to 4 instead of the higher - better - multiple of 4. I.e. it's a subset of the t-power test.

Regards,
Mikael

[paul.jobling]

Hi there,

Somehow I managed to stop myself being notified of updates to this thread, so I didn't see these comments until just now.

First off, the mod 5 is implicitly used by the t-power test, as Mikael correctly states.

Secondly, I saw the idea about using a higher mod value and gave it some though. To do it properly, I would have to have each k in the sieve multiple times. The thing is that to get an advantage, I have to be able to multiply by 2^t mod p quickly. I can do that for t<=48; for higher values of t (for example 720 or 120) that is not so easy.

If I limit myself to t=48, there is still an advantage to be gained. For example for k=67607, all n are=3 mod 8. However, mod 48 they are equal to the four values 3, 11, 27, and 35. So we can get through that particular k value in 2/3 of the time.

Lets see:

k old t t=48
4847 24 2/2 (No gain)
5359 8 4/6
10223 12 3/4
19249 36 No gain
21181 24 No gain
22699 72 No gain
24737 24 No gain
27653 36 No gain
28433 24 No gain
33661 24 No gain
55459 12 No gain
67607 8 4/6

So looking at it, there is definitely scope for a small performance increase. On the figures above, the gain should be about 17%, which isn't too bad. It might shift the optimum alpha value, but I will cater for that in code.

Also, I have done some small tweaks to the assembler anyway, and it is (on this P3) about 4% faster. So we should be looking at about a 22% performance improvement if I have done my math right.

I'll keep you posted.

Regards,

Paul.

[paul.jobling]

On implementation, I see a 16% gain, which isn't too bad :) .

Is there anybody who has got some test values? I really need to know the n's removed for k=5359, 10223, and 67607.

Regards,

Paul.

[mklasson]

Originally posted by paul.jobling
On implementation, I see a 16% gain, which isn't too bad :) .

Have you at least tried t values higher than 48 to see if it's faster?

Granted, I don't know what spooky things you're doing to multiply so much faster by 2^48 than by higher values. :) I just know higher values are very beneficient for me.

Regards,
Mikael

[Mystwalker]

You can use the values in the results file:
http://www.seventeenorbust.com/sieve/results.txt

Maybe 1004115398383 (1004G) - 1004515852098 (1005G) provides a nice testbed:

2x 5359
4x 10223
2x 67607

p k n

1004115398383 10223 2910521
1004143824433 67607 5886747
1004190214861 22699 16711174
1004212760959 21181 7662932
1004224501807 5359 1093182
1004242561667 21181 8988428
1004281725373 10223 7559237
1004282905711 5359 18736486
1004297287733 4847 2138727
1004327139227 5359 19246182
1004329974253 10223 16083689
1004425684013 10223 13782437
1004428333609 24737 6955423
1004446463039 55459 11026750
1004482778209 10223 3464765
1004484316531 55459 5359078
1004515852097 67607 3942387


Maybe the lower ranges would be even better due to the fator density, but I don't know the name of the appropriate result file. :(

[jjjjL]

http://www-personal.engin.umich.edu/~lhelm/lowresults.zip

These are the 1G - 1T sieve results.

-Louie

[paul.jobling]

Originally posted by mklasson
Have you at least tried t values higher than 48 to see if it's faster?

Granted, I don't know what spooky things you're doing to multiply so much faster by 2^48 than by higher values. :) I just know higher values are very beneficient for me.

Regards,
Mikael

I can do a 62 bit a*b mod p with 25 assembler instructions. Not too shabby :) The basic technique is due to Peter Montgomery, and can be implemented in C as follows:

uint64 mulmod (uint64 a, uint64 b, uint64 p)
{
uint64 y = (uint64)((float64)a*(float64)b/p+0.5);
uint64 r=a*b-y*p;
if (r<0) r = r+p;

return r;
}

Since this is the heart of the code, to work with higher values of t I need an implementation that is at least this fast, relatively, when the gain is factored in. Hmm, it might be possible, I will have to give it some thought. The main thing is that in this case, we are not dealing with random a, b - instead, b will be a big power of 2. So it comes down essentially to doing something like

r = (a<<b)%p;

where b is the big power of 2, eg 360, and a and p are 48 bit integers.

Thanks for the test data, I will try it out.

Regards,

Paul.

[olaright]

I have a suggestion about the sieving:

why don't we start a new threat; what we need is this:

a few (very short) ranges to test
links to all the different versions of paul's sieving program
(or maybe a new webpage for easy download)

then we can do this:

everyone who likes does the test and submits his results (average rate),

and then someone can make:

a nice graph of the different systems (AMD/PIII/PIV)
performance versus version number.

This would be totally cool :)

regards,

ola

[mklasson]

Originally posted by paul.jobling
I can do a 62 bit a*b mod p with 25 assembler instructions. Not too shabby :)

Since this is the heart of the code, to work with higher values of t I need an implementation that is at least this fast, relatively, when the gain is factored in.
Just doing a powmod to get 2^t mod p and then using that as the multiplier in the loop works fine for me (though I'm using (2^(-1))^t).

Regards,
Mikael

[paul.jobling]

Originally posted by mklasson
Just doing a powmod to get 2^t mod p and then using that as the multiplier in the loop works fine for me (though I'm using (2^(-1))^t).

Regards,
Mikael

True, it can be a one-off hit it the start of the inner loop. But I am currently trying to sort out another problem :(

[jjjjL]

Originally posted by paul.jobling
I can do a 62 bit a*b mod p with 25 assembler instructions. Not too shabby :) The basic technique is due to Peter Montgomery, and can be implemented in C as follows:

uint64 mulmod (uint64 a, uint64 b, uint64 p)
{
uint64 y = (uint64)((float64)a*(float64)b/p+0.5);
uint64 r=a*b-y*p;
if (r<0) r = r+p;

return r;
}

Since this is the heart of the code, to work with higher values of t I need an implementation that is at least this fast, relatively, when the gain is factored in. Hmm, it might be possible, I will have to give it some thought. The main thing is that in this case, we are not dealing with random a, b - instead, b will be a big power of 2. So it comes down essentially to doing something like

r = (a<<b)%p;

where b is the big power of 2, eg 360, and a and p are 48 bit integers.

Can you optimize for the fact that the number is constant and the value you're moding by is changing in a slow, predictable way.

Since you know 2^t is constant, couldn't you basically precalc the above y value once and then use it for all p? Even as p grows, the y will never change by more than 1 between p's. Just make y right the first time so that r > 0 and then do the check to see if r becomes negetive. If it does, then you just hit the spot where y changed so you update the precalced y value and fix that r. This works assuming the sieve is going through sequentially larger p values (in other words, the sieve doesn't ever go from higher to lower p values).

For t=48, this works incredibly well since we are sieving around p=2^44. Due to the fact that there is only a 16x difference the y value would rarely change. For instance, I was playing with typical #s and

for p~15T you would subtract 17*p from 2^48.

for p~20T you would subtract 13*p from 2^48.

So it would only have to catch the 4 transitions in 5T worth of sieve space. Considering the average person checks out ranges 100x smaller than that, it's likely that y would only need to be precalced once each time the program runs.

You could also find all the transistions and just make a static lookup table for t=48 in the program for all p values between 2^43-2^48. There would only be about 20 values in it. Help save that single y calculation for each run. ;) You might also be able to check the bounds on the sieve window and eliminate the negetive r check if there is no transistion.


Paul, as I read your comment again, I realize I'm only optimizing finding 2^48 (mod p) by turning the mod into a subtraction. This doesn't solve the more general problem of multiplying that number. However, I've already written all this so I guess I'll post it and maybe it will give you or the others some new ideas.

-Louie

[paul.jobling]

Well, the other problem that I was trying to sort out was all to do with these high-precision a*b mod p values. When I went to 48 bits, there was some extra sorting out that I had to do - basically, that

if (r<0) r+=p;

test was not required before, whereas now it is. And it costs time to do the test... so the program is now about as fast as it was before :(

But remember that that is only allowing for t=48. There is definitely the scope to go higher... I will do some playing around and let you know.

By the way, I think that the best way to do this is to make a new release of the software and the SoB.dat file as well. The SoB.dat file will contain the multiple copies of the k values.

Regards,

Paul.

[paul.jobling]

Well, I managed to change the code so that the 48 bit limit was not present, but unfortunately the result was that it ran at about 60% of the speed before. Which is a shame, as it was a good idea.

However, I have persevered with the multiple 48 bit version and on this Athlon XP2100 it is about 16% faster than 1.28. This arises from the 48 bit changes as well as a switch to a binary gcd algorithm. Once I have got it all tidied up, I will post it here.

Regards,

Paul.

[paul.jobling]

I have had a successful day

I have

a) changed the GCD and Kronecker algorithms to use binary versions, removing the slow divisions that are otherwise required;

b) made the software automatically make multiple copies of the values for a given k, if it gives a saving;

and

c) by noting that if and only if x is a t-th power then x.2^t is as well, so some time can be saved by reusing calculated values....

I have got a version that runs 37% faster on this Athlon. Which is nice :)

[Troodon]

I still haven't tried the new version, but, Paul, could you make SoBSieve save to disk when Windows is closed? Also, an option to start minimized would be very useful. Thanks!

[Troodon]

On my Tualatin:
· In Windows 98 SE SoBSieve 1.30 is as fast as 1.28.
· In Windows 2000, 1.28 was 20000 p/s slower than in Windows 98. With 1.30, SoBSieve works in Windows 2000 between 2000 p/s (300k-20M) and 4000 p/s (3M-20M) faster than 1.30/1.28 in Windows 98. That's a ~24000 p/s increase.

Thanks Paul!

[Moo_the_cow]

Paul, does SoBSieve v.1.30 need a higher alpha (like 3.5) for it to run faster on most PCs?
It appears that an alpha of 3.2 works fastest on my P-III.

edit: Whatever alpha value I use, I have been unable to improve my CPU performance by more than 4000 p/sec. Also, i am using Windows 98.
Is this normal?

[paul.jobling]

OK, first things first: your CPU is more important than your operating system. Also, rather than just saying that it is x faster, it is important to know that it is x faster than y - 4000 better than 2000 is more important than 4000 better than 400000.

I do my best to improve performance, but you must note that while algorithmic improvments should see things improve across all processors, there will be some tweaks that are processor specific. Since I did the development yesterday on an Athlon, Athlon users will get the most benefit from it.

The Alpha may well need changing, and I recommend that you experiment to find the best value for your system.

Oh, and I did some more work last night... there might be a 1.31 soon, but I will compare it with the 1.30 with on a PIII first.

Regards,

Paul.

[Troodon]

Paul, have you considered a "multi-path" version, with CPU-specific paths? Or is it not worth the effort?
Have tried alpha=2.000, 2.500, 3.000 and 2.500 is still the fastest.

Moo that's normal, see my previous post.

[Xeltrix]

Absolutely brilliant increase.
My XP 1800+ went from 178kp/s to 240kp/s

So an amazing 35% increase. :D

Well done!

EDIT: Actually after running the worker thread at normal and leaving the machine alone it got up to 249kp/s [alpah 3.5] making it a 40% increase! :|party|:

[MikeH]

Excelent work Paul. For P3-850 best alpha seems to be about 2.0.

Any chance of an updated console version?

Thanks,
Mike.

[Moo_the_cow]

Weird. An alpha value of 3-3.2 still works fastest on my P-III (800 Mhz)
Oh yeah, the improvement for my PC (4000 p/sec) is from 93500 p/sec to 97500 p/sec.
BTW, does the p range you're testing have any effect on the optimal alpha values?

[paul.jobling]

Hi all,

OK, in answer to some questions, I am trying to keep to a single codebase for all processors. If an algorithm is fast on a PIII it ought to be fast on an Athlon. Fortunately I have got access to both so I can verify it.

With that in mind, yesterday on the Athlon I produced 4 different versions that all ran at about the same speed, and tried them out today on this PIII. The results are:

1.30 release 42.9 kp/sec
1.30 release with smaller cache requirement 47.3 kp/sec

1.31 48.5 kp/sec
1.31 with smaller cache requirement 53.4 kp/sec

So I will now release 1.31 with the smaller cache requirement. Athlon users might see a slight improvement; other users will definitely (I hope) see an improvement.

This also includes the console version.

Regards,

Paul

[paul.jobling]

Originally posted by Moo_the_cow

BTW, does the p range you're testing have any effect on the optimal alpha values?

I would have thought not. The important factors in deciding alpha are the range of n, and how many k values are being sieved together.

By the way, this new release may well need some experimentation to find the best alpha value.

Regards,

Paul

[MikeH]

Paul,

Great job again. But there seems to be something wrong with the console version. On this PC (XP 2100+), I see the following

SobSieve 1.31 ~280Kp/s
SobSieveConsole 1.31 ~70Kp/s

Thanks,
Mike.

[Xeltrix]

I can confirm the same problem on my XP 1800+

GUI: ~250Kp/s
Console: ~59Kp/s

Console also takes an age to start up. 3-5 secs.

[paul.jobling]

I have managed to get some more speed out of it... on this Athlon the rate goes from 258 kp/sec to 300 kp/sec. Which isn't too bad :)

Mike/Xeltrix, the console rate problem was just a reporting problem - it worked out the rate incorrectly (I report the rate a quarter of the time now... but I didn't multiply the relevant variable by 4 in the console code). That has been fixed as well.

[Mystwalker]

Be careful not to surpass the speed limit! :p

Damn, that new versions are blazing fast! 161kp/sec for a 900 MHz Duron? Is was "only" a bit more than half that much with 1.28 - which was the current version 3(!) days ago!

Maybe you should do how Mr. "Scotty" Scott does: Lower expectations and than - Wham! - surpirse everyone. Hm, maybe you already do... :D


One strange thing:

I got 19 factors within a range of 2.1G around 14T - and all those factors are indeed valid! Did you make sure that those new versions do not find any additional (but nevertheless valid) factors compared to the prior versions? If yes, it may be pure coincidence... :cool:

Ah, before I forget it:

FANTASTIC WORK, PAUL! :cheers:

[Troodon]

Paul I love you!!! Haven't done extensive testing (other apps running, only tested in Windows 2000), but I got a ~50000 p/s increase (from 165 to 215 kp/s) versus 1.30! The only problem I see it takes 190 Mb of memory :eek: , but it's worth :) .
The console version crashes on my computer.

[MikeH]

Paul,

I have some concerns about SobSieve 1.31. It is producing way too many factors. On my test PC, where the sob.dat file has not changed (still the alternate 300K-20M file), in an 8G range 20.200T-20.208T it found 35 factors. This is much too high, in this region even with a "lucky" 8G I would expect no more than (say) 15 factors.

I am able to parse the results with my Sieve Scoring program. Of the 35,

13 are unique (high, but OK - must be correct)
1 is duplicate (about what I'd expected)
21 are excluded (not good!)

Of course when submitted using the web form, all seems OK - "35 of 35 verified ... 35 new...".

However the 21 "excluded" results simply aren't present in the sob.dat file, so shouldn't be being generated.

On the upside - the speed increase is genuine, and I guessing that no genuine factors are being missed.

Cheers,
Mike.

[paul.jobling]

Originally posted by Mystwalker
Be careful not to surpass the speed limit! :p

I got 19 factors within a range of 2.1G around 14T - and all those factors are indeed valid! Did you make sure that those new versions do not find any additional (but nevertheless valid) factors compared to the prior versions? If yes, it may be pure coincidence...


That is odd... you see, for my testing I remove one particular test so that it will report divisors that are not in the bitmap. That way, I get a lot more results reported. All of the results are valid, of course, it is just that they have already been removed. But I checked and double checked and the version on the web doesn't do that... so perhaps it is coincidence. Ah, was that 1.31 (I have just seen Mike's comment)? Maybe I didn't reinstate the test in 1.31... but use 1.32 anyway, it is faster :) EDIT: I Just tested 1.31, and it definitely reports all divisors regardless of whether n is in the bitmap or not.

Incidentally, I had a real nightmare with the software just before releasing it. I was trying it out with some test numbers and it failed to find a divisor for one of the numbers. It took me a long time to see that at one point in the code I had used the register "edx" rather than the register "edi"...

By the way, I forgot to mention that this version is a heavy RAM user. 174 Mb... let me know if that is too much, and I can add an optional flag to the software to make it use less.

Regards,

Paul.

[Mystwalker]

I think that option would be useful.
I was surprised to see such a high Mem Usage for a fresh system. But strangely, the usage doesn't show up in the Task Manager... :confused:

[MikeH]

I was surprised to see such a high Mem Usage for a fresh system. But strangely, the usage doesn't show up in the Task Manager... It does if (in Task Manager) you go to 'view' -> 'select columns...', then check 'Vertual Memory Size'.

I agree it would be a nice option. I'm not sure all my sieving PCs have enough virtual memory setup right now. On the other hand, if less memory means less speed, I'd be better off just increasing the VM size.

BTW Fantastic job Paul. :)

And preliminary news on v1.32, it seems to be producing less factors, so the problem with 1.31 seems to be resolved. We'll see from the sieve scores over the next few days who has been using 1.31;)

[Mystwalker]

It does if (in Task Manager) you go to 'view' -> 'select columns...', then check 'Vertual Memory Size'.

193 MByte... neat... ;)

ATM I'm running the sieve on two systems sporting 512 MB RAM - but tomorrow two 256 MB machines will run again...

[Joe O]

I've got Task Manager showing 1700K for V1.32 and 2200K for V1.31!

[Mystwalker]

I've got Task Manager showing 1700K for V1.32 and 2200K for V1.31!

Mine says 3.5 MB. But when you add the column "Virtual Memory Size", you see the difference...

[Xeltrix]

I don't get a chance to report on anything! All very quick. (Siever and responses!)

So now 1.32 is 100Kp/s faster than the siever I was using 4 days ago! Mindblowing.

Also noticed 1.31 was suddenly giving me an influx of factors. It is gone now...

So all in all an amazing job Paul!!!

Now to go reserve (what used to be) insanely large amounts of p for me to sieve!

[jjjjL]

wow, i don't watch the forums for 12 hours and Paul has already released two new sievers. nice work. ;)

I didn't try ver 1.31 since it ignores the bitmaps but here is what I see speedwise for v1.32.

I installed it on a t-bird athlon 1.4Ghz(100MHz fsb) and it went up from 220k to 245k. Changing alpha from 2.0 --> 3.0 increased it to 255k. This was from v1.30 to 1.32. The console version appears to give almost no increase in speed... nothing I can notice.

I am also very impressed w/ its performance on a Duron 600 I installed it on.

ver rate alpha
v1.28 56k a=2.5
v1.30 80k a=2.5
v1.32 95k a=2.5
v1.32 100k a=3.5

So the smaller cached Duron seems to enjoy a big increase. Makes me wonder how a P4 might do now.

I saw someone mentioning that the sieve scores might get skewed because of v1.31 since it will report extra factors. I'll look into it. Even though the verifier accepts them, that doesn't mean it saves the factor in the db. I'm pretty sure it checks to make sure there's a proth number in the database first and I only added those for numbers that didn't have factors below 1G. So while it's possible a few might get though, it's also likely that the database wouldn't even save them. I'll go though the code and let you know. Mike, for now you may want to add a check to the factor stats to see if the factors are for numbers in the SoB.dat. You may want to discount those that aren't. I can find you a copy of the original dat file if you want it or you can exclude the check for numbers below p=210G which is about where the current dat file was sieved to when it was created. I think a few numbers above it were also done so I'd just exclude all p < 1T from such a check for now.

-Louie

[Joe O]

Originally posted by Joe O
I've got Task Manager showing 1700K for V1.32 and 2200K for V1.31!

OK, so that is the "working set". The total virtual memory is 34228K for V1.31 and 56612 for V1.32.

[paul.jobling]

Originally posted by MikeH
It does if (in Task Manager) you go to 'view' -> 'select columns...', then check 'Vertual Memory Size'.

I agree it would be a nice option. I'm not sure all my sieving PCs have enough virtual memory setup right now. On the other hand, if less memory means less speed, I'd be better off just increasing the VM size.


OK, I had a brainwave tonight and I worked out how to get rid of loads of the extra memory that it is using. This probably wont make it any faster, but it will make it a better friend to the other programs that you are running.




BTW Fantastic job Paul. :)


Hey, I am just reacting to the great ideas that people are having on this forum. There was a really interesting conversation with mklasson, Joe O, MikeH, wblipp, and others, about using higher powers of t a few weeks ago. And basically I am implementing ideas that came out of that along with trying to reuse calculated values as much as possible.




And preliminary news on v1.32, it seems to be producing less factors, so the problem with 1.31 seems to be resolved. We'll see from the sieve scores over the next few days who has been using 1.31;)

*chuckle* Please move to 1.32 - it is faster!

Regards,

Paul.

[MikeH]

I'll go though the code and let you know. Mike, for now you may want to add a check to the factor stats to see if the factors are for numbers in the SoB.dat. You may want to discount those that aren't. It's no problem, I already use my own 1G sieved sob.dat file, so I can catch anything that would have fallen out before 1G. Anything that would have fallen out between 1G and the current sieving ranges will just be clasified as yet more duplictes.

Prior to today, only Nuri and myself had submitted "excluded" factors, and that was due to me not constructing the first alternate sob.dat file correctly. My guess is there will be another half dozen with excludeds once todays stats are ready.

[paul.jobling]

Hi all,

Here is a 1.33 release. This uses a lot less memory than 1.32, but is just as fast - in fact, it might be a tad faster (but the difference is negligible).

Regards,

Paul.

[MikeH]

Again, many thanks Paul.

Preliminary findings:

On AMD XP2100+ 1.32 is faster than 1.33 by ~5%.
On P3-850 1.33 is faster than 1.32 by ~5%.

Could be memory related - AMD has 768M, P3 has 256M.

"Pick and mix" sounds good to me.

Mike.

EDIT: Just to clarify, these numbers refer to the console version.

[ceselb]

Wow, very nice.

PII-350 alpha=3.5 (alternate sob.dat) 1.30 36k 1.33 48k


Watch out :machgun: 30000 :sniper: here we come. :D

[priwo]

great job Paul

1.28 203kp/s
1.33 254kp/s

on a P3-Celeron(Tualatin) with 1500 MHz, 128 MB SDRAM, alpha=2.5

1.32 didn`t work (system crashed after some minutes)

[Troodon]

Thanks Paul! 1.33 console is a bit faster than 1.32 GUI (~225000 p/s), while 1.33 GUI is as fast (or as slow) as 1.32 console (~210000 p/s). That's with 300 k - 20 M SoB.dat and Windows 2000.

Priwo, what speeds gets that Tualatin on PRP testing? Here's (http://www.free-dc.org/forum/showthread.php?s=&postid=27874#post27874) my problem. Could you reply in that topic, please? Thanks!

[OberonBob]

ok, this is great, but is there any chance for a Linux version?

We non-windows folks are not feeling the love.

Should I bother to see if I could run this under Wine?

[priwo]

Tualatin-Celeron 1500 doing prp-test:

n=3673052 k=21181
cEMs/sec=155.000 time left (for full test)=91hours 5minutes

[Joe O]

While V1.33 gives me the best results for n<20M for p around 17.3T, V1.28 gives me the best results for n <3M for p around 3.3T

113232 p/sec V1.28
108353 p/sec V1.30
92915 p/sec V1.32
90278 p/sec V1.33
Celeron/450 Win NT 4 3.3T for the p range
This is for lower range sieving, i.e. n < 3M

68157 p/sec V1.33
67575 p/sec V1.32
47477 p/sec V1.30
46458 p/sec V1.28
PIII/500 Win98SE 17.3T for the p range
This is for the full range sieving, i.e. n <20M

[paul.jobling]

Originally posted by OberonBob
ok, this is great, but is there any chance for a Linux version?

We non-windows folks are not feeling the love.

Should I bother to see if I could run this under Wine?

Yes, definitely!


I have been thinking about a Linux version, but haven't had the time to get it done properly. If there are any volunteers out there who have got time and know gcc and embedded assembler (like this:

int x (int y)
{
unsigned halftoMinNum;

asm("shr $1,%edx ");
asm("rcr $1,%eax ");
asm("movl %eax,halftoMinNum");
}

)

then let me know. The pain is that the assembler all needs to be changed round - the VC++ version of the above is


int x (int y)
{
unsigned halftoMinNum;

_asm
{
shr edx, 1
rcr eax, 1
mov dword ptr halfto MinNum, eax
}
}


Regards,

Paul.

[mklasson]

Originally posted by paul.jobling
The pain is that the assembler all needs to be changed round
Perhaps an automated intel->at&t converter would be least painful?

A quick search yields:
http://www.delorie.com/djgpp/mail-archives/djgpp/1995/06/06/05:48:34

Might just work. It seems like you'll have to write a filter that converts "_asm{" to at&t as well, makes a string of the instructions, and so on, but that should be relatively easy. Of course, a more thorough googling might come up with a better tool.

Regards,
Mikael

[MikeH]

Paul,

A few quick questions. When I'm using SobSieveConsole, how do I set the alpha? When I use SobSieve and change the alpha, the value is remembered. Is this stored value then used by SobSieveCosnole?

I have taken a quick look through the registry, and uless the alpha is stored as part of 'FriendlyCacheCTime', then I can't see anything obvious.

What would be nice is to have the ability to set the alpha as a command line parameter (or config file) for SobSieveConsole.

Thanks,
Mike.

[paul.jobling]

Originally posted by MikeH
Paul,

A few quick questions. When I'm using SobSieveConsole, how do I set the alpha? When I use SobSieve and change the alpha, the value is remembered. Is this stored value then used by SobSieveCosnole?

I have taken a quick look through the registry, and uless the alpha is stored as part of 'FriendlyCacheCTime', then I can't see anything obvious.

What would be nice is to have the ability to set the alpha as a command line parameter (or config file) for SobSieveConsole.

Thanks,
Mike.

Mike,

use

-a=<value> on the command line, for example

SoBSieveConsole -a=3.0

You can also use

-o=<file name>

to tell it the name of the status file to use. This is useful on multiprocessing systems or clusters to enable one SoB.dat file to be shared by many instances of the program.

Mikael,

Thanks for that link - it looks good. Some small modifications are required, but not too much.


Regards,

Paul.

[MikeH]

Many thanks Paul. Very useful.

[Moo_the_cow]

From Mike's stats page it appears that SoBSieve v.1.33 is producing extra factors.
On Mike's stats, I have 1 excluded factor, and I didn't use versions 1.31 or 1.32.
Paul (or anyone else), do you know what is the reason for this?

[MikeH]

On Mike's stats, I have 1 excluded factor The excluded factor (in results.txt format) is

12620584122611 22699 3808774 2537 NULL

... and for anyone that's interested, here's a full list of the factors that are spat out by the scoring as excluded.

[Keroberts1]

is it possible for one value ot eliminate several different N values or maybe Nvalues for different Ks? I don't need the technical info on this justa yes or no but als oif the answer is yes does the sieve program check for this?

[jjjjL]

yes, it is possible. although unlikely at such high factor levels, it has happened.

5018720299 divides both 19249*2^5609822+1 and 21181*2^13471484+1.

This was sieved out with an older version of the sieve such as v1.04 but there's no reason why it wouldn't still check for those.

-Louie

[paul.jobling]

Originally posted by Keroberts1
is it possible for one value ot eliminate several different N values or maybe Nvalues for different Ks? I don't need the technical info on this justa yes or no but als oif the answer is yes does the sieve program check for this?

The answer is yes, yes, and yes.

Definitely one p can eliminate n values for different ks. It is also true that one p can eliminate many ns for one k value - particularly when p is small (for example, p=3 eliminates half of the n values for these particular k values). Fortunately, the software finds all eliminated k values.


As for the software finding factors that have already been excluded.... I will look into it. Are we sure that this isn't a case of different SoB.dat files being used?

Regards,

Paul.

[biwema]

Hi,

Is there a version of SoBSieve available which is maybe a little bit slower then 1.33, but can handle factors beyond 281500 G like versioin 1.22?
At the moment 1.22 is only half as fast as 1.33.

Thanks,
Reto

[paul.jobling]

Originally posted by biwema
Hi,

Is there a version of SoBSieve available which is maybe a little bit slower then 1.33, but can handle factors beyond 281500 G like versioin 1.22?
At the moment 1.22 is only half as fast as 1.33.

Thanks,
Reto

Hi Reto,

You know...thinking about it, the math in the current version should be good up to 2^60. I will check, and if it is the case (and I am 90% sure that it is) I will ease the restriction.

Paul.

[Mystwalker]

From the gap analysis file:



SER+RAT: 21011.96G - 21031.60G, size: 19.65G, est fact: 22 (21011958908903-21031604828711)
( 19.65G) : 21000-21100 Mystwalker
RATIO: 21055.60G - 21070.94G, size: 15.33G, est fact: 10 (21055604737771-21070935933361)
( 15.33G) : 21000-21100 Mystwalker


I wonder why the estimation says 22 factors for a 20G range (--> 1,12 factors/G), but only 10 factors for a 15G range (--> 0,65 factors/G). The size difference of the factors is not that big to make this change due to the growing factor sparsity, right? Is it SER+RAT vs. RATIO?

[MikeH]

I wonder why the estimation says 22 factors for a 20G range (--> 1,12 factors/G), but only 10 factors for a 15G range (--> 0,65 factors/G). The size difference of the factors is not that big to make this change due to the growing factor sparsity, right? Is it SER+RAT vs. RATIO? The estimate of the number factors is based on the distribution of factors that immediately precede the identified gap (I think, I don't have the code in front of me). To be honest, this is a very very crude estimate, and shouldn't be taken too seriously. The final estimate of factors in the whole range is even cruder.

..and yes this is kind of characterised by the SET+RAT vs. RATIO. Where there is a SET+RAT, there is a better probability that this really is a hole, and since the estimate of factors in the gap comes from the SERIES detection, since this hasn't trigged in the second case, it almost definitely means a lower number of factors will be declared.

I've also just noticed that the "gap" between the two gaps is only 25G. If there are less that 30 factors in this 25G range, then in fact the size of the first gap will distort the estimate of the second gap. If you submit factors for the first gap, I would guess that this will change the estimate of the second gap.

But to be honest, this gap finding it's not an exact science, and I think I've learned quite a lot since I originally wrote, so when I get time I'll have a go at improving the detection and estimation algorithms.

Cheers,
Mike.

[Keroberts1]

I don't know why I decided ot give it a try but i started sieveing from 1 billion to 2 billion just to see how my P4 performed (horrible as expected) but i also discovered an interesting anomaly. I submitted the first 6 factors it found and it said 3 of them were new. This is very weird since i thought this range was sieved a long time ago. If these are real new factors then this means tht the old program used ot factor these numbers was missing many factors. If not then that means many many false factors are being produced. they were all verified though. I'm going ot finish the range and submit all of the factors if someone with access to the information could look them over and lemme know if this is just an anomaly in the new program or if these really are missed factors from the original range.

[Keroberts1]

the factors were
1000186877 | 55459*2^6790366+1
1000455791 | 55459*2^6353590+1
1000931203 | 22699*2^10251478+1
1001422771 | 55459*2^18342478+1
1001707669 | 22699*2^8018542+1
1001956961 | 55459*2^7158550+1

[Keroberts1]

ok this is generating way to many factors to enter them all so I'm gonna stop at
1079729251 | 55459*2^4631734+1
if it turns out these are real factors that have been missed before and we need to resieve the earlier range then I'd like to reserve the first 500 now.
thanks
someone please reply to this soon.

[Mystwalker]

Which version of SobSieve did you use? The 1.31 (or was it 1.30?) produced quite a lot of "excluded" factors. I'm not totally aware what that means, but these factors are not relevant for SoB - although they get recognized as valid.

[Mystwalker]

@MikeH:

I found a strange error in your scores file. According to it, I have only 100G not declared [complete]. But it's 2 100G ranges:

21000-21100 Mystwalker
22950-23050 Mystwalker

:confused:

[MikeH]

someone please reply to this soon. I assume you are using SobSieve 1.32 or 1.33?

I which case, I think you are confirming the problem that the scoring is indicating - that there is a small problem with these clients in generating factors that are not in the sob.dat file. Make a quick note of your various stats (http://www.aooq73.dsl.pipex.com/scores.txt), then take a look tomorrow to see what has increased. You can also see exactly what has been excluded from the link from here (http://www.aooq73.dsl.pipex.com).

I think you'll see that just about everyone who is submitting factors are getting excludes. Prior to these latest clients, the only people to have generated excludes were Nuri and myself, and that was because of a duff sob.dat file that only he and I used for a short period. All the others are new.


if it turns out these are real factors that have been missed before and we need to re-sieve the earlier range then I'd like to reserve the first 500 now. This is a little premature. I suggest we analyse the data tomorrow before embarking on any re-sieving effort. I think these will turn out to be factors which were elliminated with p<1G.

Mike.

[MikeH]

I found a strange error in your scores file. According to it, I have only 100G not declared [complete]. But it's 2 100G ranges: The allocated ranges bit of the scores rely upon me copying the contents of the sieving thread to a text file - I haven't managed to automate this bit yet. I try to update it every few days, but you may find this numbers of days out of date sometimes. Sorry. ;)

[Keroberts1]

I was using 1.33 and i sure od hope that these aren't real factors but there sure were alot of them nearly 80% of the factors i found were verified and then saved to data base as new.

[Mystwalker]

The allocated ranges bit of the scores rely upon me copying the contents of the sieving thread to a text file - I haven't managed to automate this bit yet. I try to update it every few days, but you may find this numbers of days out of date sometimes. Sorry.

No problem, just thought this is done by a (malfunctioning) script. :cool:

[paul.jobling]

Hi all,

I found the problem that was cuasing the extra factors to be found. It has been fixed in the attached release. I strongly recommend that you up grade to this version!

Regards,

Paul.

[expinete]

What happens if an invalid factor is submitted? Does the script verify if the factor are real factors?

[Joe O]

Originally posted by expinete
What happens if an invalid factor is submitted? Does the script verify if the factor are real factors?
These factors are not "invalid", they are excluded because they are outside the range of the sieving effort, i.e. they were already known and excluded from the SoB.dat file(s). The script does verify that the values submitted are really factors before including them in the data base. AFAIK the only problem the excluded factors cause is wasted effort.

[MikeH]

the factors were
1000186877 | 55459*2^6790366+1
1000455791 | 55459*2^6353590+1
1000931203 | 22699*2^10251478+1
1001422771 | 55459*2^18342478+1
1001707669 | 22699*2^8018542+1
1001956961 | 55459*2^7158550+1

These three

1000186877 | 55459*2^6790366+1
1000455791 | 55459*2^6353590+1
1001956961 | 55459*2^7158550+1

have factors less than 1G.

These three

1000931203 | 22699*2^10251478+1
1001422771 | 55459*2^18342478+1
1001707669 | 22699*2^8018542+1

were submitted by Louie some time ago when we sieve the 1G range.

Thus, as antisipated, no new factors, no candidates removed.

[MikeH]

I found the problem that was cuasing the extra factors to be found. It has been fixed in the attached release. I strongly recommend that you up grade to this version! Many thanks Paul. Do you have the console version?

Cheers,
Mike.

[paul.jobling]

Originally posted by MikeH
Many thanks Paul. Do you have the console version?

Cheers,
Mike.

Ah, I forgot it. Here it is.

Regards,

Paul.

[paul.jobling]

To explain the problem: I had some dodgy code that meant that the various k values were sharing the same bitmap in different ways. This meant that for a given k value, the bitmap would contain the n values remaining for that k as well as for other ks. Fortunately this means that all of the real factors in the range were found, but there were occasional reports of a factor being found when in fact the n was for a different k.

An upgrade is strongly recommended because there is a miniscule chance that a factor won't be found. This can only occur if the n value for a k is removed by the detection of a factor for a different k for that n value, on the same run of SoBSieve, when the actual factor for that n is a p value that is also tested in that run but later on. These chances are very very slight (so I hesitate to even mention it), but they do exist. I seriously doubt that any factors have been missed, but the possibility exists.

[Joe O]

Have you determined if indeed the client can go to p = 2^60 and eased the restriction?


ps
Congratulations on finding a prime. What is its current rank, 134?

[paul.jobling]

Originally posted by Joe O
Have you determined if indeed the client can go to p = 2^60 and eased the restriction?

That is the next thing that I am going to do. But I wanted to get this fixed version out ASAP first.


ps
Congratulations on finding a prime. What is its current rank, 134?

Thank you! As I recall, 3*2^414840-1's rank was 134 when it was added, and I don't think any larger ones were added at the same time. The real thanks should go to Jean Penne for writing LLR, and Paul Underwood for organising the 3*2^n-1 search and practically forcing me to test a range (I sent him an updated NewPGen for his sieving, using some of the ideas that came out of the SoBSieve work, and he insisted that I should have a range to test :) ).

But hopefully it is about time for another hit from the Seventeen or Bust search... and it is guaranteed to be groundbreaking when it comes.

Regards,

Paul.

[Moo_the_cow]

quote:
__________________________________________________
An upgrade is strongly recommended because there is a miniscule chance that a factor won't be found.
__________________________________________________

About how small is that chance? 1 out of 5,000 factors?

[Joe O]

If I understand this correctly, there are at the moment only 183 k n pairs of values that would need to be retested.
For example 15775530631129 | 5359*2^13089790+1 was reported and excluded.
Only the expression 22699*2^13089790+1 might have had a factor missed. If this already has a reported factor, then there is nothing else to do. If this does not already have a reported factor then we could try to find a factor for it now, or just wait and see if a factor is found for it and factor it later if none is found.

[Keroberts1]

is there a linux version of the siever? if there is could someone post it I would like ot try it out on one of my systems

[jjjjL]

I have updated the sieve page to link to a site where NBeGon can be found. (Mystwalker has mirrored it while Phil's site is down).

http://www.seventeenorbust.com/sieve/

or direct link is http://mystwalker.de/sb/fatphil/orgmathssierpinski.html

[jjjjL]

BTW, hopefully we can link directly back to Phil's site sometime soon. i'll email him to get a timetable for when his site will be online again. i don't mind linking to his statements about the war... i just mind linking to them indefinately. ;)

so if you're on the forum Phil, just let us know at what point you plan to reopen your site to the world and then we can link back. something like "the day Bush calls an end to hostilities" or "the day a new Iraqi gov't is formed' or something just so we know. i never took the link down during the war since i thought it was creative how you were demonstrating (although i would have appreciated a heads up). but i also expected you to one day open your site back up when the war ended a few months ago. i'm all for protest, but i feel hurt when it turns from a calculated protest against an unjust war into an open-ended protests against America.

-Louie

PS - only Phil has permission to talk war here (since it relates to his sieve client). all other war related comments belong here (http://www.free-dc.org/forum/showthread.php?s=&threadid=3016&perpage=25&pagenumber=2).

[Joe O]

Setting alpha seems to be a hit or miss operation. There are a lot of local minima and maxima so a runge-kutta approach does not seem to work. Are there any counters that you can easily and efficiently produce/display that would give us a clue? Maybe the ratio of little steps to big steps?

Another thought: Do you have the "computation costs" of big steps and little steps? That would be very helpfull.

[paul.jobling]

Originally posted by Joe O
Setting alpha seems to be a hit or miss operation. There are a lot of local minima and maxima so a runge-kutta approach does not seem to work. Are there any counters that you can easily and efficiently produce/display that would give us a clue? Maybe the ratio of little steps to big steps?

Well, looking at the code I can see that I get two values: arange, and brange.

arange=sqrt (alpha*34 million);

arange is then rounded up to the nearest multiple of 15840.

brange=1+17million/arange


arange is used for the baby-steps loop; brange for the giant steps loop.

The rounding to a multiple of 15840 (which is a lot higher than I expected, actually) means that many values of alpha result in the same values of arange and brange being used.

Regards,

Paul.

[jjjjL]

is that rounding behavior only in the newest versions? because i could swear alpha had a noticable effect on performance when changing it by as little as 0.5 just a few versions back.

if i'm doing my math right, the behavior you describe would make all alpha 0.0-7.0 the same.

-Louie

[paul.jobling]

Originally posted by jjjjL
is that rounding behavior only in the newest versions? because i could swear alpha had a noticable effect on performance when changing it by as little as 0.5 just a few versions back.

if i'm doing my math right, the behavior you describe would make all alpha 0.0-7.0 the same.

-Louie

In a word, yes, this is comparatively new behaviour. The rounding has always been present, but with the current implementation - where each k value appears multiple times in the sieve - the effect is much more pronounced. The number used to be less than 1000 before, and I am surprised that it is so large now.

Regards,

Paul.

[Nuri]

Originally posted by jjjjL
if i'm doing my math right, the behavior you describe would make all alpha 0.0-7.0 the same.

If I'm not wrong, it should always round to 15840 (unless alpha is set to 16.7 or more, which AFAIK, is not possible).

Paul, sorry if it's a silly question, but is it possible (or may be "is it worth" is the right question) to increase that 9.99 alpha limit (or leave it as it is and increase 34 million)?

[paul.jobling]

Originally posted by Nuri

Paul, sorry if it's a silly question, but is it possible (or may be "is it worth" is the right question) to increase that 9.99 alpha limit (or leave it as it is and increase 34 million)?

It isn't a silly question... it is an easy change to make. If anybody wants to experiment, a version without the 9.99 restriction on alpha is attached.

The 34 million can't be changed - that is twice the range of n.

EDIT: I tried it out and performance was worse. I also found a minor bug - you can't stop and restart it without it crashing.

Regards,

Paul.

[Robert Gerbicz]

Speed up the general k sieve algorithm:
The big trick:

If order(2,p) is divisible by D, where D is an integer then there is only one c(k)
mod D for every remaining k value for that if k*2^n+1 is divisible by p then
n==c(k) mod D.

Proof:suppose there exists n1<n2 for that k*2^n1+1 and k*2^n2+1 is
divisible by p and n1 isn't equal to n2 mod D. k*2^n1+1==k*2^n2+1 mod p
so 2^(n2-n1)==1 mod p (we supposed that p<>k so gcd(p,k)=1) it means
that n2-n1 is divisible by order(2,p).But order(2,p) is divisible by D and (n2-n1)
is not divisible by D.It is a contradiction.

We will use the previous trick with baby step-big step method!!! for every prime
power divisors of D, then use Chinese Remainder Theorem to get for every
remaining k the required c(k) value.( we'll use a faster method to power
calculating).

Fast power calculating method (similar than MKLASSON proposed on the 10 th
page but our method is faster):I'll call this "binary tree" algorithm:
Suppose that p-1 is divisible by q(1)^b(1)*q(2)^b(2)*...*q(s)^b(s) where
q(1)<q(2)<...<q(s) are small prime numbers ( b(i) are positive integers )
we know that p-1 is even but we will use this fact only if p-1 is divisible by 4
(so if p==3 mod 4 then we won't use 2 as a factor).
Let T(i)=q(i)^b(i) for i=1,2,...,s.
Suppose that we need the x^((p-1)/T(j)) mod p value (here 1=<j=<s):
Calculate x^((p-1)/T(1)/T(2)/.../T(s)) mod p (if it hasn't been calculated before)
and store this in a table.
In general suppose that we have calculated G=x^((p-1)/T(a)/T(a+1)/.../T(b))
mod p (here a=<j=<b is true)

case g1:
If j=<round((a+b)/2) then calculate H=x^((p-1)/T(a)/.../T(round((a+b)/2)))
mod p (if it hasn't been calculated before) is easy bacause it is
H=G^(T(1+round((a+b)/2))*T(2+round((a+b)/2))*...*T(b)) mod p and store
this value in a table.
case g2:
If j>round((a+b)/2) then calculate
H=x^((p-1)/T(1+round((a+b)/2))/T(2+round((a+b)/2))/.../T(b)) mod p
(if it hasn't been calculated before) is easy:
H=G^(T(a)*T(a+1)*...*T(round((a+b)/2))) mod p and store this in a table.

If we iterate the loop we'll get in the last step x^((p-1)/T(j)) mod p.

Table[deleted remainder classes]:
In the beginning of the algorithm we can make a (small) table. For every
remaining k values (now there are 12): for every small prime power
determine which remainder classes have already been deleted. So Table_k
contains {q^b,e} pair if k*2^n+1 is composite for every n==e mod q^b value
.(I think that prime powers up to 300 is enough).

Calculating e(k) values: (see the pseudo code step 3. for what values have
already been calculated).

Suppose that (p-1) is divisible by q^b (where q is a prime number and b is a
positive integer, but if q=2 then b>1).
Suppose that 2^((p-1)/q^0),...,2^((p-1)/q^w) are all congurent with 1 mod p
(the first is always true because 2^(p-1)==1 mod p (Fermat's little theorem))
and the remaining powers (if they exist, so if w<>b): 2^((p-1)/q^(w+1)),...,
2^((p-1)/q^b) are incongurent with 1 mod p.It means that order(2,p) is
divisible by q^(b-w).
If w>0 then for every remaining k value do:
suppose that k*2^n+1 is divisible by p so
k*2^n==-1 mod p
(-k)*2^n==1 mod p raise it up to (p-1)/q^w th degree we get:
(-k)^((p-1)/q^w)*2^(n*(p-1)/q^w)==(-k)^((p-1)/q^w)==1 mod p.
In step 3. of the pseudo code we have calculated H_k_0=(-k)^((p-1)/q^b)
mod p so we can easily get H_k_1=(-k)^((p-1)/q^(b-1)) mod p=H_K_0^q
mod p and so on
H_k_(b-w)=(-k)^((p-1)/q^w) mod p=H_k_(b-w-1)^q mod p.
So it means that if H_k_(b-w) is not 1 then we can discard that k value.
If w<b then order(2,p) is divisible by q (order(2,p) is divisible by q^(b-w)) then:
Calculate H_k_1=(-k)^((p-1)/q^(b-1)) mod p=H_k_0^q mod p if it hasn't
been calculated before and store this,...,and so on
H_k_(b-w-1)=(-k)^((p-1)/q^(1+w))
mod p==H_k_(b-w-2)^q mod p if it hasn't been calculated before and store
this. For every remaining k value we'll determine in this case that if
k*2^n+1 is divisible by p then n==e(k) mod q^(b-w). Let z=b-w>0. Let
D=D*q^z.
We use induction to determine these e(k) values:
Suppose that we know:STEP[j] (for some 0=<j<z)
n==f(j-1,k)*q^(j-1)+...+f(0,k)*q^0 mod q^j
so we know: f(j-1,k),...,f(0,k) values for every remaining k value.(0=<f(i)<q).
we can suppose that:
n=u*q^(j+1)+f(j,k)*q^j+f(j-1,k)*q^(j-1)+...+f(0,k)*q^0 (u is an integer)
and we want to know the f(j,k) value (0=<f(j,k)<q) for every remaining k.
So if k*2^n+1 is divisible by p then we can write that
(-k)*2^(u*q^(j+1)+f(j,k)*q^j+f(j-1,k)*q^(j-1)+...+f(0,k)*q^0)==1 mod p
raise it up to (p-1)/q^(j+1+w)-th degree (remark: j+1+w=<z+w=b so (p-1) is
divisible by q^(j+1+w)) we get the following equation(1):
(-k)^((p-1)/q^(j+1+w))*2^((p-1)/q^(j+1+w)*(f(j-1,k)*q^(j-1)+...+f(0,k)*q^0))*
*2^(f(j,k)*(p-1)/q^(1+w))==1 mod p (we have used that
2^((p-1)/q^w)==1 mod p).We know
A(k)=(-k)^((p-1)/q^(j+1+w)) mod p=H_k_(b-j-1-w). We have already
calculated 2^((p-1)/q^(j+1+w) mod p in step 3 of the pseudo code. It is
easy to determine 2^((p-1)/q^(j+1+w)*(f(j-1,k)*q^(j-1)+...+f(0,k)*q^0))
mod p because we know from induction:
f(j-1,k)*q^(j-1)+...+f(0,k)*q^0 and from pseudo code the
G=2^((p-1)/q^(j+1+w)) mod p ,so raise it up to
f(j-1,k)*q^(j-1)+...+f(0,k)*q^0 th degree and we get
B(k)=G^(f(j-1,k)*q^(j-1)+...+f(0,k)*q^0)) mod p.
Let L(k)==A(k)*B(k) mod p.We know also from pseudo code:
M=2^((p-1)/q^(1+w)) mod p
So in equation(1) we can write that:
L(k)*2^(f(j,k)*(p-1)/q^(1+w))==1 mod p so
for every remaining k value equation(2):
L(k)*M^f(j,k)==1 mod p (here 0=<f(j,k)<q)
We know for every k value the L(k). And we are searching the f(j,k) values
(it is depending on k).So the previous equation is a simultan k value
problem,which can be solve by the general baby step-big step method
(don't forget that 0=<f(j,k)<q is true).If you want to understand than it is
important to remark that L(k) depends on k and STEP[j].But
M=2^((p-1)/q^(1+w)) mod p is constant in every STEP[j].So it is only
need to calculate the multiplicative inverse of M mod p once time for the
big step-baby step method.This can be calculated easy:
2^((p-1)/q^(1+w)*(q^(1+w)-1)) mod p=M^(q^(1+w)-1) mod p
(because their product is 2^(p-1)==1 mod p).
So it is only need to calculate once the RHS in the baby step-big step
algorithm but the LHS has to be calculated for every STEP[j].
In the STEP[j] we'll get for every remaining k value:if k*2^n+1 is divisible
by p then n==f(j,k)*q^j+...+f(0,k)*q^0 mod q^(j+1).We can discard that k
value if this remainder class has been deleted:so if it is in the
Table[deleted remainder classes].
It is also important to remark that there is only one solution for f(j,k),
because if there are 0=<f1<f2<q solutions then M^(f2-f1)==1 mod p so
2^((p-1)/q^(1+w)*(f2-f1)) mod p is 1 so order(2,p) divides
(p-1)/q^(1+w)*(f2-f1).It means that q^(1+w)*order(2,p) divides (p-1)*(f2-f1)
but order(2,p) is divisible by q^(b-w) so q^(b+1) divides (p-1)*(f2-f1) but
0<f2-f1<q and (p-1) isn't divisible by q^(b+1).It is a contradiction.
(it is similar than the big trick).
In STEP[z-1] we'll know for every k the remainder of n mod q^z what we
needed.(z is b-w)
(It is possible that 0<w<b.)

The (whole) algorithm in pseudo code:(do only once time step 0., don't after every
p prime).

0. Create Table[deleted remainder classes].

For p prime number do:

1. For every remaining k value make a fast Kronecker test.

2. Factorise p-1 a little: (p-1) is divisible by q(1)^b(1)*q(2)^b(2)*...*q(s)^b(s),
where q(1)<q(2)<...<q(s) are small prime numbers b(1),...,b(s)>0 are integers.
(if q(1)=2 then b(1)>1). Let D=1. If there are no small prime divisors then
go to the step 4.

3. for m=1 to s do: calculate U(m,0)=2^((p-1)/q(m)^b(m)) mod p (store this value)
by "binary tree" method.
for every remaining k value calculate also by "binary tree" method
H_k_0=(-k)^((p-1)/q(m)^b(m)) mod p and store this.
for h=1 to b(m)-1 do:calculating 2^((p-1)/q(m)^(b(m)-h)) mod p is easy
because this is U(m,h)=U(m,h-1)^q(m) mod p (store this value)
next h (if b(m) is 1 then this is zero cycle)
use "Calculating e(k) values" method for q=q(m) and b=b(m)
next m

4. By Chinese Remainder Theorem we can get for every remaining k value that if
k*2^n+1 is divisible by p then n==c(k) mod D.
In general for every remaining k value there are only few possibilities for n mod
48. So let new_D=smallest common multiple of D and 48.(this is D*48/gcd(D,48)
,let D=new_D)
So for every remaining k value there are only few possibilities for n mod D.
(these can be calculated also by Chinese Remainder Theorem).

5. Do the general big step-baby step method.

I think that we can use for example 997 as a factor of (p-1) (if 997 divides it) in
pseudo code step 3. Because computing the required baby step-big step
method isn't requiring much time and we'll know the remainders of n mod 997 for
every remaining k value.

For step 4.:possible speeding up of this step:
We may reusing calculated values if we are using higher powers.(higher D values).
(as in the original algorithm).

Robert Gerbicz

[jjjjL]

hi Robert. welcome to the discussion. :)

i'm still digesting what you've suggested. i'm sure paul will have something to say about it when he reads it. anyone else think he's onto something?

mklasson - have you done this with your siever? is the math good and does it yield an improvement?

-Louie

[mklasson]

Originally posted by jjjjL
mklasson - have you done this with your siever? is the math good and does it yield an improvement?

I haven't really taken the time to try to get my head around everything Robert wrote, much less implemented it. It was quite a load. :) I'll try to get around to it soon.

Anyhow, welcome Robert,
Mikael

[jjjjL]

i optimized the factor database today. factor submission should be noticably faster now. let me know.

-Louie

[Keroberts1]

Yup Yup Yup much better, :cheers:

[Mystwalker]

Definitely much faster. :)

[paul.jobling]

Originally posted by jjjjL
hi Robert. welcome to the discussion. :)

i'm still digesting what you've suggested. i'm sure paul will have something to say about it when he reads it. anyone else think he's onto something?

mklasson - have you done this with your siever? is the math good and does it yield an improvement?

-Louie

Louie et al,

I am on a well-deserved holiday travelling around Spain right now, and my only chance to hit the internet is today while we are in Grenada and Karen is "shopping for shoes" :)

I saw Robert's ideas here and also in an email he sent to me... I haven't had time to look at them in detail (in an internet cafe time really is money) but I will definitely look closely at them when I get home in a weeks time.

BTW, are there any programmers from Spain here? How do you cope with the square brackets and vertical bar (|) being so difficult to find?

Regards,

Paul.

[expinete]

Hi Paul, you can get the |, [ and ] with the Alt GR key

Alt GR + 1 = |
And the two keys at the left of the key P with the ALT gr give you the brackets.

It isn't difficult iif you have worked with a Spanish keyboard all of your live ;)

Enjoy your holydays!

[Mystwalker]

And the two keys at the left of the key P with the ALT gr give you the brackets.

That sounds like the normal US layout, doesn't it?

Btw. if you come to Germany, [ and ] are Alt Gr + 8 resp. 9, | is Alt Gr + <>-key. ;)

[Joe O]

Originally posted by jjjjL
i optimized the factor database today. factor submission should be noticably faster now. let me know.

-Louie

Much, much faster!

Anywhere from 40x to 100x faster!

That's 4000% to 10000% faster for those of you who like %.

[b2uc]

When a K is found/completed whatever...are the .dat files quickly changed to exclude the K that is no longer needed and thus keep us from spending time finding factors for that K?

In other words...is it such a good idea to reserve a month or so of work when a K could be found at any time? Or is it not that much more work for the client to scan 12 instead of 11K's? Would we get like an 8% boost if we just did a day or twos work at one time and then changed the .dat when a K is found? I know a lot of people may point out that it's a long time inbetween finding K's...but I'm an optimist:)

Talk real slow on your explanation...I run cat5e for a living...not program in asm and I don't think I've ever read books that start out... "The world around in you: Explained in number theory"

[Mystwalker]

That is no problem. All you have to do is changing the leading 12 to 11 and erasing the list of n's assigned to the found k. As these are sorted by k, this is done within a minute. If you find a prime, I'll show you. :jester:

[b2uc]

Question: I'm sieving 32300 to 32350 and on of my factors found is 21181*2^3392204+1 Now this number is less than 4Mil...has this number already been previously sieved and probably already prp'd? Will numbers less than 4 million just be thrown away by the script..or is this a new find all together?

[mklasson]

Originally posted by b2uc
Question: I'm sieving 32300 to 32350 and on of my factors found is 21181*2^3392204+1 Now this number is less than 4Mil...has this number already been previously sieved and probably already prp'd? Will numbers less than 4 million just be thrown away by the script..or is this a new find all together?
If it's the first known factor for a k,n pair it can always be used to eliminate the need for a double check prp.

Mikael

[Keroberts1]

would it be possible just out of curiosity sake to sive just for one K value by delewting all of the data for the other values?

[ceselb]

yes, that's exactly what will be done when we find the primes.

[paul.jobling]

Hi,

Attached is a 1.34 release of SoBSieve. This is almost identical to the 1.33 release - it does a couple of things in a different order to help the Sieving Server development effort, but apart from that the performance is the same as before.

Regards,

Paul.

[Mystwalker]

Thanks a lot, paul! :cheers:

But one question: We already had version 1.34, didn't we?

[paul.jobling]

Originally posted by Mystwalker
Thanks a lot, paul! :cheers:

But one question: We already had version 1.34, didn't we?

Did we? I thought the last release was 1.33 - though I might have put a 1.34 up for a while then withdrawn it...

Anyhow, if it doesn't cause a problem I won't rerelease. BTW, does it work as required now? I look forward to distributed sieving.

Regards,

Paul.

[jmblazek]

Originally posted by paul.jobling
Did we? I thought the last release was 1.33 - though I might have put a 1.34 up for a while then withdrawn it...

Anyhow, if it doesn't cause a problem I won't rerelease. BTW, does it work as required now? I look forward to distributed sieving.

Regards,

Paul.

I started sieving 3 weeks ago and I've only used the 1.34 version. I downloaded it from MikeH's "All Things SoB Sieving" website:

http://www.aooq73.dsl.pipex.com/

It was the recommended client to use for dual range sieving. Is it the same??? or do I need to download the rerelease???

John

[Joe O]

John,
Your 1.34 is OK. Paul released and pulled a 1.35
Paul,
Welcome back from vacation/holiday.

[Joe O]

Originally posted by paul.jobling
Hi all,

I found the problem that was cuasing the extra factors to be found. It has been fixed in the attached release. I strongly recommend that you up grade to this version!

Regards,

Paul.

Paul, I do hope that you based this new 1.34 on the old 1.34 not on the 1.33.

[Joe O]

Paul, could you enlighten us about this?

[paul.jobling]

Ok guys,

It look like I forgot about a 1.34 release somewhere along the way. This is the latest code though, so there shouldn't be any problems with it. Sorry about that! I can make a release with a 1.35 label if you are desperate for it?

Paul.

[Mystwalker]

I can make a release with a 1.35 label if you are desperate for it?

It would make the requirements list easier if there's only one new client with that version. ;)


BTW, does it work as required now? I look forward to distributed sieving.

Honestly speaking, I haven't tested it myself. But my fellow student didn't comment, so I think it is working. Testing today was quite good. :thumbs:


Other question:
supersecret is approaching n=300k. When do we plan to raise the lower limit of DC and dual sieving?

[paul.jobling]

OK, here is one branded 1.35 for y'all.

[Keroberts1]

how many N values that are in the current dat file have already been removed? it appears to me that this should be a rather largr number since this dat includes values that were between 3-4 million. I understand cutting the range has been talked about before but there are also a lot of values that have already been removed by sieving and these values don't need a double check so why do we still check the mwith the sieve. Could we speed up the siever with a new updated dat file?

[Keroberts1]

If someone with a little bit more knowhow than me could offer some input on this i would really like ot hear it perhaps by using an automatically upadting dat file we could build a siever that would constantly increase speed as the project continues This would allow the siever to obviously achieve much greater speeds as time progresses perhaps extendeding greatly the life of productive sieving.

[mklasson]

keroberts1:
the siever basically has to process every n value between the lowest you want it to find and the highest, i.e. between 3M and 20M currently. It doesn't matter how many k,n pairs there actually are in that range. This isn't _really_ true, but it's more so than not. :) If you get down to very few remaining pairs, there's a chance they all fall in the same residue classes modulo larger values than what's currently used.

[jjjjL]

the idea that removing sieved out numbers would increase speed has been posted here before. paul has said that it doesn't help. phil confirmed that paul's conclusion was correct. they wrote the sieve so they should know.

some have claimed slight speed increases by clearing extra values out of the dat file. if someone convinced me that there were a true benefit to having an updated dat file, there would be an automated system to make new ones but i still don't believe it.

-Louie

[ceselb]

Well, SoBSieve might use a little less memory with less numbers to keep track of. The resulting reduction in swap use could make a slight speed increase.

Also, if you update the SoB.dat the p-1 factorer package (and updates) could be made smaller.

[mklasson]

Hmm... I just came across some sort of oddity. A few moments ago I found the factor
32560064474489 | 55459*2^7234354+1
with my own siever. I reported it at .../sieve and was told it was a new factor. Then I ran sobsieve on the same range and to my surprise it didn't find that factor. It turns out that 55459*2^7234354+1 isn't included in the sob.dat I was using (my program in its infinite wisdom didn't bother to check there... :) ).

How come? My factor was reported as new and there's no factor for that k,n pair in any of lowresults.txt and results.txt, so why wasn't 55459,7234354 in the sob.dat (dated Jan 30)?

EDIT: it just occurred to me that it might be because some p < 1G is a factor for that k,n... Is this the case?

[Joe O]

Originally posted by mklasson
EDIT: it just occurred to me that it might be because some p < 1G is a factor for that k,n... Is this the case?

If so, it will appear here (http://www.aooq73.dsl.pipex.com/FactorsInvalid.txt) tomorrow.

[Joe O]

Originally posted by jjjjL
some have claimed slight speed increases by clearing extra values out of the dat file.
-Louie
Well I'm one of those that reported a slight increase in performance, BUT it took a 22% decrease in the size of the file to get a 2% increase in performance.
I had neglected to change the sob.dat file on one of my lower n range machines. I was still using the original file. I replaced it with an updated file that was the last one before the change to 300K as a lower bound just to try it.
That's the story, folks.

It hardly seems worth it for all the work Louie would have to do.

[Keroberts1]

ok well thanks for getting back ot me at least maybe once we have removed more than half of the range then we can trim it and get a signifigant increase in speed

[Moo_the_cow]

Has anyone managed to figure out and implement Robert's idea to speed up the sieve client yet? I'm not a math wizard, so I was unable to do so :(

[paul.jobling]

Originally posted by Moo_the_cow
Has anyone managed to figure out and implement Robert's idea to speed up the sieve client yet? I'm not a math wizard, so I was unable to do so :(

Ah, well I read it, and the problem with implementing it - as with any "order of 2" idea - is that there is no fast way to find the order of 2 mod p. The only way it can be done is to completely factor p-1, and that is slow. A partial factorisation can be obtained (finding the prime divisors <100000, say), but the information that it provides on the order of 2 would be so weak as to make the test essentially useless.

However, all ideas are gratefully received, and Robert's contribution was welcome. Please keep any ideas you have coming!

Regards,

Paul.

[paul.jobling]

Hi,

I have got a Linux version of SoBSieve... does somebody want to test it for me? If so, PM me with your email address.

Regards,

Paul.

[b2uc]

Question: If I'm doing a week or so of seiving and I notice a factor around the 3.9mil to 4.1 mil range...or if I'm not sure when exactly I'll finish my range and I see these low factors...should I just cut and paste the few of them to /sieve/ before the proth test suddenly catch up to them? Like yesterday outta like 30+ I sent in at the completion of a test...some were as low as 3.8m and it took them just fine as I presume new factors.


Also.

Question 2: Can you alter the Linux cliet just a tad so it will run optimal on FreeBSD? If I can run it on FreeBSD I can put forth a lot more effort. No Linux here.:whip:

[Robert Gerbicz]

After I read Paul Jobling's (last but one) posted mail I have re-read my first posted mail
with an algorithm to this forum. Unfortunately I haven't written down a main
thing.

In the fifth step of the pseudo code I have written only that:

5. Do the general big step-baby step method.

Yes it is a big step-baby step method but not the original algorithm. We know for
every remaining k value that there are only few possibilities for n mod D. (see
fourth step: in the algorithm D>=48 ). And this fact reduce the required cost
dramatically. Because let c=Sum{for every remaining k value the number of
possibilties for n mod D}, then let n=nmin+a+b*arange if arange is divisible by D
then we know for every remaining k value the n mod D so we know also: a mod D.
If D is large then the cost of a baby step is equal to the cost of a big step. So
we can easily optimize the required cost: Let
baby step=D
arange=isqrt(D*(nmax-nmin)/c)\D*D+D (\ means integer division)
brange=isqrt(c*(nmax-nmin)/D)+1

The total cost is about 2*sqrt((nmax-nmin)*c/D) multiplications mod p in the 5-th
step of the pseudo code. And this is a small cost because if we are using the
original algorithm then we use for example D=48,because we are know that there
are only few possibilities for n mod 48 for every remaining k value.In our algorithm
D>=48 so our algorithm is faster in this step by about a factor of sqrt(D/48). ( If we
use D=48 then the baby step is a little faster then a big step because it is easier to
multiple a number by 2^48 mod p). The required cost in the previous steps won't be
much large if we are using the primes up to for example 1000 for the factorisation of
(p-1).

So we aren't use only the big trick to discard k values. We can
reduce the required multiplications mod p in the 5-th step of the
pseudo code. And if we aren't use many multiplications mod p in
the previous steps then the sieving method will be faster.

[Keroberts1]

If the size of the dat. file doesn't matter for the sieving speed (or only minorly) then parhaps we should add the values for the 20million + N ranges. After all we are progressing fast and though we won't be geting there any time soon it also appears that we won't be getting the last primes without getting there first. Maybe it'd be moreefficient to include those values now so we don't have ot repeat huge amounts of sieving.

[paul.jobling]

Originally posted by Keroberts1
If the size of the dat. file doesn't matter for the sieving speed (or only minorly) then parhaps we should add the values for the 20million + N ranges.

That would have to be a completely new sieving effort, rather than being added to the current data - we want to check them for divisiblity against the 'small' primes as well, after all.

Values up to 20 million will probably keep S0B busy enough for the forseeable future :D

Regards,

Paul.

[Keroberts1]

I've noticed that some of the factors that are removed from the dat by the siever are clumped together in some sort of a pattern. I was wondering if this could be used to in some way learn some thing new about these types of probabilitys. Perhaps some distinct patern could help us discover our own ways to speed up the algorithim. Just a thought I'm not even sure if the factors are indeed clumping I just noticed this i nmine and ithought it was unlikely ot happen.
58130163354677 | 55459*2^5984698+1
58130502895411 | 33661*2^5974872+1
58130637894977 | 28433*2^14473633+1
58133832667853 | 21181*2^9694100+1
58139256462389 | 24737*2^12631087+1
58139814210671 | 24737*2^19963543+1
58143005430539 | 5359*2^13435030+1
58143177309443 | 55459*2^18929614+1
58143725709331 | 4847*2^16345647+1
58152700125841 | 22699*2^5266198+1
58153361051249 | 67607*2^18849011+1
58130163354677 | 55459*2^5984698+1
58130502895411 | 33661*2^5974872+1
58130637894977 | 28433*2^14473633+1
58133832667853 | 21181*2^9694100+1
58139256462389 | 24737*2^12631087+1
58139814210671 | 24737*2^19963543+1
58143005430539 | 5359*2^13435030+1
58143177309443 | 55459*2^18929614+1
58143725709331 | 4847*2^16345647+1
58152700125841 | 22699*2^5266198+1
58153361051249 | 67607*2^18849011+1

[Moo_the_cow]

Keroberts, I noticed that too - whenever a big gap occurs between factors, around 3-4 factors are clumped together after that. I thought that it was just a strange coincidence, though.

[Keroberts1]

It wasn't just clusters following gaps I believe that there may be some consistancy to the pattern of the sizes of the gaps. Perhaps the sieve client may be able to intelligently skip some ranges. This may not be a good idea at the time since we can still remove factors at a fast enough pace so that it is very much worth while to keep sieving. However once factor density drops drastically in the upper ranges it may be better to risk missing some factors in exchange for the quick retrieval of a few. Its just speculation on my part I don't know nearly enough about computers or number theory to try to impliment any of this. It could be a real blesing for the project though.

[MikeH]

(Finally) new sieve/factor scoring.

First point. All factors submitted up to yesterday have been scored under the old system, and their scores have been frozen.

All new factors will be scored according to the new system.

A unique factor will score as follows:

p < 40T, score = p/1T (i.e. as before)
p > 40T, in 'active' window, 0 PRP tests performed, score = (n/1M ^ 2) * 125
p > 40T, in 'active' window, 1 PRP tests performed, score = (n/1M ^ 2) * 125 * 0.6
p > 40T, in 'active' window, 2 PRP tests performed, score = (n/1M ^ 2) * 125 * 0.2
p > 40T, outside 'active' window, score = (as duplicate, see below)

A duplicate factor will score as follows:

score = p/100T, capped at 35.

Excluded factors (those factors not present after sieving 100<n<20M to p=1G) do not score.


The following aspects of scoring have changed.

(1) A unique factor is the first factor found for a candidate (previously it was the lowest p).
(2) Scores for each unique factor are remembered. Scores can go up (as an 'active' window moves to cover a factor that was above the window), but cannot go down (as a factor moves out of a window).
(3) The 'active' windows are 0 < n < (<next double check candidate> + 200K) and (<next candidate>) < n < (<next candidate> + 500K). So currently that's about 0 < n < 590K and 4.150M < n < 4.65M.


The scoring has been changed to reflect the benefit of finding factors to the main SB project. Anyone that chooses to sieve will find that many of their factors do not fall into an 'active' window, and thus will score very low until the main SB project (thus the main window) moves forward. Since the main window is 500K wide, on average about 1 in 40 factors will immediately fall into it. Anyone that chooses to factor will score immediately for all their finds (provided they stay ahead of the window!). I think a good analogy is factoring equates to cash in the bank, while sieving generates some cash and a lot of stock options.

It's now up to everyone what they do. Right now I think sieving will continue to yield enough factors in the active windows for it to be better than factoring (and then there's all those stock options!?), but that's my gut feel, I haven't actually looked at it in any depth.

[Moo_the_cow]

Thanks Mike, now let's see who can be the first "millionaire":D

[Nuri]

Mike,

Congratulations on the new scoring system. :thumbs:

I think the score gained from finding factors for a candidate that is already PRP tested should be much less.

Would you consider changing 0 < n < (<next double check candidate> + 200K) to (<next double check candidate>) < n < (<next double check candidate> + 200K)?

Or alternatively, changing the 0.2 in p > 40T, in 'active' window, 2 PRP tests performed, score = (n/1M ^ 2) * 125 * 0.2 formula to a much lower value,

Or simply putting a cap at 35 would serve the same purpose as well.

What do you think?

[mklasson]

Nuri,
I like your cap idea. The issue is pretty moot until the double check limit reaches 1.2M though.

Mike,
looks like a fine scoring system, but one thing is unclear: what happens to a large factor for <double check limit>+200K < n < <next candidate> that scores 35 (the cap) until the double check limit rises and the factor's n value enters the lower active window, at which point the factor's score would decrease if it's allowed to change. Will it decrease?

Mikael

[MikeH]

Would you consider changing 0 < n < (<next double check candidate> + 200K) to (<next double check candidate> ) < n < (<next double check candidate> + 200K)?

Or alternatively, changing the 0.2 in p > 40T, in 'active' window, 2 PRP tests performed, score = (n/1M ^ 2) * 125 * 0.2 formula to a much lower value,

Or simply putting a cap at 35 would serve the same purpose as well.

Nuri, thanks for the comments. Your first suggestion was how I'd originally planned to do it, but then I thought it was worth rewarding a factor however small, because it is final. I guess I could reduce the 0.2, but I figured that the scores will be so small in any case that I don't want to push it down too much. A factor at n=4M no PRPs = 2000, a factor at n=300K, 2 PRPs = 2.25. Since the margin between the double check SB and main SB are likely to remain this big, do we really need to penalise more?

The cap sounds like the best idea. I'll have a think.


looks like a fine scoring system, but one thing is unclear: what happens to a large factor for <double check limit>+200K < n < <next candidate> that scores 35 (the cap) until the double check limit rises and the factor's n value enters the lower active window, at which point the factor's score would decrease if it's allowed to change. Will it decrease?

Mikael, again, thanks for the comments. Good point. Right now the score won't decrease, it will stay at 35. I feel that a different cap may be required, the current cap assumes that sieving could continue right up to 3500T, which is clearly crazzy :neener:

I think a more realistic (high) limit is 500T, which means a cap of 5 - but need to think about the application.

Mike

[Keroberts1]

What is th siever's limit? How large a value could i put in and still have it to the crunching? just wondering because I cn't test for myself until my range finishes and I currently have one that will be running until the end of summer

[MikeH]

Another score (http://www.aooq73.dsl.pipex.com/scores.htm) update - note the file extention has changed.

Now you can drill down on the details of your scores. This should make it a bit easier for sievers to follow what's happening (and what's going to happen) to their scores. You now get the following for all your unique factors.

largest scores
most recently changed scores
factors next to enter main active window
factors next to enter double check active window
most recent finds

Enjoy. ;)


P.S. I've also plugged a potential scoring flaw. Where a factor is to be scored as a 'duplicate', it will further be capped to what it would earn if it were unique.

[MikeH]

What is th siever's limit? How large a value could i put in and still have it to the crunching? just wondering because I cn't test for myself until my range finishes and I currently have one that will be running until the end of summer If you mean how many factors can you submit in one go on the web form, the answer is many hundreds. You shold be OK even leaving it running over the summer.

[Nuri]

Mike, nice job again. It's now much easier to understand what's going on with the scoring.

Just a little request:

Would you consider adding a new column ("old score") to the user scoring details that will show the old score for the factor as well?

Of course, this column will be empty (like the "Date score changed" column) if the score has not changed yet (or, the option is not still "in the money" :D).


EDIT: And a second request:

Could you please limit the k/n pairs that show up in the "Factors next to enter (main) 'active window' " and " Factors next to enter (double check) 'active window' " portions of the detailed stats to those that have factors p>40T. The way it is now, it might create wrong expectations.

[Nuri]

Originally posted by Keroberts1
What is th siever's limit? How large a value could i put in and still have it to the crunching? just wondering because I cn't test for myself until my range finishes and I currently have one that will be running until the end of summer

Or, if you mean how large a p value you can enter, there are two answers:

1- The limit of p value that the client will be able to reach is much higher than we would need to sieve. Louie once (http://www.free-dc.org/forum/showthread.php?s=&threadid=2424) wrote that it should be something like 1,152,921,504,606,846,976 (or 2^60, or 1152921T).

2- However, since the last couple of months (or you might prefer to recall it client upgrades), it is limited to 2^48 (or 281,474,976,710,656, or 281.4T). The siever will stop itself exactly at that number if you are trying to reach there from a lower number, or it will stop immediately if you try to start feom a higher number.

I think this is a precaution taken to enable us focus our computing effort to the ranges wher we can find much more factors per given time. I'm sure it will be increased in case we reach numbers that high.

BTW, you can test the limit yourself too. Simply create a new folder, copy your SoBsieve.exe and SoB.dat files to it, and start the client there. You will see that it will not run in case you write 281475 (or something higher) for the "Sieve from p =" cell.

And of course, if you will be running two clinets at the same time, your sieve speed will reduce by 50% :D.

[Keroberts1]

I'm quite confident we'll pass that limit before sieving become not qorth our time

[Keroberts1]

however if someone wnts to ready a dat file for 20-40 million then perhaps at that point we should add those numbers so we can presieve them too since it won't take much more processor power to add them in too adn only then might those ranges be more qwort hwhile sieving.

[Nuri]

I think it would be too early to worry about sieving n values above 20 million before the main project reaches testing numbers as large as 15 million (or may be even larger numbers - 18 million?). It's highly likely that we have at least a couple of years before we reach there.

Also, hopefully a couple of primes will be found before we reach 20 million. So, if we start sieving values larger than 20 million today, a significant portion of that sieving effort will be pointless (since we will not need the information for these k values anymore).

[MikeH]

Would you consider adding a new column ("old score") to the user scoring details that will show the old score for the factor as well? It is done (you'll see it in the next stats run), I've also added a "will be" score, but don't get too excited about the 50000 for those n~20M;)


Could you please limit the k/n pairs that show up in the "Factors next to enter (main) 'active window' " and " Factors next to enter (double check) 'active window' " portions of the detailed stats to those that have factors p>40T. The way it is now, it might create wrong expectations. Ah, that wasn't suposed to be that way. That will need to wait until tomorrow for a fix now.

[MikeH]

Could you please limit the k/n pairs that show up in the "Factors next to enter (main) 'active window' " and " Factors next to enter (double check) 'active window' " portions of the detailed stats to those that have factors p>40T. The way it is now, it might create wrong expectations. OK, that's fixed - now only scores that will change are displayed in these sections. Again, this won't be seen until the next update.

Next task is to get this thing updating 4x each day instead of once.

[Keroberts1]

It may not be that long after all when we reach 20 million, only perhaps 2-3 years if computers get a small increase in speed and if our member ship increases slightly(finding another prime?). Also Ithought it was a fact that having more N values being sieved at once didn't slow the speed of the client. At least that was why i didn't think trimming the ranges would help?

[Moo_the_cow]

2-3 years is more than enough time needed to sieve ranges n>20M, and in order for there to be only 2-3 years left, we would need to discover at least 6 primes and have our computing power triple.

When we reach n=10M or so, then we should trim our sieve ranges.

[b2uc]

Question:

How come my sieve scores page: http://www.aooq73.dsl.pipex.com/ui/3962.htm Doesn't have all the cool stuff like most peoples? All I have is High Scores and Most Recent Finds....nothing else.

[Mystwalker]

Hm, aren't there some posts missing?

Anyway, here my question again:

"Did you submit factors recently?"

I think now mklasson said that the factors have to be over 40T and MikeH acknowledges that your factors are in the range of 3xT. :crazy:

[mklasson]

and are they >40T? I think they're the only ones subject to the new cool stuff.

;)
Mikael