20020826, 12:33  #1 
Aug 2002
Rovereto (Italy)
3·53 Posts 
Iterations requested for factoring...
Hi all!
It is well how to time a LLtest, but how to do the same for factoring job? Once one knows the bits depth of factorization (say from 2^58 to 2^66) and the amount of RAM available, is it this time roughly calculable? Is somewhere a database for factoring iterations time? Regards. 
20020827, 01:19  #2 
Aug 2002
Dawn of the Dead
5·47 Posts 
ouch  tough question.
It depends on what you are factoring. If they are typical TF jobs to 66 bits, it will take about 2 days per AMD GHz on each. P4 will be somewhat less than twice as fast providing you use the new SSE2 client. P3 slightly slower than AMD on a same GHz basis. The great bulk of the time will be expended on the final pass  58 to 64 bits in a few hours, about a day on 66 bits. With the SSE2 client (anything later than v.22.7) it really kicks in on the 64 bits pass and higher. Below that P4 sucks on factoring. In general, the bigger the M number the faster it will go. At bigger M, you have to factor to more bits though. Ram has zero influence on trial factoring  it runs out of the L2 cache. 
20020906, 16:17  #3  
Aug 2002
Rovereto (Italy)
3×53 Posts 
Quote:
So you don't know wich is the formula, if ther is one, to calculate the amount of iterations needed for a Factoring job given to bottom and the top threshold (i.e. from 2^58 to 2^66). Does anybody knows something more? 

20020906, 20:35  #4  
P90 years forever!
Aug 2002
Yeehaw, FL
3×11×223 Posts 
Quote:
How far off was I? 

20020907, 05:28  #5 
Aug 2002
2^{2}×13 Posts 
George, trial factoring gives timings per "iterations between screen outputs" as set in the preferences, and outputs "Factoring Mxxxxxxxx to 2^66 is xx.xx% complete". By dividing the iterations selected by the incremental percentage increase between screen outputs, it can be calculated that there are about 1,876,700 iterations of a 20M exponent between 2^65 and 2^66. Your estimate appears to be off by almost exactly a factor of two (7.5M / 8 = 937,500) and since you and I both were rounding our numbers it probably is exactly two. Of course, I don't know what the program considers "an iteration". They must be lumped into groups of four instead of eight.
I can get any factoring assignment to increment by exactly 1% (at the 2^66 range) by setting the iterations equal to (375340 divided by the exponent in millions). My 475MHzK6 is currently factoring M18642373, so I have the iterations set to 20134. It completes 1% every 2985 seconds, so one "iteration" takes 0.148 seconds. Does that sound reasonable? Edit: I should have done your calculation first; it comes to 7.506 million sieves, which divided by 4 is 1,876,500. That's undoubtedly more accurate than the number I was using anyway, which I knew couldn't be any more accurate than +/ 0.01% (and was apparently off slightly more than that). I'll have to change the number in my formula to 375300. 
20020907, 21:04  #6  
Aug 2002
Rovereto (Italy)
3·53 Posts 
Quote:
well, at a first look and by intuition, since the exponent is in the denominator of your formula, the smaller the exponent itself, the higher the number of "iterations" and vice versa. OK: the bigger the exp, the deeper you go, nevertheless it looks a bit strange... I can just say that, if we take M77909849 as example, the results of your formula is: (2^66  2^65) * 16 / (120 * 77909849) / 32768=1,926,842 I didn't understand why you divided simply by 8... Anyway, if we take that figure as good for the stage from 2^65 to 2^66 only, the progression should be the following (As we well know these kind of monsters are factored as far as 2^72): (65) [(2^65  2^64) * 16 / (120 * 77,909,849) / 32768=963,421 it. (66) [(2^66  2^65) * 16 / (120 * 77,909,849) / 32768=1,926,842 it. (67) [(2^67  2^66) * 16 / (120 * 77,909,849) / 32768=3,853,684 it. (68) [(2^68  2^67) * 16 / (120 * 77,909,849) / 32768=7,707,369 it. (69) [(2^69  2^68) * 16 / (120 * 77,909,849) / 32768=15,414,738 it. (70) [(2^70  2^69) * 16 / (120 * 77,909,849) / 32768=30,829,476 it. (71) [(2^71  2^70) * 16 / (120 * 77,909,849) / 32768=61,658,952 it. (72) [(2^72  2^71) * 16 / (120 * 77,909,849) / 32768=123,317,903 it. Well, the "actual figures" seem to be exactly 1/4 of these, so your prevision is "2 bits forward", that is: 1,926,842 is the number of "iters" needed to go as deep as 2^68 not just 2^66... So the actual progression has been (roughly): (65) 240,855 (66) 481,711 (67) 963,422 (68) 1,926,844 (69) 3,853,688 (70) 7,707,375 (71) 15,414,750 (72) 30,829,500 Note that the "actual figure" have been calculated on Prime95 screen outputs after having set 6 digits of precision in prime.ini file, but they looks absolutely reliable (and after all, as you may see, they do not differ so much from your "2bitsadjusted theoretical value"): 61,418,145 (sum of the progression)*0.0165 sec.=1013399,3925sec.=11days,17h,30' exactely the time needed by my P4 "Pippo", which used these last two weeks doing nothing but running Prime95... So, since what you say is irrefutable, (above all when you're talking about your program!!), you'd have missed something in your precedent explanation or, much more probable, I've missed something! 1st: I didn't understand what do you mean when you say that "an iteration is "probably" one or four or eight runs through an 4KB sieve". Why there is some uncertanty about the actual numbers of runs? 2nd: if you know that all the sieves "are lumped into groups of 8" but you know as well that the weight of each group is not the same, why simply to divide by 8 instead of to calculate the number of sieves for each bit? On the other hand, I'm not so sure that all these figures aren't coming out just for a mathematicesoteric coincidence... OK! Now I'm sure that I couldn't find a better way to spend my Saturday night (try to ask my girlfriend...) and that I've written enough mathematical nonsense: for this reason I beg the pardon of you all in advance! Regards. Guido PS. As soon as possible (after having found a new girlfriend!) I'll check these figures and formulas with some others exponents... 

20020907, 21:09  #7 
Aug 2002
Rovereto (Italy)
3×53 Posts 
BBCode jokes...
I'm Sorry but someone or something took the number "8" and the closed bracket as an emoticon...
It's funny! 
20020907, 21:46  #8  
P90 years forever!
Aug 2002
Yeehaw, FL
3×11×223 Posts 
Quote:
I know that the assembly code operates on 4KB sieves. I also know that it does several of these before returning to the C code. The C code checks to see if Test/Stop occurred or if its time to print out data, then calls the assembly code to do the next batch of 4KB sieves. If I rember I'll dig into the assembly code and see what that value really is. 

20020907, 21:59  #9 
P90 years forever!
Aug 2002
Yeehaw, FL
1CBF_{16} Posts 
From factor64.asm:
repcnt EQU 4 ; How many reps before returning 
20020908, 05:40  #10  
Aug 2002
Rovereto (Italy)
3·53 Posts 
Quote:
like prime95 your answers are getting quicker and quicker :D One of these days I'll ask yuo to let me into your secret... Regards 

20020908, 06:34  #11  
"Mike"
Aug 2002
2^{4}·499 Posts 
Re: BBCode jokes...
Quote:
Next time check off "Disable Smilies in this post" and all will be well... Here is an example... Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Program requested  devarajkandadai  Software  3  20130708 12:01 
Rigour Requested  davieddy  Math  0  20130425 11:47 
Can anyone explain 'iterations' for factoring?  petrw1  PrimeNet  8  20070811 18:28 
Search engine feedback requested.  Xyzzy  Forum Feedback  2  20070528 04:22 
ecm benchmarks requested for Stage 1 and 2  jasong  GMPECM  0  20070419 02:25 