Might run out of memory, or explode in some other fashion whenĬalculating 100,000,000 digits, but doesn't seem impossible any more. That our algorithm scales as O(n²) where n is the number of digits. Firstly that we justĬalculated 1,000,000 decimal places of π in 40 minutes! Secondly that toĬalculate 10 times as many digits it takes 100 times as long. There are several interesting things to note. X_squared_plus_1) to get them out of the loop.Īre some timings 3 of how the Machin and the Gauss arctan formulaįared, with and without the accelerated arctan. Notice how we pre-calculate as many things as possible (like X_squared_plus_1 = x_squared 1 term = (x * one) // x_squared_plus_1 These, which are named after their inventors:Ĭalculate arctan(1/x) using euler's accelerated formula Well the answer is yes! Firstly there are better arctan formulae.Īmazingly there are other formulae which will calculate π too, like Previous calculation with the decimal module in Part So how does this work in practice? On my machine it calculates 100ĭigits of π in 0.18 ms which is over 30,000 times faster than the The number of iterations which again will be small. X_squared will be 5² = 25 or 239² = 57121 and divisor will be 2 * Both of these will be dividing by small numbers, In the loop there are two divisions, power // x_squaredĪnd power // divisor. If you don't use this then python will make floating point Note the use of the // operator which does integerĭivisions. You can think of it as representing 1 in the fixed pointĪrithmetic world. The value one passed in is the multiplication factor as describedĪbove. """ power = one // x # the /- 1/x**n part of the term total = power # the total so far x_squared = x * x # precalculate x**2 divisor = 1 # the 1,3,5,7 part of the divisor while 1: This calculates it in fixed point, using the value for one passed in The definition of the arctan(1/x) function then looks like this:Īrctan(1/x) = 1/x - 1/3*x**3 1/5*x**5. Technique known as fixed point arithmetic. This needs a little bit of care, but is a well known Should shift the decimal place 100 places to the left when done to get We then do all our calculations with integers, knowing that we The way we do that is to multiply everything by a large number, lets sayġ0 100. Represent the current term in a int 1 then we could use this speedyĭivision to greatly speed up the calculation. In fact if you are dividingĪn N digit number by an M digit number it takes rougly N*M operations.ĭozens of divisions of 200 digit numbers. The key to making a much faster π algorithm. We called this short division at school, and that is ![]() However it is much easier to divide a short number (a single digit) intoĪ 100 digit number. You can imagine from your experiences with long division at school! Dividing two 100 digit numbers is hard work as I'm sure Arctan(1/x) = \frac - \cdots ( x >= 1 )Įach term in the series is created by dividing the previous term by a
0 Comments
Leave a Reply. |