pythonで2の平行根を数百万桁計算するプログラムを作成。
計算方法は逆数に対する下記ニュートン反復法を使用。
反復式 : x = x + x*(1 - x*x/2) / 2
この方式の特徴は多数桁除算が無い。pythonでn桁の計算部分は下記。
def sqrt2(n):
bit, dec = 40, 12
d12 = 10000*10000*10000
x = int( math.sqrt(2)*(1 << bit) )
while dec <= n:
dec = dec << 1
d2 = 1 << (2*bit)
x0 = (x*x) >> 1
x1 = (d2 - x0) >> 1
x2 = (x*x1) >> bit
x = (x << bit) + x2 + 1
bit = 2*bit
d12 = d12*d12
x = (x*d12) >> bit
dec_o = (n // 100)*100
return x
x=sqrt2(n)の計算結果を10進数に変換するにはformat(x)が必要。
全体のpythonは https://ecc-256.com のpythonプログラム欄に掲載。
sqrt2をダウンロードし、sqrt2.pyと先頭のinportをimportに変更する。
コマンドプロンプトでpython sqrt2.pyと打ち込む。
次に、出力桁数を打ち込む。100万桁なら、1000000
windows10のパソコン(4Ghz)の300万,600万,1200万の計算時間は下記。
x=sqrt(n) : 6.7, 19.9, 59.7 (s)
format(x) : 136, 545, 2180 (s)
sqrt(2)の計算より、出力用に10進数変換の方が大幅に時間がかかる。
sqrt(2)は桁数2倍で3倍の時間、10進数変換は4倍の時間がかかる。
計算の乗算はカラツバ法で、変換の乗算は定義式のままが原因。
pythonでも、10進1000桁程度(値は2進のint)で位取りし、高速剰余変換(FMT)を適用すれば高速化可能。1億桁計算し、10進数の文字に変換するまで含めて4Ghzのパソコンで3分以内を目標(2月末)。