Data needed... Please Help!

[guido72]

Originally Posted by Reboot It

Could you post that formula, please, or perhaps a link to it? It would be interesting.

Sure!
That's it:

[code:1]
"George's Formula": (2^66 - 2^65)*16/ (120*M) / 32768
"Revisited Formula": (2^66 - 2^65)* 4 / (120*M) / 32768

Example:
Exponent: 77.909.849
Fact. bits: from 65 to 72

Bits Weight(%) Theor.#
of iterat.
-------------------------------
64 -
65 0,392% 240.855
66 0,784% 481.711
67 1,569% 963.421
68 3,137% 1.926.842
69 6,275% 3.853.684
70 12,549% 7.707.369
71 25,098% 15.414.738
72 50,196% 30.829.476
--------------------------------
Sum 100,000% 61.418.096[/code:1]

My experience (but it isn't so huge with factorization jobs, and above all limited to P4 CPUs) says that you have to put "4" instead "16" in this formula. George says that "Your formula for factoring from 2^65 to 2^66 is accurate in that it is basicly (2^66 - 2^65) * C / M, where M is the exponent, and C is a constant that will vary based on cpu type and speed." So I'd definitely need your help to collect enough data to fill a table...
Regards

[NickGlover]

Here's some relevant information about factoring iteration time that you may want to take into account. Factoring iteration time can vary based on the exponent.

Let M = exponent and F = a potential factor

Factoring iterations require ceil( log2( M ) ) squarings. This is because the binary exponentiation used for calculating 2^M mod F does as many squarings as there are bits in M. An example:

Note that
2^24 = 16777216
2^25 = 33554432

Checking a single potential factor of 33,000,000 will require 25 squarings, but checking a potential factor of 34,000,000 will require 26 squarings. So the iteration time for factoring 34,000,000 will be 26/25 times the iteration time for 33,000,000 or 4% longer (assuming everything else is equal).

[guido72]

I Thank you Nick!
I'm sorry, but I'm not sure I've understand...
Do you mean that the only relevant variable for my calculations is the number of the bit there are in each exponent? If yes, what George meant when he told me that "C is a constant that will vary based on cpu type and speed"?

[NickGlover]

Originally Posted by guido72

I Thank you Nick!
I'm sorry, but I'm not sure I've understand...

The first thing I should be clear about is that my post was not about the calculation George sent to you. That calculation covered how to figure out how many iterations are done in a factoring assignment.

My post was about the time single iterations take, or basically, the time it takes to test one factor.

Originally Posted by guido72

Do you mean that the only relevant variable for my calculations is the number of the bit there are in each exponent?

I'll give you an example of when what I said would be relevant:

2^23 = 8,388,608
2^26 = 67,108,864

Say someone tells you that their Athlon XP-1600 does factoring to 64 bits of M8,300,000 (23-bit exponent) at a rate of 23 sec for 1000 iterations.

If you want to know how long 1000 iterations of factoring M77,900,000 (27-bit exponent) to 64 bits would take on a Athlon XP-1600, the answer would not be 23 sec. It would be 23 * (27/23) = 27 sec.

So, what I said is relevant to the time an iteration takes when the number of bits in the exponent changes. However, it is not the only thing that is revelant to the iteration time. The other major thing is the bit size of the factors you are trying (or factoring depth), which you already mentioned.

[guido72]

... Once again. I think I've understand what you mean now...
So, collecting suggestions: using George's formula (which gives the theorical number of overall iterations needed) and your caveat about the bit in the exponent (which gives instead the time per iteration needed for each bit of factorization) all together I may reach the goal. I should just modify my script to take into account that the time per iteration is not the same but depends on how deeper one goes with factorization. Right?
If not, please pardon me, but here now is almost 5 o'clock in the morning... Time to go to sleep, I think!
See you soon!
Guido

[Prime95]

Originally Posted by guido72

"George's Formula": (2^66 - 2^65)*16/ (120*M) / 32768
"Revised Formula": (2^66 - 2^65)* 4 / (120*M) / 32768

George says that "Your formula for factoring from 2^65 to 2^66 is accurate in that it is basicly (2^66 - 2^65) * C / M, where M is the exponent, and C is a constant that will vary based on cpu type and speed."

First off, the concept of a factoring iteration is a complete invention. It exists solely so that the Options/Preferences dialog box can control the output frequency in "iterations between screen outputs".

The first formula I gave was in response to the question "How many iteration are there in factoring M from 2^65 to 2^66?" My answer came from studying the code and could be wrong.

The second formula "(2^66 - 2^65) * C / M, where M is the exponent, and C is a constant that will vary based on cpu type and speed" was in reply to the question "how much time does it take to factor M from 2^65 to 2^66?"

[NickGlover]

Originally Posted by guido72

I should just modify my script to take into account that the time per iteration is not the same but depends on how deeper one goes with factorization. Right?

Yes, you got it. I can give you some help with dealing with the factoring depth. There are three groups of factoring depths you need to deal with that correspond with three different paths in the code.

Two of these are:
1 to 62 bits
63 and 64 bits

Within each of these two groups, the factoring iterations all take about the same amount of time. For example, once you get an iteration time for factoring a certain exponent to 60 bits, you can assume that the same iteration time will apply for 1 to 62 bit factoring.

For 65 to 72 bits, it seems more complicated. The best I can tell, 67 bit iterations take 2% longer than 66 bits, and 66 bit iterations take 2% longer than 65 bits. 67 to 72 bit iterations all take about the same amount of time. So, you may want to consider 65, 66, and 67 to 72 bits as three separate groups to collect times for. Or you could ignore this maximum 4% variation and just consider 65 to 72 bits to be one group.

[ewmayer]

To trial-factor an exponent p to a given bound B = 2^facbits involves
sieving O(B/p) factor candidates, with each candidate needing O(log2(p))
work. Thus, the work to trial-factor M(p) to depth 2^facbits is proportional
to log2(p)*2^facbits/p. The constant of proportionality will depend on
whether B is less than or greater than the computer's supported wordsize
(here we're generally speaking of 64-bit words, i.e. the size of a
long long int in C); if K is the constant for factor candidates < 2^64,
a typical figure is 4K for factoring above 2^64 (the exact value will
depend on the implementation and the hardware.) Thus, factoring from
64 to 65 bits needs ~4x the work of factoring to 64 bits, factoring
from 0 to 2^66 needs ~(1+2*4) = 9x the work of factoring to 64 bits,
and so forth.

Note that the 4x performance penalty for factoring beyond 64 bits is

only a representative value: Garo's timings suggest a penalty ~4.5x on
the P2, vs. only ~2.5x on the P4.

On the P2 (and perhaps the P3, as well?) there also appears to be a
significant penalty in going beyond 62 bits. George, can you clue us in as
to why this is so? My factor.c code running on various 64-bit architectures
(e.g. Alpha and Itanium) suffers a small penalty in going from 63 to 64 bits
because of added integer overflow checking that is needed, but this
penalty is nowhere near what Garo's numbers for the P2 show for going
from 62 to 63 bits.

[Prime95]

Originally Posted by ewmayer

On the P2 (and perhaps the P3, as well?) there also appears to be a
significant penalty in going beyond 62 bits. George, can you clue us in as
to why this is so?

Colin Percival wrote some highly optimized factoring code for 62 bits and below. The key difference between it and the 63/64 bit code is that the 62-bit version tests two factors at once. This introduces a lot more opportunities for the CPU to schedule FPU operations.

Can the 63/64 bit code also test 2 factors at once? I don't know. With just 8 FPU registers it might be impossible. Is it worth optimizing the 63/64 bit code now. I don't think so, as most of the time is spent factoring to the current limit 2^66 or higher.

[tha]

Originally Posted by Prime95

Colin Percival wrote some highly optimized factoring code for 62 bits and below.

Can we use it for our factoring ? Can it be included in Prime95?

YotN,

Henk

[Prime95]

Percival's optimizations for 62-bit factoring are in prime95.