PRP for F33? - Page 5

chris2be8 · 2020-11-12, 17:27

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

bsquared · 2020-11-12, 18:03

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.

LaurV · 2020-11-17, 13:39

Quote:

Originally Posted by mathwiz

We can at least write F₃₃ 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.

retina · 2020-11-17, 14:01

Quote:

Originally Posted by LaurV

Yeah, 2^85 is close to the number of particles in the universe ...

Hehe.

Yeah, 10⁸⁵ and 2⁸⁵ 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é.

retina · 2020-11-17, 14:11

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.

kriesel · 2020-11-17, 15:42

Quote:

Originally Posted by retina

Hehe.

Yeah, 10⁸⁵ and 2⁸⁵ is only 8 different. So close it is. You are right.

Touché.

Or ~2; 10⁸⁵ and 2²⁸⁵. 285 log₁₀2 =~85.794
There seems to be considerable uncertainty in the 10⁸⁵ figure.
https://www.popularmechanics.com/spa...tire-universe/
Times 10⁹ more if counting neutrinos https://www.quora.com/How-many-eleme...iverse?share=1
From https://en.wikipedia.org/wiki/Elementary_particle, select 10⁸⁰ baryons or 10⁸⁶ including neutrinos or 10⁹⁷ including photons.
The article links to one on the Eddington number, which appears to be some sort of record for misplaced precision and numerology.

LaurV · 2020-11-18, 11:29

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

xilman · 2020-11-18, 17:23

Quote:

Originally Posted by retina

Hehe.

Yeah, 10⁸⁵ and 2⁸⁵ 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.

retina · 2020-11-18, 22:42

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?

kruoli · 2020-11-18, 23:58

Quote:

Originally Posted by LaurV

[...] plus or minus few [...]

If you'll define "few" as "finite natural number", that's definitely true!

JeppeSN · 2020-11-19, 00:41

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

2020-11-12, 18:03	#46
bsquared "Ben" Feb 2007 6441₈ 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-18, 11:29	#51
LaurV 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!