faster factoring?

S80780 · 2003-04-08, 02:41

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 60-61/61-62 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

garo · 2003-04-08, 03:03

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.

Kevin · 2003-04-08, 03:06

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^60-2^61 has 2^60 numbers, and the one from 2^61-2^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.

Prime95 · 2003-04-08, 03:38

Quote:

Originally Posted by S80780

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 60-61/61-62 edge took roughly 1.5 as much time. Can anyone confirm this?
Would it be faster to split factoring jobs into 1 bit tasks?

It should have taken twice as long not 1.5 times as long

One bit tasks should not speed up the factoring job. You have to test the same number of factors either way.

NickGlover · 2003-04-08, 04:35

Quote:

Originally Posted by S80780

Nevertheless, factoring over the 60-61/61-62 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

Are you talking about the time for the first iterations after you finish the previous bit depth? Something like this:

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 pre-calculations needed for the next bit depth (62 bits in this case).

trif · 2003-04-08, 05:24

Quote:

Originally Posted by NickGlover

Are you talking about the time for the first iterations after you finish the previous bit depth? Something like this:

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 pre-calculations needed for the next bit depth (62 bits in this case).

Actually, it's because the 100% complete is never reported, so the time it takes to do it is tacked on to the time it takes to do the first set of iterations at the next bit level.

S80780 · 2003-04-08, 10:18

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 bit-pass-over and if so, of what kind.

Benjamin

cheesehead · 2003-04-08, 14:59

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 trial-factoring, 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/bit-level combination. And that case looks like an anomaly, because no other run showed a first-interval excess of more than 0.5%.

Since each interval covered 1000 "iterations" (2000 FFT transforms), the first-interval 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 P-75 (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.

S80780 · 2003-04-08, 16:44

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

cheesehead · 2003-04-08, 20:05

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.

NickGlover · 2003-04-08, 21:51

Quote:

Originally Posted by cheesehead

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.

Umm, that's ok, considering my theory was pretty much wrong (since we were trying to explain a large, 50% effect, not a 0.8% one).

2003-04-08, 02:41	#1
S80780 Jan 2003 far from M40 5³ 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 60-61/61-62 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Faster factoring with binary splitting?	__HRB__	Software	3	2009-01-03 16:27
My CPU is getting faster and faster ;-)	lidocorc	Software	2	2008-11-08 09:26
Faster Factoring Algorithm?	Citrix	Factoring	6	2007-12-23 11:36
Faster way to do LLT?	1260	Miscellaneous Math	23	2005-09-04 07:12
Faster than LL?	clowns789	Miscellaneous Math	3	2004-05-27 23:39

2003-04-08, 03:03	#2
garo 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.

2003-04-08, 03:06	#3
Kevin 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^60-2^61 has 2^60 numbers, and the one from 2^61-2^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.

2003-04-08, 10:18	#7
S80780 Jan 2003 far from M40 1111101₂ 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 bit-pass-over and if so, of what kind. Benjamin

2003-04-08, 14:59	#8
cheesehead "Richard B. Woods" Aug 2002 Wisconsin USA 17014₈ 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 trial-factoring, 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/bit-level combination. And that case looks like an anomaly, because no other run showed a first-interval excess of more than 0.5%. Since each interval covered 1000 "iterations" (2000 FFT transforms), the first-interval 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 P-75 (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.

2003-04-08, 16:44	#9
S80780 Jan 2003 far from M40 5³ 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

2003-04-08, 20:05	#10
cheesehead "Richard B. Woods" Aug 2002 Wisconsin USA 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.