mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-11-13, 22:50   #1
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2C016 Posts
Default Mersenne statistics on p-1 factoring

hi,

Rumours that reached me indicated that p-1 factoring gets used at highspeed for Mersenne.

Is there statistics on how much p-1 factoring is removing after trial factoring has been applied to Mersenne?

We're investigating that now for Wagstaff.

That is, the statistics are most important to compare with alternatives i'll try, if those alternatives factor anything useful at all after deep trial factorisation.

I do have a break even table on trial factorisation for mersenne, what break-even table is getting used for the p-1 factorisation?

Thanks for sharing any info,
Vincent
diep is offline   Reply With Quote
Old 2010-11-14, 12:51   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

When you start a P-1, Prime95 tells you the expected chance of finding a factor. It depends on what B1 and B2 bounds were chosen, which depends on the memory you allowed it and the formula at The Math page, but I think it usually is around 5%. The current strategy is to do most of the TF, then P-1, then the last bit of TF. e.g. for a target TF depth of 70, you'd TF from 0 to 2^69, do P-1, then TF from 2^69 to 2^70. This was calculated to be marginally better than doing all TF, then the P-1.
Mini-Geek is offline   Reply With Quote
Old 2010-11-14, 12:58   #3
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

70410 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
When you start a P-1, Prime95 tells you the expected chance of finding a factor. It depends on what B1 and B2 bounds were chosen, which depends on the memory you allowed it and the formula at The Math page, but I think it usually is around 5%. The current strategy is to do most of the TF, then P-1, then the last bit of TF. e.g. for a target TF depth of 70, you'd TF from 0 to 2^69, do P-1, then TF from 2^69 to 2^70. This was calculated to be marginally better than doing all TF, then the P-1.
Thanks!

Yes i also figured out that the last part of the TF is simply very expensive.

The odds you TF a number after having done nearly a 30 minutes of TF, it becomes real little after that to do another additional bit. Whereas the next bit takes 1+ hour.

Also the amount that gets TF'ed here with 1 additional bit of TF is a lot less than the VRB-Reix test takes; this of course because last few years cpu's have improved that much in floating point.

5% roughly is not bad for P-1 at Mersenne.

Is your roughly 5% indication, a percentage of the remainder or a percentage of the number of prime exponents?

Here TF removes roughly 60% of all prime exponents for wagstaff.

Regards,
Vincent

Last fiddled with by diep on 2010-11-14 at 12:59
diep is offline   Reply With Quote
Old 2010-11-14, 15:40   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by diep View Post
Is your roughly 5% indication, a percentage of the remainder or a percentage of the number of prime exponents?
For such a small number it's almost the same, but it's the chance that the P-1 will be successful, so it's not quite either. It's: 5% of P-1'd candidates are eliminated through a P-1 factor. e.g. if 100 exponents remained after TF to the P-1-appropriate level, 5 should be eliminated with 95 remaining.
Mini-Geek is offline   Reply With Quote
Old 2010-11-14, 18:15   #5
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

10110000002 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
For such a small number it's almost the same,

not really.

5% from 100% = 5%
5% from 40% = 2%

Quote:
but it's the chance that the P-1 will be successful, so it's not quite either. It's: 5% of P-1'd candidates are eliminated through a P-1 factor. e.g. if 100 exponents remained after TF to the P-1-appropriate level, 5 should be eliminated with 95 remaining.
Glad you explain it clearly. It is 2% that gets eliminated from the original candidates (that are prime themselves).

Means it improves the total factorisation rate to 62% roughly.

Many thanks for the answer!

Vincent
diep is offline   Reply With Quote
Old 2010-11-14, 18:30   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×5×587 Posts
Default

Look at the top producers report for success rates.
Here is some data I quickly gathered. I excluded ANONYMOUS because lots will not have had enough memory and Rob_Dee because it looks like he has done lots of low exponent p-1. These are the top 5 I thought were accurate expectations.
Code:
Attempts    Successes    %Success
3128           211        6.75
2070           167        8.07
3255           192        5.9
2974           196        6.59
1613           110        6.82

Last fiddled with by henryzz on 2010-11-14 at 18:32
henryzz is offline   Reply With Quote
Old 2010-11-14, 18:41   #7
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

26·11 Posts
Default

Quote:
Originally Posted by henryzz View Post
Look at the top producers report for success rates.
Here is some data I quickly gathered. I excluded ANONYMOUS because lots will not have had enough memory and Rob_Dee because it looks like he has done lots of low exponent p-1. These are the top 5 I thought were accurate expectations.
Code:
Attempts    Successes    %Success
3128           211        6.75
2070           167        8.07
3255           192        5.9
2974           196        6.59
1613           110        6.82
Wow very useful, many thanks!

How much RAM are we speaking about?

My hardware here has lots of RAM...
...and yet very little if i calculate from the 90s using knuth's transistor doubling rate of factor 2 each 18 months.
diep is offline   Reply With Quote
Old 2010-11-14, 19:09   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110111011102 Posts
Default

Quote:
Originally Posted by diep View Post
Wow very useful, many thanks!

How much RAM are we speaking about?

My hardware here has lots of RAM...
...and yet very little if i calculate from the 90s using knuth's transistor doubling rate of factor 2 each 18 months.
I think the current recommendation is >= 500MB per core. The person with ~8% probably has more memory that the other people. As far as I know once you get to 1-1.5GB per core more memory doesn't help that much more.
henryzz is offline   Reply With Quote
Old 2010-11-14, 19:13   #9
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

26·11 Posts
Default

Quote:
Originally Posted by henryzz View Post
I think the current recommendation is >= 500MB per core. The person with ~8% probably has more memory that the other people. As far as I know once you get to 1-1.5GB per core more memory doesn't help that much more.
Oh really, do most people have so little RAM?

I thought most sold thing is a laptop and most laptops have at most 2 cores and 2GB ram default.

Am i wrong?

Vincent
diep is offline   Reply With Quote
Old 2010-11-14, 19:22   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts
Default

Quote:
Originally Posted by diep View Post
Oh really, do most people have so little RAM?

I thought most sold thing is a laptop and most laptops have at most 2 cores and 2GB ram default.

Am i wrong?

Vincent
Allocated to Prime95. :)
When my pc had 2GB of memory I would never have allocated more than 1GB because the pc would have become unusable. The operating system and other running programs need memory as well especially windows.
henryzz is offline   Reply With Quote
Old 2010-11-14, 19:27   #11
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

13008 Posts
Default

Quote:
Originally Posted by henryzz View Post
Allocated to Prime95. :)
When my pc had 2GB of memory I would never have allocated more than 1GB because the pc would have become unusable. The operating system and other running programs need memory as well especially windows.
Ah yes i forgot, it's fulltime busy factorizing here at the machines, not there :)
diep is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Factoring Report at mersenne.ca Gordon mersenne.ca 21 2019-01-21 02:38
Factoring Mersenne numbers paulunderwood Miscellaneous Math 18 2017-08-27 14:56
(FAQ?) Statistics on http://mersenne.org/account/ Unregistered Information & Answers 3 2009-01-07 14:28
Factoring compltely low mersenne numbers henryzz Factoring 17 2007-09-11 19:22
Mersenne NUmber Factoring andi314 Math 4 2002-11-26 14:25

All times are UTC. The time now is 11:42.

Wed May 12 11:42:25 UTC 2021 up 34 days, 6:23, 0 users, load averages: 1.89, 1.50, 1.43

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.