_04b_intsqrt Namespace Reference

Finding int(sqrt) of a given number, by using Newton's Method. More...

Functions
def	intsqrt (n)
	Calculates the integer part of the square root of a long. More...
def	isqrt (n)
	Python 3.8. More...
def	main (argv=None)

Detailed Description

Finding int(sqrt) of a given number, by using Newton's Method.

\[x_{n+1} = x_n - \frac {f(x_n)} {f'(x_n)}.\]

Consider \(x^{2} - n = 0\), which gives us the following recursive formula:

\begin{eqnarray*} x_{k+1} &=& 1/2 (x_{k} + \frac{n}{x_{k}}), k >= 0, x_{0} > 0, \\ x_{0} &=& n. \end{eqnarray*}

Stopping condition: \(| x_{k+1} - x_{k} | < 1\)

Author

Paulo Roma

Since

04/01/2009

See also

http://www.duke.edu/~dga2/cps149s/

http://programmingpraxis.com/2012/06/01/square-roots/

http://en.wikipedia.org/wiki/Integer_square_root

http://en.wikipedia.org/wiki/Newton's_method

Function Documentation

intsqrt()

def _04b_intsqrt.intsqrt

(

n

)

Calculates the integer part of the square root of a long.

It is applied the Newton method for solving: \(x^{2} - n = 0.\)

Parameters

n	given long.

Returns

\(int(\sqrt{n}).\)

Referenced by _10_factorize2.factorize(), _04a_prime.isPrime(), _10_factorize2.isPrime(), and main().

isqrt()

def _04b_intsqrt.isqrt

(

n

)

Python 3.8.

Parameters

n	given long.

Returns

\(int(\sqrt{n}).\)

See also

https://stackoverflow.com/questions/15390807/integer-square-root-in-python

Referenced by main().

main()

def _04b_intsqrt.main

(

argv = None

)

References intsqrt(), and isqrt().