mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2009-02-28, 23:38   #1
Unregistered
 

100111000001102 Posts
Default Trial factoring speed

Hello,

I am using Windows XP (32-bit) with 32-bit Prime95 (25.9 build 3). I have an AMD Athlon 64 3200+.

For fun I started trial factoring exponents in the 99,000,000 range. I also started trial factoring exponents in the 199,000,000 range.

It seems that the exponents in the 199 million range trial factor *faster* than the smaller ones in the 99 million range. Is there a mathematical reason for this?

My worktodo.txt:

Factor=199999673,0,63
Factor=99999073,0,63

Trial factoring to 63 bits is faster on the bigger exponent. Does anyone else see similar results?
  Reply With Quote
Old 2009-03-01, 00:32   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Yes, there's a mathematical reason. A Mersenne number 2[I]p[/I]-1 can only have factors of the form 2kp+1, so a larger exponent means there are fewer candidate factors to test below a given bound. There is some more info on the math behind GIMPS at http://www.mersenne.org/various/math.php

Alex
akruppa is offline   Reply With Quote
Old 2009-03-01, 00:57   #3
Unregistered
 

130408 Posts
Default 15 Ridgely

Ahhh, that makes sense. As p gets higher, there's less potential factors due to 2kp+1.

I had the mindset that for general numbers, the bigger the number, the longer the number of calculations and the longer the time it would take to trial factor all primes < 2^X.

Thanks for your quick response.
  Reply With Quote
Old 2009-03-01, 02:43   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·17·101 Posts
Default

It's because the bitdepth is the "standard" choice for measuring trialfactoring, but for mersennenumbers it's not very logical, since we only test every 2*k*p from k=1,2,3.....

For your exponent 99999073 k-values up to 2^63/(2*99999073) = 46.1*109 are tested, but for 199999673 only k-values up to 2^63/(2*199999673) = 23.1 * 109 are tested. So if you test 199999673 to 64bit instead it will correspond to almost the same number of tests and you'll see that 199999673 will take longer.

Last fiddled with by ATH on 2009-03-01 at 02:43
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU Trial Factoring FAQ garo GPU Computing 100 2019-04-22 10:58
Approximating Factoring Speed hasan4444 Factoring 17 2009-10-28 14:34
Clues to speed up the factoring zarabatana Miscellaneous Math 21 2009-10-17 02:50
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53
How to only do Trial Factoring? michael Software 23 2004-01-06 08:54

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


Sun Jan 29 23:24:38 UTC 2023 up 164 days, 20:53, 0 users, load averages: 1.04, 1.07, 1.03

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

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