12
$\begingroup$

Bob makes a claim that he made a new record and computed $\pi$ to 10 trillion digits (or your favourite number here). How would Alice verify that the newly computed constant is actually a correct approximation of $\pi$?

Given a finite string $x,$ of $n+1$ decimal digits: $(3\ 1\ 4\ 1\ 5\ 9\ 2\ldots),$ is there an efficient algorithm to decide whether $x$ is an approximation of $\pi$ up to the $0.\underbrace{00 \ldots 01}_{n-1}$ decimal places?


Edit: Clarification.

  1. Alice does not have access to Bob's method (so she can't prove that his method is correct).
  2. Alice only receives $x$ from Bob (in any number bases), and wants to verify that $x$ is indeed a correct approximation. No further communications between them.
  3. Alice could look at all digits of $x$ but should be able to verify in time $\ll$ than what it takes to compute $x$.
  4. Motivation: Assume Alexander J. Yee did not publish his code nor his method. He only publish $x$ in many number bases. He said it took him 3 months to compute $x.$ How could we verify his claims that $x$ is correct in a day or week or two without access to his code and formulas? Is there such a verification formula or algorithm?
  • 1
    See [Approximations of $\pi$](http://en.wikipedia.org/wiki/Approximations_of_%CF%80#Development_of_efficient_formulae).2012-03-14
  • 0
    Not sure if this link helps or not. But you may refer this as well http://www.numberworld.org/misc_runs/pi-5t/details.html2012-03-14
  • 2
    Can you ask Bob to give you the digits in base 16?2012-03-15
  • 0
    @Aryabhata yes. In any base.2012-03-15
  • 1
    My earlier link was just silly, but perhaps this one might be useful in the context you are looking for http://tinyurl.com/84396h32012-03-15
  • 0
    @J.D.: Would a randomized algorithm do? Otherwise we do need to look at all the trillion digits, which I suppose is not permitted because of the lack of computing power?2012-03-15
  • 0
    @Aryabhata the randomized algorithm would do for sure.2012-03-15
  • 0
    I guess I tricked you guys into (1) crypto argument (2) bounded complexity argument. You can look at all the trillion digits, but you should be able to verify $x$ in a time $\ll$ that generating $x$. I'm really thinking here in practical terms. Assume Alexander J. Yee in the link above did not publish his code nor his method. He only publish $x$ in many bases. He said it took him 5 months to compute $x$. How could we verify his claims that $x$ is correct in a day or two without access to his code and formulas? Is there such a verification formula or algorithm?2012-03-15
  • 0
    Great Question J.D. (Reminds all of us of some clever methods)2012-03-15

1 Answers 1

13

Since you allow any base, (16 in particular) and randomized algorithm, you can use the Bailey-Borwein-Plouffe formula which allows you to compute the $n^{th}$ digit of $\pi$, without having to compute the earlier $n-1$ digits! (Alas, such a algorithm seems to have been discovered only for base-16.)

All Alice needs to do is pick "some" random digits and compare.

  • 0
    Fascinating! Classic method discovered in 1995.2012-03-15
  • 0
    How efficient is it to convert between bases?2013-08-19
  • 0
    @PyRulez: Not sure what you mean by efficient, but given an n digit number in base b, there will be a linear time algorithm ($\mathcal{O}(n)$) to convert between bases. People are still trying to find such formulae in other bases...2013-08-19