# -*- coding: utf-8 -*-
#
# 平方根を求めるプログラム
# Writtend by T'z Factory Co.,Ltd
# Ver 1.0  2018/05/25
# Ver 1.1  2018/06/04  Python2系に対応するため、copy属性をlist関数に書き換え。表示を一部sys.stdout関数に書き換え
# Ver 1.2  2018/06/15  桁上がり候補を求める部分をマルチプロセス化
# Ver 1.3  2018/06/20  配列を文字列型から整数型へ変更
# Ver 2.0  2018/06/21  開平法のアルゴリズムを実装
# Ver 2.1  2018/06/21  x-a^2=b(2a+b)のb候補を求める部分をマルチプロセス化

#==========================================
# インポートモジュール
#==========================================
try:
  import datetime, logging, os, sys, time
  from multiprocessing import Pool

except ImportError:
  print('必要なモジュールをインポートできませんでした。環境を確認してください。')
  sys.exit()

#==========================================
#変数定義
#==========================================

SEP =  '---------------'

#==========================================
# 上位桁から有効数字までの'0'を削除する
#==========================================
def zerosupress(a):
  i = len(a)
  if i < 3:
    return(a)
  j = 0
  while (i > 0 and j < 1):
    if a[i-1] == 0:
      a.pop()
    else:
      j += 1
    i -= 1
  i = len(a)
  if a[i-1] == '.':
    a.append(0)
  return(a)

#==========================================
# 配列同士の足し算
#==========================================
def add(a1, a2):
  a = list(a1)
  b = list(a2)

# 小数点以下の桁数を合わせる
  p = a.index('.') - b.index('.')
  if p > 0:
    for i in range(p):
      b.insert(0, 0)
  if p < 0:
    for i in range(-p):
      a.insert(0, 0)

# 整数部分の桁数を合わせる
  p = (len(a) - a.index('.')) - (len(b) - b.index('.'))
  if p > 0:
    for i in range(p):
      b.append(0)
  if p < 0:
    for i in range(-p):
      a.append(0)
  l_a = len(a)

# 和格納用配列初期化
  c = []
  for i in range(l_a + 1):
    c.append(0)

# キャリー初期化
  cy = 0

# 計算
  for i in range(l_a):
    if a[i] == '.':
      c[i] = '.'
    else:
      t = a[i] + b[i] + cy
      if t > 9:
        cy = 1
        t -= 10
      else:
        cy = 0
      c[i] = t

# 最後のキャリーを足し込む
  if cy == 1:
    c[i + 1] = cy
  return(zerosupress(c))

#==========================================
# 配列同士の引き算
#==========================================
# a1 - a2
#==========================================
def sub(a1, a2):
  a = list(a1)
  b = list(a2)

# 小数点以下の桁数を合わせる
  p = a.index('.') - b.index('.')
  if p > 0:
    for i in range(p):
      b.insert(0, 0)
  if p < 0:
    for i in range(-p):
      a.insert(0, 0)

# 整数部分の桁数を合わせる
  p = (len(a) - a.index('.')) - (len(b) - b.index('.'))
  if p > 0:
    for i in range(p):
      b.append(0)
  if p < 0:
    for i in range(-p):
      a.append(0)
  l_a = len(a)

# 差格納用配列初期化
  c = []
  for i in range(l_a + 1):
    c.append(0)

# ボロー初期化
  br = 0

# 計算
  for i in range(l_a):
    if a[i] == '.':
      c[i] = '.'
    else:
      t = a[i] - b[i] - br
      if t < 0:
        br = 1
        t += 10
      else:
        br = 0
      c[i] = t
  return(br, zerosupress(c))

#==========================================
# 配列同士の掛け算
#==========================================
def multi(a1, a2):
  a = list(a1)
  b = list(a2)

# ピリオドを一旦最下位に移動（整数化）
  p_a = a.index('.')
  p_b = b.index('.')
  a.pop(p_a)
  b.pop(p_b)
  a.insert(0, '.')
  b.insert(0, '.')
  l_a = len(a)
  l_b = len(b)
  l_d = l_a - l_b
  l_p = l_a + l_b

# 桁数を合わせる
  if l_d > 0:
    for i in range(l_d):
      b.append(0)
  if l_d < 0:
    for i in range(-l_d):
      a.append(0)
  l_a = len(a)

# 積格納用配列初期化
  d = []
  for i in range(l_p):
    d.append(0)
  d.insert(0, '.')

# 計算
  for i in range(1, l_a):

# 和格納用配列初期化
    c = []
    for j in range(1, l_a):
      c.append(0)
    c.insert(0, '.')
    for k in range(int(b[i])):
      c = add(c, a)
    c.pop(0)
    for k in range(1, i):
      c.insert(0, 0)
    c.insert(0, '.')
    d = add(d, c)
  d.pop(0)
  d.insert(p_a + p_b, '.')
  return(zerosupress(d))

#==========================================
# 配列同士の比較
#==========================================
# 戻り値
# a1 > a2 -- 2
# a1 < a2 -- 1
# a1 = a2 -- 0
# エラー --- -1
#==========================================
def compare(a1, a2):
  a = list(a1)
  b = list(a2)

# 小数点以下の桁数を合わせる
  p = a.index('.') - b.index('.')
  if p > 0:
    for i in range(p):
      b.insert(0, 0)
  if p < 0:
    for i in range(-p):
      a.insert(0, 0)

# 整数部分の桁数を合わせる
  p = (len(a) - a.index('.')) - (len(b) - b.index('.'))
  if p > 0:
    for i in range(p):
      b.append(0)
  if p < 0:
    for i in range(-p):
      a.append(0)
  l_a = len(a)
  r = -1

# 比較
  for i in range(l_a):
    j = l_a - i - 1
    if a[j] > b[j]:
      r = 2
      break
    if a[j] < b[j]:
      r = 1
      break
    if a[j] == b[j]:
      r = 0
  return(r)

#==========================================
# 計算結果を表示
#==========================================
def display(a):
  if len(a) == 0:
    return(False)
  l_a = len(a)
  for i in range(l_a):
    j = l_a - i - 1
    if j > 0:
      b = a[j]
    if j == 0 and a[j] == '.':
      b = ' '
    else:
      b = a[j]
    sys.stdout.write(str(b))
  print('\r')
  
#==========================================
# 候補値を計算し比較結果を返す
#==========================================
# cx -- b(2a+b)
# dx --- (x-a^2)-b(2a+b)
# k  --- b
#==========================================
def zcandidate(dx, cx, k):

  cx.insert(1, k)
  cx1 = multi(cx, ['.', k])
  r = compare(dx, cx1)
  (br, dx2) = sub(dx, cx1)
  cx = add(cx, ['.', k])

  return(r, dx2, cx)

#==========================================
# ラッパー
#==========================================
def wrap_zc(args):
  return(zcandidate(*args))

#==========================================
# 平方根の計算（開平法）
#==========================================
# x -- 平方根を求める値
# c -- 求める平方根の桁数
#==========================================
def sqrt(x, c, disp):

  max_proc = 10
  pool = Pool(max_proc)

# 加算値
  p = ['.', 1]

  l_x = len(x) - 1

  if c % 2 != 0:
    c += 1

  l_p = (c - 1) * 2
  p_x = x.index('.')
  x.pop(p_x)

  for i in range(l_p):
    x.insert(0, 0)
  x.insert(0, '.')

# 1桁目を求める

# 平方根の初期値
  z = ['.', 0]
  x_1 = x[len(x)-1:]
  x_1.insert(0, '.')

  while True:
    r = compare(x_1, multi(z, z))
    if r == 2:
      z1 = list(z)
      z = add(z, p)
    else:
      break

  if r == 0:
    return(zerosupress(z))
  z = zerosupress(z1)
  i = len(x) - 2
  cx = add(z, z)

# dx・・筆算途中値
# br・・引き算ボロー
  (br, dx) = sub(x_1, multi(z, z))
  dx = zerosupress(dx)

  if br > 0:
    print('1桁目の計算エラー')
    sys.exit()
  z.insert(0, '.')
# 2桁目以降を求める

  while i > 0:

# 平方値の対象ブロックを切り出し
    dx.insert(1, x[i-1])
    dx.insert(1, x[i-2])

    zcargs = [(dx, cx, 0), (dx, cx, 1), (dx, cx, 2), (dx, cx, 3), (dx, cx, 4), (dx, cx, 5), (dx, cx, 6), (dx, cx, 7), (dx, cx, 8), (dx, cx, 9)]
    zcr = pool.map(wrap_zc, zcargs)

    j = 0
    while j < 10:
      if zcr[j][0] == 2:
        j += 1
      else:
        j -= 1
        break

    if j == 10:
      j -= 1

    dx = zcr[j][1]
    cx = zcr[j][2]
    z.insert(1, j)

    if disp == 'y':
      print(SEP)
      sys.stdout.write('cx=')
      display(cx)
      sys.stdout.write('dx=')
      display(dx)
      sys.stdout.write('z =')
      display(z)
      print(SEP)

    i -= 2
    if i % 20 == 0:
      print( '%d桁目の計算結果です。' % (int(c-(i+2)/2+1)))
      print('\r')
      display(z)
      print('------------------------------')
  return(z)

#==========================================
# メイン
#==========================================
if __name__ == '__main__':
  try:
    xi = list(str(sys.argv[1]))
    c = int(sys.argv[2])
    x_len = len(xi)
    if c == 0:
      raise exception

  except:
    print('計算回数を入力してください')
    print('Usage: sqrt.py x digit-count display-process(y/-)')
    sys.exit()

  disp = 'n'

  try:
    disp = str(sys.argv[3])

  except:
    pass

  x = []
  y = []
  p = 0
  for i in range(x_len):
    if xi[i] == '.':
      p += 1
    x.insert(0, int(xi[i]))

# 1桁に限定
  if len(x) > 1:
    print('1桁の数値を入力してください')
    sys.exit()

# ピリオドが2個以上ならエラー
  if p > 1:
    print('入力した数字が誤っています')
    sys.exit()

# ピリオドが含まれていない場合は最終桁にピリオドを追加する
  if p == 0:
    x.insert(0, '.')

# 計算開始時刻を記録
  print(SEP + SEP)
  st = datetime.datetime.now()
  sys.stdout.write('計算開始時刻：')
  print(str(st))
  print(SEP + SEP)

# 平方根を計算
  y = sqrt(x, c, disp)

# 計算終了時刻を記録
  et = datetime.datetime.now()

# 表示
  print('\r')
  print(SEP + '結果' + SEP)
  display(y)
  print(SEP + '----' + SEP)

# 終了処理

  print('\r')
  print('\r')
  sys.stdout.write('計算開始時刻：')
  print(str(st))
  sys.stdout.write('計算終了時刻：')
  print(str(et))
  sys.stdout.write('計算時間:     ')
  print(str(et-st))

  sys.exit()