mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2002-08-26, 12:33   #1
guido72
 
guido72's Avatar
 
Aug 2002
Rovereto (Italy)

3·53 Posts
Default Iterations requested for factoring...

Hi all!
It is well how to time a LL-test, 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.
guido72 is offline   Reply With Quote
Old 2002-08-27, 01:19   #2
PageFault
 
PageFault's Avatar
 
Aug 2002
Dawn of the Dead

5·47 Posts
Default

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.
PageFault is offline   Reply With Quote
Old 2002-09-06, 16:17   #3
guido72
 
guido72's Avatar
 
Aug 2002
Rovereto (Italy)

100111112 Posts
Default

Quote:
Originally Posted by PageFault
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.
Thank a lot for your answering!
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?
guido72 is offline   Reply With Quote
Old 2002-09-06, 20:35   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×5×691 Posts
Default

Quote:
Originally Posted by guido72
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?
Its been years since I've run any factoring jobs or worked on this code. Does it give per iteration timings? If so, an iteration is probably one or four or eight runs through an 4KB sieve. A 4KB sieve represents 32K bits. One bit is needed for each possible trial factor. A factor is of the form 2kp+1 and this broken into 16 passes with a distance of 120*p for each bit. That's clear as mud. Putting it all together, factoring from 2^65 to 2^66 would take (2^66 - 2^65) * 16 / (120 * p) / 32768 sieves. So for P = 20000000, that would be 7.5 million sieves. I think these are lumped into groups of 8, for a total of 1 million "iterations".

How far off was I?
Prime95 is offline   Reply With Quote
Old 2002-09-07, 05:28   #5
binarydigits
 
Aug 2002

22×13 Posts
Default

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 475MHz-K6 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.
binarydigits is offline   Reply With Quote
Old 2002-09-07, 21:04   #6
guido72
 
guido72's Avatar
 
Aug 2002
Rovereto (Italy)

15910 Posts
Default

Quote:
Originally Posted by Prime95
Quote:
Originally Posted by guido72
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?
Its been years since I've run any factoring jobs or worked on this code. Does it give per iteration timings? If so, an iteration is probably one or four or eight runs through an 4KB sieve. A 4KB sieve represents 32K bits. One bit is needed for each possible trial factor. A factor is of the form 2kp+1 and this broken into 16 passes with a distance of 120*p for each bit. That's clear as mud. Putting it all together, factoring from 2^65 to 2^66 would take (2^66 - 2^65) * 16 / (120 * p) / 32768 sieves. So for P = 20000000, that would be 7.5 million sieves. I think these are lumped into groups of 8, for a total of 1 million "iterations".

How far off was I?
Thanks, George! Your "lessons" are always suited to the understanding of the pupils...
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 "2-bits-adjusted 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 mathematic-esoteric 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...
guido72 is offline   Reply With Quote
Old 2002-09-07, 21:09   #7
guido72
 
guido72's Avatar
 
Aug 2002
Rovereto (Italy)

100111112 Posts
Default BBCode jokes...

I'm Sorry but someone or something took the number "8" and the closed bracket as an emoticon...
It's funny!
guido72 is offline   Reply With Quote
Old 2002-09-07, 21:46   #8
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

153768 Posts
Default

Quote:
Originally Posted by guido72
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?
Probably, means "its one of these values and I don't remember which".
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.
Prime95 is offline   Reply With Quote
Old 2002-09-07, 21:59   #9
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×5×691 Posts
Default

From factor64.asm:


repcnt EQU 4 ; How many reps before returning
Prime95 is offline   Reply With Quote
Old 2002-09-08, 05:40   #10
guido72
 
guido72's Avatar
 
Aug 2002
Rovereto (Italy)

3·53 Posts
Default

Quote:
Originally Posted by Prime95
From factor64.asm:


repcnt EQU 4 ; How many reps before returning
As usual, many thanks George! You're like your program in a sense:
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
guido72 is offline   Reply With Quote
Old 2002-09-08, 06:34   #11
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

756110 Posts
Default Re: BBCode jokes...

Quote:
Originally Posted by guido72
I'm Sorry but someone or something took the number "8" and the closed bracket as an emoticon...
It's funny!
That is the BBS trying to think for you...

Next time check off "Disable Smilies in this post" and all will be well...

Here is an example...

Quote:
(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.
Xyzzy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Program requested devarajkandadai Software 3 2013-07-08 12:01
Rigour Requested davieddy Math 0 2013-04-25 11:47
Can anyone explain 'iterations' for factoring? petrw1 PrimeNet 8 2007-08-11 18:28
Search engine feedback requested. Xyzzy Forum Feedback 2 2007-05-28 04:22
ecm benchmarks requested for Stage 1 and 2 jasong GMP-ECM 0 2007-04-19 02:25

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

Sat Jul 11 05:38:48 UTC 2020 up 108 days, 3:11, 0 users, load averages: 0.86, 1.26, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.