Create a program that calculates the parallel roots of 2 in millions of digits with python. The calculation method uses the following Newton iterative method for the reciprocal. Iterative: x = x + x * (1-x * x / 2) / 2 The feature of this method is that there is no multi-digit division. The n-digit calculation part in python is below. def sqrt2(n): bit, dec = 40, 12 d12 = 100001000010000 x = int( math.sqrt(2)(1 << bit) ) while dec <= n: dec = dec << 1 d2 = 1 << (2bit) x0 = (xx) >> 1 x1 = (d2 - x0) >> 1 x2 = (xx1) >> bit x = (x << bit) + x2 + 1 bit = 2bit d12 = d12d12 x = (x*d12) >> bit dec_o = (n // 100)*100 return x
format (x) is required to convert the calculation result of x = sqrt2 (n) to a decimal number. The entire python is posted in the python program section at https://ecc-256.com. Download sqrt2 and change sqrt2.py and the first import to import. Type python sqrt2.py at the command prompt. Next, enter the number of output digits. 1000000 for 1 million digits
The calculation time of 3 million, 6 million, 12 million of windows 10 personal computer (4 Ghz) is as follows. x=sqrt(n) : 6.7, 19.9, 59.7 (s) format(x) : 136, 545, 2180 (s)
Decimal conversion for output takes much longer than the calculation of sqrt (2). sqrt (2) takes twice as many digits and three times as long, and decimal conversion takes four times as long. The calculation multiplication is the Karatsuba method, and the conversion multiplication is due to the definition formula.
Even in python, it can be speeded up by scaling with about 1000 decimal digits (value is binary int) and applying high-speed remainder conversion (FMT). The goal is to calculate 100 million digits and convert it to decimal characters within 3 minutes on a 4Ghz personal computer (end of February).
Recommended Posts