#!/usr/bin/env python # coding: UTF-8 # ## @package _04b_intsqrt # Finding int(sqrt) of a given number, by using Newton's Method. # # @f[x_{n+1} = x_n - \frac {f(x_n)} {f'(x_n)}.@f] # # Consider @f$x^{2} - n = 0@f$, which gives us the following recursive formula: # @f{eqnarray*}{ # x_{k+1} &=& 1/2 (x_{k} + \frac{n}{x_{k}}), k >= 0, x_{0} > 0, \\ # x_{0} &=& n. # @f} # Stopping condition: @f$| x_{k+1} - x_{k} | < 1@f$ # # @author Paulo Roma # @since 04/01/2009 # @see http://www.duke.edu/~dga2/cps149s/ # @see http://programmingpraxis.com/2012/06/01/square-roots/ # @see http://en.wikipedia.org/wiki/Integer_square_root # @see http://en.wikipedia.org/wiki/Newton's_method import sys ## # Calculates the integer part of the square root of a long. # It is applied the Newton method for solving: @f$x^{2} - n = 0.@f$ # # @param n given long. # @return @f$int(\sqrt{n}).@f$ # def intsqrt(n): r = n rnew = (r + 1) // 2 while rnew < r: r = rnew rnew = (r + n // r) // 2 # integer division return r ## Python 3.8 # # @param n given long. # @return @f$int(\sqrt{n}).@f$ # @see https://stackoverflow.com/questions/15390807/integer-square-root-in-python def isqrt(n): if n > 0: x = 1 << (n.bit_length() + 1 >> 1) while True: y = (x + n // x) >> 1 if y >= x: return x x = y elif n == 0: return 0 else: raise ValueError("square root not defined for negative numbers") def main(argv=None): if argv is None: argv = sys.argv if len(argv) < 2: print("One argument is needed.") return 1 else: if not argv[1].isdigit(): print("A positive integer is expected.") return 1 n = int(argv[1]) print("intsqrt({}) = {}".format(n,intsqrt(n))) print("isqrt({}) = {}".format(n,isqrt(n))) return 0 if __name__ == "__main__": sys.exit(main())