mersenneforum.org  

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

Reply
 
Thread Tools
Old 2007-05-15, 17:03   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

519610 Posts
Default What is the formula for factoring credits?

I just learned how easy it is to calculate LL/DC credits using the status chart

Now that leaves me curious how factoring credits are calculated. Is it just as easy to determine from a similar chart somewhere?
petrw1 is offline   Reply With Quote
Old 2007-05-16, 05:25   #2
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

1,823 Posts
Default

The formula is the following and can be infered from the sources of Prime95.

Factoring Credit : Constant * (2^"HowFarFactored"-2^"HowFarItHadAlreadyBeenFactored")/Exponent

Constant for factoring up to 62 5,00000E-17
Constant for factoring up to 63-64 2,17250E-14
Constant for factoring up to 65 and above 1,63100E-14

So for factoring an exponent N from 62 to 68 bits :

(5 E-17 * (2^64 - 2^62) / N) + (2,1725 E-14 * (2^68-2^64) / N)

Jacob
S485122 is offline   Reply With Quote
Old 2007-05-16, 18:27   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

519610 Posts
Default

Thanks.

So as I understand it, if I have a Factoring assignment this computes the credits; however, if I have a LL assignment that first determines the exponent needs to be factored more I assume I will get the Factoring credits for this factoring work and then the LL credits once the LL test is done....correct?

As well, I assume what you are talking about here is P-1 factoring. Are credits also awarded for ECM factoring or is that NOT part of the GIMPS initiative?
petrw1 is offline   Reply With Quote
Old 2007-05-16, 19:17   #4
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

22·3·433 Posts
Default

Quote:
Originally Posted by S485122 View Post
So for factoring an exponent N from 62 to 68 bits :

(5 E-17 * (2^64 - 2^62) / N) + (2,1725 E-14 * (2^68-2^64) / N)

Jacob
Maybe I misunderstand, but as I read your explanation I think the formula should be:

1.63100E-14 * (2^68 - 2^62) / N

I used the constant 1.631E-14 because I am going up to 68 bits, and I am factoring an exponents already factored up to 62 bits.

This gives me a number that matches the credits I actually received lately.
petrw1 is offline   Reply With Quote
Old 2007-05-17, 12:24   #5
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

1,823 Posts
Default

I did mix up the constants :-(

I meant :

2,1725 E-14 * (2^64 - 2^62) / N + 1.631 E-14 * (2^68-2^64) / N = (300566,636 + 4512995,937) / N = 4813562,574 / N

Your formula gives 4738645,735 / N

The difference between your formula and the one I think is the correct one is less than two percent because the first term about 15 times smaller than the second.

Last fiddled with by S485122 on 2007-05-17 at 12:35
S485122 is offline   Reply With Quote
Old 2007-05-22, 21:52   #6
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

22·3·433 Posts
Default

You appear to be correct ... the points I got for the last number I factored matches the points your formula came up with.

HOWEVER ... one thing that strikes me as odd is: Since the formula divides by "N", the BIGGER the exponent(N) the FEWER the points that will be awarded (within specified ranges) ?!?! This seems backwards to me
petrw1 is offline   Reply With Quote
Old 2007-05-23, 05:41   #7
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

1,823 Posts
Default

This is because the bigger the exponent the fewer the potential factors in each interval (63 bits, 64 bits...) Since the factors are of the form 2*k*exponent+1 the number of k to be tried is proportionnal to 2n/(2*exponent). I say proportionnal because some the k values are eliminated before trying, see the The Math page on the GIMPS site. The trial factoring times indeed decrease when the exponent increases.

Last fiddled with by S485122 on 2007-05-23 at 05:42
S485122 is offline   Reply With Quote
Old 2007-05-23, 18:30   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts
Default

Quote:
Originally Posted by petrw1 View Post
HOWEVER ... one thing that strikes me as odd is: Since the formula divides by "N", the BIGGER the exponent(N) the FEWER the points that will be awarded (within specified ranges) ?!?! This seems backwards to me
Yes, many (maybe most) people think the same thing when they first contemplate a formula for trial factoring credit.

But, for the reason that Jacob gave, it takes about twice as long to TF exponent 18xxxxxx from 264 to 265 as it does to TF exponent 36xxxxxx from 264 to 265, because the lower exponent has twice as many potential 2kp+1 factors in that range as the higher exponent has.

Last fiddled with by cheesehead on 2007-05-23 at 18:36
cheesehead is offline   Reply With Quote
Old 2007-05-23, 19:50   #9
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

22×3×433 Posts
Default

Hmmm.....this might clarify something for me.

About a month ago, just for fun, and after learning about the undocumented feature AdvanceFactor, I thought I would try Advancing M1061 from 60 to about 75 BITS. I naively assumed that if I could factor a 40M exponent from 62 to 68 in a day that I could advance M1061 from 60 to 75 bits in a matter of minutes. Well I started it and when it took a few hours to do 1% of 61 BITS I assumed it must be doing a completely different, very intense method of factoring for it to take that long, so I cancelled it.

Now that I, likewise am 1% wiser of the ways of GIMPS was it only that my M1061 experiment doing the same P-1 factoring but with an exponent with SIGNIFICANTLY more factors to test than a 40M range exponent? ... or is it that AND AdvanceFactor uses different a factoring method?
petrw1 is offline   Reply With Quote
Old 2007-05-23, 23:29   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by petrw1 View Post
I thought I would try Advancing M1061 from 60 to about 75 BITS. I naively assumed that if I could factor a 40M exponent from 62 to 68 in a day that I could advance M1061 from 60 to 75 bits in a matter of minutes.
As you now understand, trial-factoring over that range would take ... a very ... long ... time. (I'm not sure exactly what AdvancedFactor does.)

Quote:
Well I started it and when it took a few hours to do 1% of 61 BITS I assumed it must be doing a completely different, very intense method of factoring for it to take that long, so I cancelled it.
Trial factoring is as "intense" as it gets -- you're trying every possible factor!! No other method is that exhaustive.

Note that TF also tries many non-possible (composite) factors because that's faster than screening out all composite candidates. Homework question: Why do I say in this context that composite 2kp+1 candidates are not possible factors?

Quote:
was it only that my M1061 experiment doing the same P-1 factoring but with an exponent with SIGNIFICANTLY more factors to test than a 40M range exponent?
I don't know what method AdvancedFactor actually uses. If it were trial-factoring (not P-1), then the answer would be "Yes, M1061 has about 40,000 times as many potential factors in a given fixed range (such as 260 -> 261) as M4244xxxx has in that range."
cheesehead is offline   Reply With Quote
Old 2007-05-28, 18:02   #11
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

22×3×433 Posts
Default

Quote:
Originally Posted by cheesehead View Post
Note that TF also tries many non-possible (composite) factors because that's faster than screening out all composite candidates. Homework question: Why do I say in this context that composite 2kp+1 candidates are not possible factors?
Pardon my ignorance but admittedly my interest in prime numbers far exceeds my mathematical theory prowess regarding prime numbers.

In your context is the "k" composite OR the 2kp+1 composite?

For the latter, all non-prime numbers can be factored into 2 or more prime factors. SO, if we find a composite factor then by definition it can be further factored into primes.

For the former, I'll have to think harder.
petrw1 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Assignment credits? afjewkes PrimeNet 2 2016-07-15 06:26
CREDITS GONE pegaso56 Information & Answers 2 2009-12-15 02:55
How to create TWO fat CPU credits? ET_ PrimeNet 12 2008-11-03 22:11
V5 credits for trial-factoring Graff PrimeNet 2 2008-07-25 15:21
P90 CPU years credits Carlo Monari PrimeNet 2 2004-07-18 14:14

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


Thu Jun 30 11:24:40 UTC 2022 up 77 days, 9:25, 0 users, load averages: 1.63, 1.51, 1.39

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔