vjs
12-21-2004, 11:58 AM
O.K. here is a direct copy paste from the creator of the new sieve program himself.
b2 wrote:
vjs wrote:
Couple question,
Will we still use a dat file...
Have you tested it against previous sieve efforts....
Joe_O and myself have sieved several 100G worth of large n upto 100m, I could send you the factors/dat's for comparision/testing purposes...
I'd also like to test this client against high n and large ranges of n eventually.
I believe Chuck and I identified problems in the sieve code that only pertain to our project. Some code after an if riesel statement leave doubt to whether our sieve can accurately handle n>20million very well at this moment.
I'll defer to Chuck to explain this issue. I believe Chuck may have already taken care of the problem in the future sieve.
From Chuck....
Ok.. guess it's my turn to fill you all in since I've been so quiet.....
B2 is correct in that we cannot guarantee... specifically, if i may rephrase, have a very low confidence, of the current version's ability to go above 22M... and definately know that above 24M, there is almost zero confidence. I have factors which are legitimate, but the program ignored / discarded. If it DOES produce any... most are good... but no guarantees.
I can share the math... but the problem lies with the numbers 1<<25, 1<<22, 1<<19, and 1<<13. these do not work properlly when there are more than 20 K values.... Nor will it work at all above P > 2^50.
It will appear to work, but it is waisting time... part of the software is making a very honest effort to produce a real factor (and does).... only to be discarded or incorrectly 'reassembled' before printing out. This is because it detects a 2^25th partial factor and discards the entire factor. This is incorrect logic. the factor should be reduced to the lowest set of primes FIRST, recalculated in terms of K.2^N +/- 1... and THEN the test if N > 25.....
The reverse method (which I use), is to ensure the final N<25 during the factoring / reduction / reconstruction process...
Hope that makes sense.. it is difficult to describe multiple 32 and 64 bit words that you 'slide' above and below each other.... (in a stack) until they cancel out... (the cross cancelling is the key)..
The existing bitmap is basically flawed due to coding errors and, mostly, hardware changes. It was originally designed for SOB, and this is obvious in the # of bits used as boundary conditions. It was also designed for fewer than 20 'K' values.
This is all very very evident if you were to do the following....
1) sieve 1G -> 24T, 24->48T, 48->76.8T, 76.8->96T, and finally 96T -> 112T.... The sieve will collapse at 112T. You will see speed slowdowns at each marker. These correspond to the bit positions 2^45, 2^46, 2^47, 2^48, 2^49.
or
2) sieve any range 2 -> 20M....record the results. clear the files. (startfresh).. and run 20-40M... you will notice 4000days of work vs 1 hr of work. Then do it again (full reset) at 40-60M.
I am not criticising the design, coding or anything........PLEASE don't get me wrong... it was adapted from +1 to -1, it is a 3000+ line of code highly complex work.... The translation was a non-trivial task. I am pleased how much works as well as it does. It is quite remarkable. It was created before 64 bits was "Native"... now 64 bit math is 'normal'.
In the new sieve, none of this is a problem because 2^50 is not a limit , nor is 2^25 within the sieve.... The only limits are:
a) Nmin -> Nmax factor values are searched (2^2 -> 2^64) fast mode.
aa) Nmax > 2^64 is a bit slower.
b) Nmax < 2^25 (an LLR limit for now).... so even putting 20M <=N <= 40M would gain nothing...
..... UNLESS it can refactor it.... Otherwise it would chop at 2^25 (32meg) if it cannot find a way to reduce N to within the LLR limit and then you are subject to the possibility of a 'duplicate' or 'out of range'.
Essentiallly... after I complete the repairs to the existing sieve, which take priority, I will finish the new sieve.
This will allow us to maintain a complete verification database of factors output.
Repairs / bug fixes are currently prioritized as:
1) bitmap
2) ranging (Scanning N, and Output 2^N)
3) refactoring limit boundary conditions.
Correct operation is priority 1. Correct ops result in performance. I will implement as many corrections as possible in the existing sieve as rapidly as possible (and time worthy) to make it equivalent to the new sieve with exception of the limits being removed (which is new sieve only).
I will aim to make this sieve more efficient in it's current implmentation with NO changes to the math.... the core algorithms & techniques will remain the same. The end result will be less memory, less wasted cpu time, and fewer page faults... resulting in more P/ sec.
I would be greatly interested in knowing the P range and/or value / conditions that caused the trap/core dump... It would point me to possibly yet another area that I have yet to examine.
Please forgive the prose.. the hour here is late. If I am unclear in anything, please feel free to correct me.
Thanks
Chuck
b2 wrote:
vjs wrote:
Couple question,
Will we still use a dat file...
Have you tested it against previous sieve efforts....
Joe_O and myself have sieved several 100G worth of large n upto 100m, I could send you the factors/dat's for comparision/testing purposes...
I'd also like to test this client against high n and large ranges of n eventually.
I believe Chuck and I identified problems in the sieve code that only pertain to our project. Some code after an if riesel statement leave doubt to whether our sieve can accurately handle n>20million very well at this moment.
I'll defer to Chuck to explain this issue. I believe Chuck may have already taken care of the problem in the future sieve.
From Chuck....
Ok.. guess it's my turn to fill you all in since I've been so quiet.....
B2 is correct in that we cannot guarantee... specifically, if i may rephrase, have a very low confidence, of the current version's ability to go above 22M... and definately know that above 24M, there is almost zero confidence. I have factors which are legitimate, but the program ignored / discarded. If it DOES produce any... most are good... but no guarantees.
I can share the math... but the problem lies with the numbers 1<<25, 1<<22, 1<<19, and 1<<13. these do not work properlly when there are more than 20 K values.... Nor will it work at all above P > 2^50.
It will appear to work, but it is waisting time... part of the software is making a very honest effort to produce a real factor (and does).... only to be discarded or incorrectly 'reassembled' before printing out. This is because it detects a 2^25th partial factor and discards the entire factor. This is incorrect logic. the factor should be reduced to the lowest set of primes FIRST, recalculated in terms of K.2^N +/- 1... and THEN the test if N > 25.....
The reverse method (which I use), is to ensure the final N<25 during the factoring / reduction / reconstruction process...
Hope that makes sense.. it is difficult to describe multiple 32 and 64 bit words that you 'slide' above and below each other.... (in a stack) until they cancel out... (the cross cancelling is the key)..
The existing bitmap is basically flawed due to coding errors and, mostly, hardware changes. It was originally designed for SOB, and this is obvious in the # of bits used as boundary conditions. It was also designed for fewer than 20 'K' values.
This is all very very evident if you were to do the following....
1) sieve 1G -> 24T, 24->48T, 48->76.8T, 76.8->96T, and finally 96T -> 112T.... The sieve will collapse at 112T. You will see speed slowdowns at each marker. These correspond to the bit positions 2^45, 2^46, 2^47, 2^48, 2^49.
or
2) sieve any range 2 -> 20M....record the results. clear the files. (startfresh).. and run 20-40M... you will notice 4000days of work vs 1 hr of work. Then do it again (full reset) at 40-60M.
I am not criticising the design, coding or anything........PLEASE don't get me wrong... it was adapted from +1 to -1, it is a 3000+ line of code highly complex work.... The translation was a non-trivial task. I am pleased how much works as well as it does. It is quite remarkable. It was created before 64 bits was "Native"... now 64 bit math is 'normal'.
In the new sieve, none of this is a problem because 2^50 is not a limit , nor is 2^25 within the sieve.... The only limits are:
a) Nmin -> Nmax factor values are searched (2^2 -> 2^64) fast mode.
aa) Nmax > 2^64 is a bit slower.
b) Nmax < 2^25 (an LLR limit for now).... so even putting 20M <=N <= 40M would gain nothing...
..... UNLESS it can refactor it.... Otherwise it would chop at 2^25 (32meg) if it cannot find a way to reduce N to within the LLR limit and then you are subject to the possibility of a 'duplicate' or 'out of range'.
Essentiallly... after I complete the repairs to the existing sieve, which take priority, I will finish the new sieve.
This will allow us to maintain a complete verification database of factors output.
Repairs / bug fixes are currently prioritized as:
1) bitmap
2) ranging (Scanning N, and Output 2^N)
3) refactoring limit boundary conditions.
Correct operation is priority 1. Correct ops result in performance. I will implement as many corrections as possible in the existing sieve as rapidly as possible (and time worthy) to make it equivalent to the new sieve with exception of the limits being removed (which is new sieve only).
I will aim to make this sieve more efficient in it's current implmentation with NO changes to the math.... the core algorithms & techniques will remain the same. The end result will be less memory, less wasted cpu time, and fewer page faults... resulting in more P/ sec.
I would be greatly interested in knowing the P range and/or value / conditions that caused the trap/core dump... It would point me to possibly yet another area that I have yet to examine.
Please forgive the prose.. the hour here is late. If I am unclear in anything, please feel free to correct me.
Thanks
Chuck