Calculation of Pi
From ancient times we know of the number Pi - it shows how many times longer is circumference of the circle compared to the diameter.
We know it has endless and non-repetitive pattern of digits when represented as a decimal. It starts with:
Curious question is - how did people calculated its numerical value at all? Obvious idea is that some ancient greek may use a rope to measure the circumference of some round column. However this is hardly sufficient even for two digits after decimal point because any rope is slightly elastic and any column is slightly imperfect.
Instead some pure-mathematical approach should be used. Probably one of the first was proposed by
Archimedes more than
2000 years ago.
The idea is simple:
12sides - splitting each of the hexagon's sides in two;
96sides and so on.
Surely polygons with that many sides are already quite close to circle so approximation converges fast enough.
Now, how can we convert polygon of
N sides to another with
2*N sides? I.e., how should we calculate the length of
a side of new polygon?
Regard the picture above. Point
O is the center of the circle and blue line of the length
D is one side of original
polygon (say, hexagon). There are two radiuses of the length
R drawn from the center to the ends of this side.
Now if we want to split this side
D exactly in two, we draw the third radius
R (one in the middle) to be orthogonal
to this side. Then we draw two new sides of the yet unknown length
x (green lines) to this new radius.
Note that middle radius
R is split in two (unequal) parts by crossing the side
D. Let us mark the shortest of
these two parts as
y and the rest as
h=R-y. Of course we do not know length of any of them still.
Also let us use letter
d for the half of the side
d = D/2.
See, here are several right triangles at the picture!
One is formed by outer radius
d and the part of
the middle radius
Another, smaller, consists of the
For both of these triangles Pythagorean Theorem holds, so we can write:
R^2 = d^2 + h^2 => h = sqrt(R^2 - d^2) x^2 = d^2 + y^2 => x = sqrt(d^2 + (R-h)^2)
So we can easily calculate the length of the new side
x - and use this method for approximating the circle with
Since we want to know many digits of
Pi we could not use imprecise floating-point types.
Instead we will choose
R to be very large integer, like
1 000 000 000 000 000 000 = 1e18 and then we can
perform all necessary operations on integers. Let us agree that:
2) we throw away fractional part, simply rounding the result down;
Z(with Heron's method for example), we should use as a result the greatest integer
Msuch that when squared it does not exceed
M*M <= Z).
So for example with radius
R = 1e18 and starting with hexagon with
D = R we calculate:
d=500000000000000000 h=866025403784438646 side=517638090205041524 (for 12 sides) d=258819045102520762 h=965925826289068286 side=261052384440103182 (for 24 sides) d=130526192220051591 h=991444861373810411 side=130806258460286133 (for 48 sides) d=65403129230143066 h=997858923238603506 side=65438165643552283 (for 96 sides)
And to get the value of
Pi (well, without decimal point) we need to multiply
side by amount of sides and then
2 (that is why it is good to use
R equal to some power of
Pi = 96 * 65438165643552283 / 2 = 3141031950890509584
Of course if we repeat this algorithm too many time,
side may decrease to very small values so the precision will
Input data will contain value
200 which you will use to set radius as
R = 10^K.
N will be given - how many steps of algorithm to perform (so the last polygon has
6 * 2^N sides).
Answer should give the representation of
Pi (without decimal point) after that many steps.
input data: 37 11 answer: 31415926193653839551895493120653182976
Note: since this exercise requires long-arithmetic, it is better to user language which have built-in types for this,