inport math,time

#=========================================================#
#  Compute sqrt(2) by python with int                     #
#    Reciprocal Newton's method                           #
#      x = x + x*(1 - x*x/2) / 2                          #
#    compute m digits for n digits (input)                #
#      n < m < 2n : m=12*2^(int(log2(n/12)))              #
#---------------------------------------------------------#
#  copy right : Ushiro Yasunori (ISCPC)                   #
#    date : 2020/02/09                                    #
#=========================================================#
def sqrt2(n):
   bit, dec = 40, 12                      # 2^40 > 10^12
   d12 = 10000*10000*10000                # 10^12
   x = int( math.sqrt(2)*(1 << bit) )     # initial sqrt(2)
   while dec <= n:                        # compute n digits
      dec = dec << 1                      # dec=2*dec
      d2  = 1 << (2*bit)                  # d2=2^(2*bit)
      x0  = (x*x) >> 1                    # x0=x^2/2
      x1  = (d2 - x0) >> 1                # x1=(1-x0)/2
      x2  = (x*x1) >> bit
      x   = (x << bit) + x2 + 1           # x=x+x*x1+round
      bit = 2*bit
      d12 = d12*d12
   x = (x*d12) >> bit                     # hex to decimal
   print("compute digits =",dec)
   dec_o = (n // 100)*100                 # output digits
   print("output digits =",dec_o)
   return x

#=========================================================#
#  file output sqrt(2) by python                          #
#    output file: sqrt.txt : n digits by 100 digits       #
#      if n <= 1000: print n digit                        #
#---------------------------------------------------------#
#  copy right : Ushiro Yasunori (ISCPC)                   #
#    date : 2020/02/09                                    #
#=========================================================#
def out_sq2(n):
   fo = open("sqrt.txt", "w")
   t1 = time.time()
# x_dec = sqrt(2)-1
   x_dec = sqrt2(n)
   t2 = time.time()
   t_comp = "{:.2f}".format(t2-t1)
   print("compute time = "+t_comp+" (s)")
# change decimal 
   x_char = format(x_dec)
   t3 = time.time()
   t_dec  = "{:.2f}".format(t3-t2)
   print("decimal time = "+t_dec+" (s)")
# print for small digits
   if n <= 1000:
      print("sqrt(2)= 1.")
      print(x_char[1:n])
# write file
   fo.write("compute "+format(n)+" digits sqrt(2)\n")
   fo.write("sqrt(2) = 1.\n")
   lp = n // 100
   for k in range(lp):
      j = 100*k + 1
      fo.write(x_char[j:j+99]+" : "+format(j)+"\n")
# output time
   fo.write("compute time = "+t_comp+" (s)\n")
   fo.write("decimal time = "+t_dec+" (s)\n")
   fo.close

#=========================================================#
#  Compute sqrt(2) by python with int                     #
#    type in : digits                                     #
#    output file: sqrt.txt                                #
#---------------------------------------------------------#
#  copy right : Ushiro Yasunori (ISCPC)                   #
#    date : 2020/02/09                                    #
#=========================================================#
print("type in compute-digits")
n = int(input(">>"))
out_sq2(n)                       # output sqrt(2)