1

If I wanted to generate a billion digits of sqrt of 2, what is the quickest way of doing that? (I am talking about the mathematical methods and the programming issue, not hardware memory limit problem)

Today I coded a program in php, using bisection method from numerical analysis. But a float in php can only display max 13 digits.

Questions:

  1. What is the most effective mathematical method for doing that? One from numerical analysis or adding values of a series?

  2. What is the best programming tool for that in php say, considering the limit of 13 of digits of a float variable?

Thank you.

MJD
  • 65,394
  • 39
  • 298
  • 580
Jane N.
  • 22
  • 1
    Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Sep 05 '21 at 11:50
  • 1
    Question 1. asks for mathematical methods, question 2. asks for programming tools. – Jane N. Sep 05 '21 at 11:52
  • here you have 1 million digits but they do not indicate the method. I guess it is a rapidly converging series. – Jean Marie Sep 05 '21 at 11:58
  • 1
    Bisection is very slow because each loop only gives you 1 more bit. You can do much better than that. Eg, the Babylonian method aka Heron's formula (which is a special case of Newton's method) doubles the precision on each loop. – PM 2Ring Sep 05 '21 at 12:01
  • In English is this area of mathematics called arbitrary-precision arithmetic. – Jane N. Sep 05 '21 at 12:01
  • 1
    Why PHP? In Python, it would be easier because arbitrary precision integer arithmetic is built into Python. There's also the standard decimal module for arbitrary precision fixed-point decimal arithmetic. However, doing calculations with a billion decimal digits tends to be slow &/or difficult unless you have a lot of RAM. – PM 2Ring Sep 05 '21 at 12:04
  • "Most effective" depends on what is available at what cost. For example, whether to do your intermediate arithmetics as rationals with large integer denominators and numerators (e.g., directly computing continued fractions of $\sqrt{2}$ until denominator is large enough), or as floats with large significand. – user10354138 Sep 05 '21 at 12:11
  • Here can be found series that are all based on the series expansion of $\sqrt{1+x}$ but whose convergence can be improved by the use of the first convergents of $\sqrt{2}$ (resulting from its continued fraction expansion). – Jean Marie Sep 05 '21 at 12:14
  • Here's some live Python code using the Heron algorithm that can easily calculate >100,000 digits of sqrt(2) in a couple of seconds. For larger sizes, most of the time is consumed in converting from binary to decimal & printing. – PM 2Ring Sep 06 '21 at 12:20

0 Answers0