mersenneforum.org  

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

Reply
 
Thread Tools
Old 2019-07-30, 04:50   #1
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24×5×7 Posts
Default About LL test cycles

I assume we know that we can test for LL test cycles pretty easily. Instead of checking for repeated residue, we can store the units digit of the residue after each cycle in ram or on hard drive, and periodically check for repeating digits in this string in less than 1 second, and then verifying a true cycle exists by running a number of steps equal to the cycle length. Is the reason we don't do that that the probability is so low from what we can tell?
JuanTutors is offline   Reply With Quote
Old 2019-07-30, 05:17   #2
axn
 
axn's Avatar
 
Jun 2003

34·5·13 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
Is the reason we don't do that that the probability is so low from what we can tell?
Yep. Totally pointless.
axn is offline   Reply With Quote
Old 2019-07-30, 15:39   #3
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24×5×7 Posts
Default

Quote:
Originally Posted by axn View Post
Yep. Totally pointless.
Thanks! Also, I can hear the bunny's head hit the ground in your avatar. Reminds me of that gif of the utility pole jumping ropes with power lines.
JuanTutors is offline   Reply With Quote
Old 2019-07-30, 23:12   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3·19·107 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
I assume we know that we can test for LL test cycles pretty easily. Instead of checking for repeated residue, we can store the units digit of the residue after each cycle in ram or on hard drive, and periodically check for repeating digits in this string in less than 1 second, and then verifying a true cycle exists by running a number of steps equal to the cycle length. Is the reason we don't do that that the probability is so low from what we can tell?
How big is this units digit you mention; the rightmost 1 bit? 4 bits? 64 bits?
See https://www.mersenneforum.org/showpo...1&postcount=10
kriesel is offline   Reply With Quote
Old 2019-07-31, 03:58   #5
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24·5·7 Posts
Default

Quote:
Originally Posted by kriesel View Post
How big is this units digit you mention; the rightmost 1 bit? 4 bits? 64 bits?
See https://www.mersenneforum.org/showpo...1&postcount=10
I just mean the last bit, stored locally. For an n-digit mersennes, the file would be n bits large, and does not need to be uploaded. Quick math says the probability of a cycle existing is approximately p/Mp if the residues are distributed randomly within the range [0,Mp-1]. I'm not saying that number isn't exceedingly small if the residues are in fact randomly distributed. My question is partially asking whether the question about cycles existing is open, and partially about whether the cost is close to zero enough that it's interesting to try to answer.
JuanTutors is offline   Reply With Quote
Old 2019-07-31, 04:27   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

23×32×137 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
in less than 1 second
Do you mean like 330 times slower than the LL test itself is done?
(Think about the fact that each iteration takes, say, 3 milliseconds, in an average processor, for an average exponent.)

Joking apart, and from mathematical point of view, the length of a cycle would be closely related to the znorder of the factors. And smallest factors are larger than the exponent, by at least a factor of 2 (for p=4k+3) or 6 (for p=4k+1). If m turns out prime, there are no cycles (beside of the trivial 2-2-2-2-2). For composites, possible cycles are larger than the number of iterations we do. We'll never find one... (even the trivial cycle for a prime, happens AFTER the test is finished)

Last fiddled with by LaurV on 2019-07-31 at 04:36
LaurV is online now   Reply With Quote
Old 2019-07-31, 04:39   #7
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24×5×7 Posts
Default

Quote:
Originally Posted by LaurV View Post
Do you mean like 330 times slower than the LL test itself is done?

(Think about the fact that each iteration takes, say, 3 milliseconds, in an average processor, for an average exponent.)
True! Perhaps much faster than that. And looking for a cycle is probably significantly faster than looking for other things. Nearly free, except for the fact that the string has to be stored, so it does take SOME memory and circles per iteration. Really depends on how useful or interesting the question is. I would estimate that it would add perhaps a minute per LL test based on absolutely nothing.
JuanTutors is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Too few cycles error cardmaker Factoring 4 2016-12-29 15:52
3n + 1 cycles for n = 2^57,885,161-1 Unregistered Information & Answers 7 2013-02-16 02:24
Dependencies and cycles Sleepy Msieve 18 2011-06-10 09:16
LLT Cycles for Mersenne primality test: a draft T.Rex Math 1 2010-01-03 11:34
CPU cycles Unregistered Information & Answers 0 2007-07-19 12:24

All times are UTC. The time now is 08:54.


Thu Jan 20 08:54:13 UTC 2022 up 181 days, 3:23, 0 users, load averages: 1.60, 1.82, 1.64

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.

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