mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects > y-cruncher

Reply
 
Thread Tools
Old 2020-12-08, 10:59   #45
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101111002 Posts
Default

Quote:
Originally Posted by LaurV View Post
Yep. After I remake the calculus to see if I get the same value...
I assume somebody verifies this things, anyhow... Or not?
That's why your suggested methods is just not working (needs to repeat the whole computation), but my proposed way is using much less time.
For comparison in this record size the BBP takes less than a single day, while the whole record computation took 303 days. (ref. https://en.wikipedia.org/wiki/Chrono...tion_of_%CF%80). So with a 50% probability your record claim would fail in a single day. What is not that bad.

ps. Or with a much larger probability if we'd ask at each position not a single bit but say 20 consecutive bits, this is not increasing the BBP time too much but you'd fail with much larger chance.
R. Gerbicz is offline   Reply With Quote
Old 2020-12-08, 11:18   #46
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,143 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
For comparison in this record size the BBP takes less than a single day, while the whole record computation took 303 days. (ref. https://en.wikipedia.org/wiki/Chrono...tion_of_%CF%80). So with a 50% probability your record claim would fail in a single day. What is not that bad.
But the claimant can also compute the required digits just as you could.

So you ask for your 20 positional digits. A day later the reply gives the digits. You check them and see no error. Still doesn't prove the claimant computed all the other digits. Only a hash of them all after a full re-computation can do that.
retina is offline   Reply With Quote
Old 2020-12-08, 12:25   #47
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22·367 Posts
Default

Quote:
Originally Posted by retina View Post
But the claimant can also compute the required digits just as you could.

So you ask for your 20 positional digits. A day later the reply gives the digits. You check them and see no error. Still doesn't prove the claimant computed all the other digits. Only a hash of them all after a full re-computation can do that.
False, I've written this:
"if you're claiming a world record then I would choose 1 million random positions and you should give the bits for each of these positions. The check: select say 20-25 positions and verify the bits with BBP. You have an extremely small probability to fake me."

I'm requesting the bits for 1 million positions and after receiving your file with bits, checking random(!!!) 20-25 positions. If you'd do this with BBP then the overall computation time would be 2500 times larger than what a direct computation of pi would use. You can still select some positions from the list and use BBP for these and/or use known bits of pi (for small positions), but you wouldn't pass the test.

Last fiddled with by R. Gerbicz on 2020-12-08 at 12:28 Reason: small typo
R. Gerbicz is offline   Reply With Quote
Old 2020-12-08, 12:29   #48
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,143 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
False, I've written this:
"if you're claiming a world record then I would choose 1 million random positions and you should give the bits for each of these positions. The check: select say 20-25 positions and verify the bits with BBP. You have an extremely small probability to fake me."
I see now. You are correct, it would be almost impossible to fake it. Might as well do the entire computation and save a lot of hassle.
retina is offline   Reply With Quote
Old 2020-12-09, 03:06   #49
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

223548 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
If you'd do this with BBP then the overall computation time would be 2500 times larger than what a direct computation of pi would use
How do you figure? Is BBP so slow that computing one million bits with it (in fact, you compute 4 bits every time, iirc), is 2500 times slower than computing (what's the record? two terra-digits?) of pi by the fastest method? (probably some variation of Ramanujan formula?, well, it seems odd to me, but yes, I didn't make any calculation, just gut feeling, and just asking).

Last fiddled with by LaurV on 2020-12-09 at 03:12
LaurV is offline   Reply With Quote
Old 2021-01-06, 17:47   #50
Mysticial
 
Mysticial's Avatar
 
Sep 2016

33210 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
False, I've written this:
"if you're claiming a world record then I would choose 1 million random positions and you should give the bits for each of these positions. The check: select say 20-25 positions and verify the bits with BBP. You have an extremely small probability to fake me."

I'm requesting the bits for 1 million positions and after receiving your file with bits, checking random(!!!) 20-25 positions. If you'd do this with BBP then the overall computation time would be 2500 times larger than what a direct computation of pi would use. You can still select some positions from the list and use BBP for these and/or use known bits of pi (for small positions), but you wouldn't pass the test.
Another approach: Ask for any random offset and if you don't get an answer immediately, then it's suspicious. It would take a tremendous amount of computing power to run get a distant offset in under a minute.

---------------

There's some preliminary research into a hybrid BBP+Binary Splitting algorithm that may allow M consecutive digits starting from the N'th digit to be computed faster than O(M * N log(N)). (binary digits of course)

Such an algorithm could potentially allow for a low-memory distributed computation of Pi - but only the binary digits and at the cost of a much larger Big-O than the classic algorithms.

If such an algorithm does come to fruit, then asking for a million digits starting from N may not be sufficient.

Last fiddled with by Mysticial on 2021-01-06 at 17:53
Mysticial is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Google Cloud Compute 31.4 Trillion Digits of Pi Mysticial y-cruncher 30 2019-10-11 14:45
How many digits? kokakola Information & Answers 23 2009-11-03 05:08
15M Digits - Just For Fun storm5510 Math 7 2009-09-08 04:14
All 10 Digits davar55 Puzzles 5 2007-06-18 15:06
140+ digits which is better marthamm GMP-ECM 4 2006-01-25 17:32

All times are UTC. The time now is 15:11.

Tue May 18 15:11:56 UTC 2021 up 40 days, 9:52, 1 user, load averages: 1.54, 1.74, 1.88

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.