Iterations requested for factoring...

[guido72]

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.

[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.

[guido72]

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?

[Prime95]

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?

[binarydigits]

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.

[guido72]

Originally Posted by Prime95

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]

I'm Sorry but someone or something took the number "8" and the closed bracket as an emoticon...
It's funny!

[Prime95]

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]

From factor64.asm:


repcnt EQU 4 ; How many reps before returning

[guido72]

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

[Xyzzy]

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...

(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.