mersenneforum.org PRP for F33?
 Register FAQ Search Today's Posts Mark Forums Read

2020-11-12, 17:27   #45
chris2be8

Sep 2009

200510 Posts

Quote:
 Originally Posted by bbb120 you don't know Google and Wikipedia and Twitter and Facebook and YouTube can not be used in some country
Just use whatever search engine is available in China. Or move to a civilised country.

Chris

 2020-11-12, 18:03 #46 bsquared     "Ben" Feb 2007 3,371 Posts I didn't know much about the algorithm either, really, but after looking at it for a few minutes I'll illustrate how I think it works. I'm going by the recursive description here: numberworld.org/y-cruncher/internals/binary-splitting-library.html#pi_chudnovsky Say you want to compute pi to 1000 decimal places. With ~15 digits per term, you need about 67 terms. So n=67 and we therefore need to compute P(0,67) and Q(0,67), after which we can get pi by doing a few more multiplications/divisions/additions by constants. I am not going to spell out every single recursive step, but lets look at just the P term, starting with P(0,67): Code: Need P(0,67), Q(0,67) Pick m=33 P(0,67)=P(0,33)Q(33,67)+P(33,67)R(0,33) Q(0,67)=Q(0,33)Q(33,67) R(0,67)=R(0,33)R(33,67) Need P(0,33) Pick m=16 P(0,33)=P(0,16)Q(16,33)+P(16,33)R(0,16) Need P(0,16) Pick m=8 P(0,16)=P(0,8)Q(8,16)+P(8,16)R(0,8) Need P(0,8) Pick m=4 P(0,8)=P(0,4)Q(4,8)+P(4,8)R(0,4) Need P(0,4) Pick m=2 P(0,4)=P(0,2)Q(2,4)+P(2,4)R(0,2) Need P(0,2) Pick m=1 P(0,2)=P(0,1)Q(1,2)+P(1,2)R(0,1) Now we have a bunch of terms of the form P(b-1,b), Q(b-1,b), and R(b-1,1), for which we have explicit formulas. Following the recursion back upward, each multiplication is now of two (large) numbers of approximately equal size, so we can take advantage of asymptotically fast multipliers. The number of steps in the recursion is logarithmic in 'n'. So, you can see now, hopefully, that we are not really iterating anything. We are recursively multiplying numbers of equal size, using fast multiplication algorithms. Hence arriving at O(n (log n)^3). Fermat tests *do* have to iterate, on each binary bit of the exponent. Each iteration also uses fast multiplication algorithms, but we have way more terms to iterate over than we would have steps in the recursive computation of pi. I encourage you to go through all of the recursive steps in this process. Getting your hands dirty like this is a great way to learn something. For a small enough target (pi to 1000 digits is probably doable), you can do all of the computing with mathematica and track the intermediate products in a text file.
2020-11-17, 13:39   #47
LaurV
Romulan Interpreter

Jun 2011
Thailand

52·7·53 Posts

Quote:
 Originally Posted by mathwiz We can at least write F33 as 2^8589934592+1, yes? That may at least help to illustrate just how much larger it is than the largest-known prime, 2^82589933-1.
The real issue here is that people, even math-literates, don't realize the size of these numbers. Yeah, 2^85 is close to the number of particles in the universe, but people don't either realize how big is that. And how many times bigger is 2^825 compared with 2^85? How about 2^8589? How many universes? If you increase the exponent 100 (and 4) times, how many times the number raises? Assuming you can PRP the mersenne one in one day, how many days would you need to PRP the fermat one? (considering the increase of the FFT, and increase of the number of iterations). No need answers, all these are just rants and rhetoric questions, but one should try to imagine for himself what's going on here. Most people can't even imagine the magnitude of the numbers we deal with.

Last fiddled with by LaurV on 2020-11-17 at 13:40

2020-11-17, 14:01   #48
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5×1,217 Posts

Quote:
 Originally Posted by LaurV Yeah, 2^85 is close to the number of particles in the universe ...
Hehe.

Yeah, 1085 and 285 is only 8 different. So close it is. You are right.

Quote:
 Originally Posted by LaurV Most people can't even imagine the magnitude of the numbers we deal with.
Touché.

2020-11-17, 14:11   #49
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5·1,217 Posts

Quote:
 Originally Posted by bbb120 you don't know Google and Wikipedia and Twitter and Facebook and YouTube can not be used in some country
The main difference between F33 and pi is that we are only computing the value of pi. We can also compute the value of F33 easily.

The hard part is to test F33 for primeness. We will never test pi for primeness.

Last fiddled with by retina on 2020-11-17 at 14:13

2020-11-17, 15:42   #50
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·5·17·29 Posts

Quote:
 Originally Posted by retina Hehe. Yeah, 1085 and 285 is only 8 different. So close it is. You are right. Touché.
Or ~2; 1085 and 2285. 285 log102 =~85.794
There seems to be considerable uncertainty in the 1085 figure.
https://www.popularmechanics.com/spa...tire-universe/
Times 109 more if counting neutrinos https://www.quora.com/How-many-eleme...iverse?share=1
From https://en.wikipedia.org/wiki/Elementary_particle, select 1080 baryons or 1086 including neutrinos or 1097 including photons.
The article links to one on the Eddington number, which appears to be some sort of record for misplaced precision and numerology.

 2020-11-18, 11:29 #51 LaurV Romulan Interpreter     Jun 2011 Thailand 100100001110112 Posts Hey, I said particle. Not atoms, quarks, elementary potatoes, etc. Let me define what that means! They are 2^85, plus or minus few!
2020-11-18, 17:23   #52
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×3×883 Posts

Quote:
 Originally Posted by retina Hehe. Yeah, 1085 and 285 is only 8 different. So close it is. You are right. Touché.
¿Que?

I make 10^85 to be 258493941422821148397315216271863391739316284656524658203125 times bigger than 2^85.

That number has 60 digits.

2020-11-18, 22:42   #53
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5×1,217 Posts

Quote:
 Originally Posted by xilman ¿Que? I make 10^85 to be 258493941422821148397315216271863391739316284656524658203125 times bigger than 2^85. That number has 60 digits.
I think your sarcasm detector is malfunctioning.

Or maybe mine is?

Both of us?

2020-11-18, 23:58   #54
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

439 Posts

Quote:
 Originally Posted by LaurV [...] plus or minus few [...]
If you'll define "few" as "finite natural number", that's definitely true!

2020-11-19, 00:41   #55
JeppeSN

"Jeppe"
Jan 2016
Denmark

2×83 Posts
Quote:
 Originally Posted by retina MM127 Now please, someone, prove me wrong and find a factor of that retched thing.
MM82589933 = 2^(2^82589933-1) - 1 is a prime.

Now please prove me wrong - any prime factor of that number would be the largest prime ever found.

/JeppeSN