20201112, 17:27  #45 
Sep 2009
3×659 Posts 

20201112, 18:03  #46 
"Ben"
Feb 2007
6441_{8} 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/ycruncher/internals/binarysplittinglibrary.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) 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. 
20201117, 13:39  #47 
Romulan Interpreter
Jun 2011
Thailand
21673_{8} Posts 
The real issue here is that people, even mathliterates, 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 20201117 at 13:40 
20201117, 14:01  #48 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3^{4}·37 Posts 

20201117, 14:11  #49  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
13552_{8} Posts 
Quote:
The hard part is to test F33 for primeness. We will never test pi for primeness. Last fiddled with by retina on 20201117 at 14:13 

20201117, 15:42  #50  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
29·167 Posts 
Quote:
There seems to be considerable uncertainty in the 10^{85} figure. https://www.popularmechanics.com/spa...tireuniverse/ Times 10^{9} more if counting neutrinos https://www.quora.com/Howmanyeleme...iverse?share=1 From https://en.wikipedia.org/wiki/Elementary_particle, select 10^{80} baryons or 10^{86} including neutrinos or 10^{97} including photons. The article links to one on the Eddington number, which appears to be some sort of record for misplaced precision and numerology. 

20201118, 11:29  #51 
Romulan Interpreter
Jun 2011
Thailand
3×3,049 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! 
20201118, 17:23  #52 
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
10502_{10} Posts 

20201118, 22:42  #53 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×3^{4}×37 Posts 

20201118, 23:58  #54 
"Oliver"
Sep 2017
Porta Westfalica, DE
406_{10} Posts 

20201119, 00:41  #55 
"Jeppe"
Jan 2016
Denmark
10100100_{2} Posts 
