mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2003-04-08, 02:41   #1
S80780
 
Jan 2003
far from M40

53 Posts
Default 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
S80780 is offline   Reply With Quote
Old 2003-04-08, 03:03   #2
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

3×919 Posts
Default

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.
garo is offline   Reply With Quote
Old 2003-04-08, 03:06   #3
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

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.
Kevin is offline   Reply With Quote
Old 2003-04-08, 03:38   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23×919 Posts
Default Re: faster factoring?

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.
Prime95 is offline   Reply With Quote
Old 2003-04-08, 04:35   #5
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22·3·11 Posts
Default Re: faster factoring?

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).
NickGlover is offline   Reply With Quote
Old 2003-04-08, 05:24   #6
trif
 
trif's Avatar
 
Aug 2002

2×101 Posts
Default Re: faster factoring?

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.
trif is offline   Reply With Quote
Old 2003-04-08, 10:18   #7
S80780
 
Jan 2003
far from M40

11111012 Posts
Default

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
S80780 is offline   Reply With Quote
Old 2003-04-08, 14:59   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-04-08, 16:44   #9
S80780
 
Jan 2003
far from M40

53 Posts
Default

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
S80780 is offline   Reply With Quote
Old 2003-04-08, 20:05   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-04-08, 21:51   #11
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22·3·11 Posts
Default

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).
NickGlover is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 04:38.

Mon Mar 1 04:38:35 UTC 2021 up 88 days, 49 mins, 0 users, load averages: 2.01, 1.79, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.