mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-11-12, 17:27   #45
chris2be8
 
chris2be8's Avatar
 
Sep 2009

1,973 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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
chris2be8 is offline   Reply With Quote
Old 2020-11-12, 18:03   #46
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D2016 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2020-11-17, 13:39   #47
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·17·179 Posts
Default

Quote:
Originally Posted by mathwiz View Post
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
LaurV is offline   Reply With Quote
Old 2020-11-17, 14:01   #48
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

135528 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 View Post
Most people can't even imagine the magnitude of the numbers we deal with.
Touché.
retina is offline   Reply With Quote
Old 2020-11-17, 14:11   #49
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×34×37 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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
retina is offline   Reply With Quote
Old 2020-11-17, 15:42   #50
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×32×269 Posts
Default

Quote:
Originally Posted by retina View Post
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.
kriesel is online now   Reply With Quote
Old 2020-11-18, 11:29   #51
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

216518 Posts
Default

Hey, I said particle. Not atoms, quarks, elementary potatoes, etc.
Let me define what that means!
They are 2^85, plus or minus few!

LaurV is offline   Reply With Quote
Old 2020-11-18, 17:23   #52
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

28·41 Posts
Default

Quote:
Originally Posted by retina View Post
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.
xilman is offline   Reply With Quote
Old 2020-11-18, 22:42   #53
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×34×37 Posts
Default

Quote:
Originally Posted by xilman View Post
¿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?
retina is offline   Reply With Quote
Old 2020-11-18, 23:58   #54
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

2·7·29 Posts
Default

Quote:
Originally Posted by LaurV View Post
[...] plus or minus few [...]
If you'll define "few" as "finite natural number", that's definitely true!
kruoli is online now   Reply With Quote
Old 2020-11-19, 00:41   #55
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·34 Posts
Quote:
Originally Posted by retina View Post
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
JeppeSN is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 20:03.

Fri Jan 15 20:03:18 UTC 2021 up 43 days, 16:14, 0 users, load averages: 2.49, 2.50, 2.42

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