I am genuinely curious, how do people compute decimal digits of irrational numbers in general, and $\pi$ or nth roots of integers in particular? How do they reach arbitrary accuracy?
2026-04-03 01:51:36.1775181096
On
On
On
On
On
On
On
On
On
On
On
Computing irrational numbers
5k Views Asked by user242891 https://math.techqa.club/user/user242891/detail At
12
There are 12 best solutions below
0
On
Using inequalities: Let's say $x$ is the irrational number you want determine. Then by adding decimals and evaluating if is less or greater, to obtain the desirable accuracy.
So if $x = \sqrt{3} = 1.732\dots$, by squaring $1.7$ and $1.8$ and comparing with $3$ and repeating the process again:
$$\begin{align} &(1.7)^2<3<(1.8)^2 \\ \text{and then } &(1.73)^2<3<(1.74)^2 \\ \text{and then } &(1.732)^2<3<(1.733)^2 \end{align}$$
7
On
Continued fractions are commonly used in order to get the decimal value with enough accuracy. For example, the A001203 sequence in the Sloan's online encyclopedia represents $\pi$ in a form of continued fraction (actually, all infinite, rational numbers can be decomposed into a finite continued fraction, whereas irrational numbers cannot).
0
On
For some irrational numbers, like $\pi$, there are convenient infinite series that converge to them. So for example $$\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}$$ By adding up more and more terms of this series you get closer and closer to $\pi^2/6$. You can take an estimate for some value of $n$, multiply by $6$ and then take the square root. That will give you an approximation of $\pi$. This illustrates the idea, but in practice nobody uses this series because there are series that converge to $\pi$ much faster.
2
On
I applaud your genuine curiosity. There is no general method. To compute the decimal digits for any particular irrational number you start with a definition of the number.
For $\pi$ there are lots of methods known. @GregoryGrant 's answer points to one of the oldest and most famous. Archimedes started with inscribed and circumscribed regular hexagons, then doubled the number of sides several times to increase the accuracy of his estimate. (See http://en.wikipedia.org/wiki/Pi#Polygon_approximation_era).
Searching for "computing digits of pi" will lead you to information about modern methods.
For roots of polynomials (like nth roots of integers) Newton's method is efficient.
For many irrationals, continued fractions are a good bet, as @Arteom notes.
For some particular irrationals, clever tricks (based on deep theory) give you lots of digits quickly. For example, the fractions 3/2, 7/5, 17/12, 41/29, ... are better and better approximations to $\sqrt{2}$. You should be able to guess the pattern.
3
On
You generally need to use arbitrary precision arithmetic to compute large numbers of digits of typical irrational numbers. The exception is oddball things like the Champernowne constant 0.12345678910111213141516… :)
There are various arbitrary precision arithmetic packages available. Internally, they use big arrays or lists to hold groups of the digits of the numbers they manipulate. The computer can do simple arithmetic on numbers represented this way using algorithms similar to those taught in grade school which allow you to do arithmetic on multi-digit numbers given the ability to do arithmetic on single digit numbers.
However, for very large numbers the naive multiplication & division algorithms are rather inefficient, so more subtle techniques are used. Multiplication of huge numbers can be performed efficiently using the Fast Fourier transform. Division can be performed by multiplying by the reciprocal of the divisor; reciprocals can be calculated using Newton's method.
Once you have such algorithms at your disposal it's fairly straightforward to calculate $n$th roots using Newton's method, as Lucian mentioned in the comments.
However, it's not necessary to have a full arbitrary precision arithmetic package to calculate large numbers of digits of some of the well-known irrational numbers. It's trivial in most programming languages to add or subtract large numbers that are stored as an array of digit blocks. It's also quite easy to multiply such numbers by a normal-sized number; division by a normal-sized number is similarly easy to implement. And that's all you need to calculate large numbers of terms of many Taylor series to huge precision.
One somewhat famous example of this technique is this gem written in C by the late Dik T. Winter of CWI, which computes $\pi$ to 800 decimal digits.
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,
f[b]=d%--g,d/=g--,--b;d*=b);}
Unfortunately, that cryptic little program cannot be extended to yield more (correct) digits, due to overflow problems.
But here's a program I wrote a few years ago that can generate large numbers of digits of $e$; it can calculate 10,000 digits in a couple of seconds. The original version of this program was written in C, this version is in Python 2; as you might guess the C version is significantly faster :). Hopefully, the comments explain the algorithm, even if you aren't familiar with Python. The core idea is to treat the Taylor series of $e$ as a number written in factorial base and to simply convert that number into decimal notation.
#! /usr/bin/env python
"""
ECalc - Big e calculator
Generate digits of e, using factorial base notation
Inspired by Dik T. Winter
Created by PM 2Ring 2003.12.26
Converted from C to Python 2007.12.10
"""
import sys, math
# Global constants
N = 50 # Default number of digits
W = 5 # Digits per block
A = 10 ** W
LR2P = .5 * math.log(2.*math.pi) # Log Root 2 Pi
L10 = math.log(10.) # Log 10
def invlfact(n):
""" Inverse Stirling's approx for log n factorial, using Newton's method """
x = y = n * L10 - LR2P
for i in xrange(3):
x = (y + x) / math.log(x)
return int(round(x))
def bigE(n):
""" Generate n digits of e using factorial base notation """
kmax = invlfact(n) + 1
print "Calculating e to %d places, using %d cells" % (n, kmax)
# Table for factorial base digits, initialized with series for e-2 = 1/2! + 1/3! + ...
# We ignore first two entries
d = [1] * kmax
print "e ~= 2."
j = 1
while n>0:
# Get the next W digits by firstly multiplying d by A,
# propagating carries back down the array,
# then printing the integer part & removing it.
kmax = invlfact(n) # Number of cells needed for this loop
c = 0 # Clear carry
for k in xrange(kmax, 1, -1):
d[k] = d[k] * A + c
c = d[k] // k
d[k] -= c*k
# Print block & field separator. May need modifying if you make W large
jj = (j%10 and 1 or j%50 and 2 or j%200 and 3 or 4) - 1
print "%0*d%s" % (W, c, "\n" * jj),
j += 1; n -= W
def main():
# Get number of digits
n = len(sys.argv) > 1 and int(sys.argv[1]) or N
bigE(n)
if __name__ == '__main__':
main()
According to MathWorld
Around 1966, MIT hacker Eric Jensen wrote a very concise program (requiring less than a page of assembly language) that computed e by converting from factorial base to decimal.
I expect that Eric's algorithm was substantially the same as the one in my code, which I derived from an obfuscated C program written by the late Dik Winter.
2
On
I don't know why nobody has mentioned the fast algorithms that are actually used for calculating $π$ to extremely high precision. Here are some:
0
On
There is no general way to compute the decimal expansion for an arbitrary member of the set of irrational numbers, I. :(
--Proof Start--
Here's a wishy washy proof (The statements that most obviously lack support are marked with a "*", so if anyone's interested, you should look into them yourself):
Consider R to be the set of real numbers. I is a proper subset of R, and both are uncountably infinite.* (A set that is uncountably infinite is defined by being "too big" to have a 1-to-1 correspondence with the set of integers, which is know to be countably infinite.)
Now, consider D to be the set of definable numbers, that is, numbers that have definitions. D is at most countable simply because there is a 1-to-1 correspondence between definable numbers and a subset of definitions.* (Informally, a "definition" may be thought of as a finite permutation of a finite alphabet of characters -- think dictionary -- and thus the entire set of definitions would be at most countable.*)
Now, consider C to be the set of computable numbers. Because of the way computers work -- think Turing machine -- in order for a number to be computed, it must be defined, thus, C is a subset of D.*
Since C is a subset of D, and D is at most countable, and I is know to be uncountable, there are infinitely more irrational numbers than computable numbers. Therefore, one could not hope to find a general way to "compute" any property on the set of irrational numbers.
--Proof End--
As for the second question, there is an intersection between the computable numbers and the irrational numbers. Many of these numbers can be defined as infinite sums. One can calculate decimal expansions of arbitrary accuracy for these numbers because each term in the sum is generally decreasing and taking a finite sum of the first few terms can give you an idea of the first few digits of an irrational number (say 3.1415 of pi) while the remaining infinite terms can still be calculated, but are insignificant.
0
On
how do people compute decimal digits of irrational numbers in general?
In general, you can't. Almost all real numbers are incomputable, only a countable number of real numbers are computable, $\pi$ and $e$ among them as well as almost every other number you can name.
An example of an incomputable number is Chaitin's Constant.
Because most of the numbers we use are computable, it is easy to fall into the trap that most numbers are computable; this simply isn't so.
2
On
One way to do it which i like the most are continued fractions because they make you feel that you can write an irrational number in rational terms that is $\frac{p}{q}$ form but actually its not a rational form.
A continued fraction is of the form :$$ a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cdots}}} $$
So a continued fraction for $\pi$ would be something like this:$$3+\cfrac{1}{7+\cfrac{1}{15+\cfrac{1}{1+\cfrac{1}{292+\cdots}}}}$$ So as you can see if you take the first few terms that is $$3+\frac{1}{7}$$ you get $\frac{22}{7}$ that is the famous value of $\pi$ used in high school. And one more fact which is very nice about these continued fractions are as you consider more and more fractions more accurate your answer starts becoming. There are many such continued fractions for other transcendental and irrational number which are really nice,also these continued fractions give you nice bounds for values.
0
On
To compute the $n^{th}$ root of the integer $N$, you can use Newton's iterations for the equation $$x^n-N=0:$$ $$x_{k+1}=x_k-\frac{x_k^n-N}{nx_k^{n-1}}=\left(1-\frac1n\right)x_k+\frac{N}{nx_k^{n-1}}.$$
You will need to implement all four arithmetic operations for long numbers; powers are computed using repeated squarings.
For a good starting approximation, just use the floating-point estimate.
As the iterations are "self correcting", you can increase the accuracy as the computation progresses.
0
On
One simple way to compute nth roots of integers is to use Khovanskii's matrix method. A good explanation of this process can be found here.
Here's how Archimedes did it 2,500 years ago. $\pi$ is the circumference of a circle with diameter one. What Archimedes did was to inscribe a polygon with $n$ sides inside the circle. Like this for $n=5$.
He then calculated the circumference of the polygon. This gives an approximation to $\pi$ for each $n$ and as $n$ grows it gets closer and closer to $\pi$.