20030408, 02:41  #1 
Jan 2003
far from M40
5^{3} Posts 
faster factoring?
Hi, LMHers!
During my factoring work I noticed that factoring 2^60 to 2^61 and 2^61 to 2^62 had about the same per iteration time. Nevertheless, factoring over the 6061/6162 edge took roughly 1.5 as much time. (10000 iterations between screen outputs) Can anyone confirm this? Would it be faster to split factoring jobs into 1 bit tasks? Benjamin 
20030408, 03:03  #2 
Aug 2002
Termonfeckin, IE
3×919 Posts 
Actually, time taken to factor doubles at each step. So 61>62 should take twice as much time as 60>61.
The per iteration time remains the same but you will see that the percent complete between iterations halves. So, in essence the number of iterations doubles. Mind you, the concept of iterations is imaginary for factoring and was created by George to give some sense of progress in the client. 
20030408, 03:06  #3 
Aug 2002
Ann Arbor, MI
433 Posts 
I'm not sure what you mean by splitting it into a 1 bit task, but the reason it takes longer is because you're factoring twice as far as before. The range from 2^602^61 has 2^60 numbers, and the one from 2^612^62 has 2^61 numbers. The numbers of factors you need to check in each range may not be exactly double, but it's close enough too explain why one takes longer.

20030408, 03:38  #4  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{3}×919 Posts 
Re: faster factoring?
Quote:
One bit tasks should not speed up the factoring job. You have to test the same number of factors either way. 

20030408, 04:35  #5  
Aug 2002
Richland, WA
2^{2}·3·11 Posts 
Re: faster factoring?
Quote:
Factoring M21491957 to 2^61 is 85.00% complete. Time: 5.000 sec. Factoring M21491957 to 2^61 is 95.00% complete. Time: 5.000 sec. Factoring M21491957 to 2^62 is 2.50% complete. Time: 7.500 sec. Factoring M21491957 to 2^62 is 7.50% complete. Time: 5.000 sec. Factoring M21491957 to 2^62 is 12.50% complete. Time: 5.000 sec. I'm sure George knows better, but I think the reason the italicized line takes longer is because Prime95 does sieving or some sort of precalculations needed for the next bit depth (62 bits in this case). 

20030408, 05:24  #6  
Aug 2002
2×101 Posts 
Re: faster factoring?
Quote:


20030408, 10:18  #7 
Jan 2003
far from M40
1111101_{2} Posts 
Hi LMHers!
It now seems to turn out as a power supply problem. The fan somehow denied service. When I fired up the machine, I got timings of about 140 ms / iter. Then timings switch to about 220 ms / iter and stayed so until the pc went down. The described phenomenon probably was a kind of announcement. Need to get some HQ Power Supply. When I got it, I'll retry it to see if there is a timing increasement around the bitpassover and if so, of what kind. Benjamin 
20030408, 14:59  #8 
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
Both trif and Nick are correct, but trif is more correct than Nick in terms of explaining the extra time displayed for the first interval of a new bit level when trial factoring straddles multiple bit levels.
It happens that I've just recently run 86 timing tests of trial factoring on single bit levels (e.g., 2^58>2^59, not 2^58>2^60). All time intervals were for 1000 "iterations". (In trialfactoring, there are no iterations in the same sense as in LL testing, but since each LL iteration involves two FFT transforms, for trial factoring timing purposes Prime95 counts two FFT transforms as one "iteration".) The first time interval of each test run was, on average, slightly longer than the second and subsequent intervals. But only slightly  the maximum excess I saw in 86 runs was about 0.8% of the average total time interval. That is, the first interval was, at most, 1.008 times as long as the average of the second and subsequent intervals for each exponent/bitlevel combination. And that case looks like an anomaly, because no other run showed a firstinterval excess of more than 0.5%. Since each interval covered 1000 "iterations" (2000 FFT transforms), the firstinterval excess was about the same as 8 "iterations" (16 transforms) in one case, but no more than 5 "iterations" (10 transforms) in every other case. So my tests indicate that the initialization at the start of a bit level (or when resuming after an interruption) takes only a small amunt of time that would often be unnoticeable when timing intervals cover 1000 or more "iterations". Okay, now for the demonstration that trif is more correct than Nick. Here is the report of a timing test I just ran on my P75 (I throw that in only to explain the slow times). Note how the excesses for the first intervals of the 2^58, 2^59, and 2^60 levels correspond to trif's explanation. Factoring M67108913 to 2^57 is 90.61% complete. Time: 278.653 sec. Factoring M67108913 to 2^58 is 45.62% complete. Time: 306.486 sec. Factoring M67108913 to 2^58 is 91.25% complete. Time: 277.551 sec. Factoring M67108913 to 2^59 is 22.82% complete. Time: 330.424 sec. Factoring M67108913 to 2^59 is 45.62% complete. Time: 277.216 sec. Factoring M67108913 to 2^59 is 68.45% complete. Time: 277.132 sec. Factoring M67108913 to 2^59 is 91.25% complete. Time: 277.224 sec. Factoring M67108913 to 2^60 is 11.43% complete. Time: 383.432 sec. Factoring M67108913 to 2^60 is 22.85% complete. Time: 277.065 sec. Factoring M67108913 to 2^60 is 34.28% complete. Time: 277.181 sec. 
20030408, 16:44  #9 
Jan 2003
far from M40
5^{3} Posts 
In other words:
when starting the next bit level, the "iteration counter" is reset whereas the timer is not. sounds plausible. BTW, the new power supply is installed, so factoring is alive and kicking again. :D Thanx for your reponses. Benjamin 
20030408, 20:05  #10 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Well ... maybe I shouldn't have written what I did about the relative correctness of Nick's and trif's explanations. Nick was just as correct as trif  it was just that the magnitude of the effect trif explained was greater than the magnitude of the effect Nick explained. Nick, I apologize.

20030408, 21:51  #11  
Aug 2002
Richland, WA
2^{2}·3·11 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Faster factoring with binary splitting?  __HRB__  Software  3  20090103 16:27 
My CPU is getting faster and faster ;)  lidocorc  Software  2  20081108 09:26 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
Faster way to do LLT?  1260  Miscellaneous Math  23  20050904 07:12 
Faster than LL?  clowns789  Miscellaneous Math  3  20040527 23:39 