mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Operation Billion Digits (https://www.mersenneforum.org/forumdisplay.php?f=50)
-   -   CPU Time and Factors Found (https://www.mersenneforum.org/showthread.php?t=13720)

 Rodrigo 2010-08-14 03:57

CPU Time and Factors Found

Hello,

I've been poking around the GIMPS.IT site to learn a little more about OBD, and I found the following page:

[URL]http://www.moregimps.it/billion/users_p.php[/URL]

The meaning of the columns on that table is mostly self-evident, except for "CPU time." What units are being measured there, and how are the totals arrived at?

Which leads me to a second question. If you compare the "CPU time" and the "Factors found" for the various participants, there seems to be little relation between the number of factors found and the amount of computing devoted to it.

For example, Uncwilly has found 162 factors in 56.345 -- umm, aahhh, 56.345 WHAT? -- whereas lavalamp has found just one factor in 38067.400 WHATs. So it would seem that Uncwilly's efforts have been some 109,000 times more efficient per WHAT than lavalamp's.

How does that compute (so to speak)? Isn't the assignment of exponents more or less random, such that you would get more or less similar efficiency at finding exponents among the participants?

I must be missing some factor here. (Pardon the second pun, I couldn't resist...)

And just to be sure -- I'm not casting aspersions on anybody here, I'm genuinely curious as to how this works. :unsure:

Rodrigo

 Uncwilly 2010-08-14 06:51

Well, to speak to why I appear to be so good.:showoff: When OBD was starting, there were many exponents that had never been tested. I went through and tested a whole bunch to low levels. I tested them en mass, a few bits at a time at first. Then I removed those with factors and repeated. The last few steps were a single bit depth at a time.

Most of the numbers that will be factored out will be in the lowest bit ranges, were it is easier to test (less CPU time) and the best chances of find a factor.

The units used are 'one year of a Pentium 90MHz' or P90 years.
See [url]http://www.moregimps.it/billion/users_f.php[/url]
That had been the standard measure of effort for GIMPS for many years. Only recently has 'GHz days' been adopted.

Play with the calculator on :[url]http://www.moregimps.it/billion/anni_cpu.php[/url] and see sort of effort I needed to take the numbers from 32 bits (the lowest possible for these numbers) to the level where factors where found.

 S485122 2010-08-14 06:55

The unit used is P90 CPU years, the previous unit of work done in the GIMPS. It corresponds at the ammount of work an Intel P90 CPU could do with the then current version of the Prime95 software.

If you look at the "Users (by factor)" page you will see how Uncwilly found so many factors in so little time : he did the initial factoring to low levels, the great majority of the factors he found were below 50 bits. The probability of finding a factor decreases with bit level, the work implied increases.

The probability of finding a factor is very roughly inversely proportional to the size of the numbers tried as factors, for 34 bits exponents it is about 1 in 34 (of course there is a minimum factor length : 2*exponent for the Mersenne number.) The time it takes to trial factor a number to a bit level is proportional to 2 in the power of the bit level : it takes twice as long to trial factor a number from 34 to 35 bits as from 33 to 34 bits.

So the yield of trial factoring is roughly proportional to 1 / (bit level * 2[sup]bit level[/sup])

Jacob

 ET_ 2010-08-14 11:44

P90 CPU years

Well, that's not completely true... :blush:

I calculated the effort in P90 CPU years [COLOR="Red"]using an older version of Factor[/COLOR], to have a measure to test my program's enhancements.

Numbers don't agree with Prime95 computation, I'm afraid, but it shouldn't be too hard translating them into Prime95 units. I've just been a bit lazy, and in all honesty, I didn't expect that the project could attract so many people, so I didn't care much about it. :smile:

Let me know if you want the results translated... just remember that people with low P90 CPU years values would suddenly see their credit shrunk to zero point zero something.

Luigi

 Rodrigo 2010-08-14 15:09

Uncwilly,

Thanks for the links! It makes sense now. What I needed was to poke around the website some more.

So then having all these results at low levels casts you as an OBD pioneer. :smile:

Rodrigo

 Rodrigo 2010-08-14 15:23

Jacob,

Thank you for the explanations. I understand now what the units are, and what accounts for the wide range of results.

Here's a question that, I hope, will show if I get it. Does this mean that, if a new OBD range is opened up, then there will be a ton of new exponents that need to be factored from low levels?

Rodrigo

 Rodrigo 2010-08-14 15:31

ET,

Translating the numbers won't be necessary, at least not for me. Just knowing what they represent is great, thanks!

Rodrigo

 Uncwilly 2010-08-14 16:19

[QUOTE=Rodrigo;225377]Here's a question that, I hope, will show if I get it. Does this mean that, if a new OBD range is opened up, then there will be a ton of new exponents that need to be factored from low levels?[/QUOTE]
Sort of. :unsure:
I worked from the top end of the then existing range 3321928999 all the way up to 3321999991. If I found a factor I stopped, else I took them all to the 60 bit depth. So, most of my work in that range does not yet show up in the stats.

 Rodrigo 2010-08-14 20:36

[quote=Uncwilly;225386]Sort of. :unsure:
I worked from the top end of the then existing range 3321928999 all the way up to 3321999991. If I found a factor I stopped, else I took them all to the 60 bit depth. So, most of my work in that range does not yet show up in the stats.[/quote]

Wow, so your significance to OBD is even greater than it looks! Cool.

Rodrigo

 All times are UTC. The time now is 06:17.