Algorithm using Newton.27s method Integer square root
1 algorithm using newton s method
1.1 using integer division
1.2 domain of computation
1.3 stopping criterion
algorithm using newton s method
one way of calculating
n
{\displaystyle {\sqrt {n}}}
,
isqrt
(
n
)
{\displaystyle {\mbox{isqrt}}(n)}
use newton s method find solution equation
x
2
−
n
=
0
{\displaystyle x^{2}-n=0}
, giving iterative formula
x
k
+
1
=
1
2
(
x
k
+
n
x
k
)
,
k
≥
0
,
x
0
>
0.
{\displaystyle {x}_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.}
the sequence
{
x
k
}
{\displaystyle \{x_{k}\}}
converges quadratically
n
{\displaystyle {\sqrt {n}}}
k
→
∞
{\displaystyle k\to \infty }
. can proven if
x
0
=
n
{\displaystyle x_{0}=n}
chosen initial guess, 1 can stop as
|
x
k
+
1
−
x
k
|
<
1
{\displaystyle |x_{k+1}-x_{k}|<1}
to ensure
⌊
x
k
+
1
⌋
=
⌊
n
⌋
.
{\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .}
using integer division
for computing
⌊
n
⌋
{\displaystyle \lfloor {\sqrt {n}}\rfloor }
large integers n, 1 can use quotient of euclidean division both of division operations. has advantage of using integers each intermediate value, making use of floating point representations of large numbers unnecessary. equivalent using iterative formula
x
k
+
1
=
⌊
1
2
(
x
k
+
⌊
n
x
k
⌋
)
⌋
,
k
≥
0
,
x
0
>
0
,
x
0
∈
z
.
{\displaystyle {x}_{k+1}=\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {z} .}
by using fact that
⌊
1
2
(
x
k
+
⌊
n
x
k
⌋
)
⌋
=
⌊
1
2
(
x
k
+
n
x
k
)
⌋
,
{\displaystyle \left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,}
one can show reach
⌊
n
⌋
{\displaystyle \lfloor {\sqrt {n}}\rfloor }
within finite number of iterations.
however,
⌊
n
⌋
{\displaystyle \lfloor {\sqrt {n}}\rfloor }
not fixed point of above iterative formula. indeed, can shown
⌊
n
⌋
{\displaystyle \lfloor {\sqrt {n}}\rfloor }
fixed point if , if
n
+
1
{\displaystyle n+1}
not perfect square. if
n
+
1
{\displaystyle n+1}
perfect square, sequence ends in period-two cycle between
⌊
n
⌋
{\displaystyle \lfloor {\sqrt {n}}\rfloor }
,
⌊
n
⌋
+
1
{\displaystyle \lfloor {\sqrt {n}}\rfloor +1}
instead of converging. termination, suffices check either number has converged or has increased 1 previous step, in case new result discarded.
domain of computation
although
n
{\displaystyle {\sqrt {n}}}
irrational many
n
{\displaystyle n}
, sequence
{
x
k
}
{\displaystyle \{x_{k}\}}
contains rational terms when
x
0
{\displaystyle x_{0}}
rational. thus, method unnecessary exit field of rational numbers in order calculate
isqrt
(
n
)
{\displaystyle {\mbox{isqrt}}(n)}
, fact has theoretical advantages.
stopping criterion
one can prove
c
=
1
{\displaystyle c=1}
largest possible number stopping criterion
|
x
k
+
1
−
x
k
|
<
c
{\displaystyle |x_{k+1}-x_{k}|<c}
ensures
⌊
x
k
+
1
⌋
=
⌊
n
⌋
{\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }
in algorithm above.
in implementations use number formats cannot represent rational numbers (for example, floating point), stopping constant less 1 should used protect against roundoff errors.
Comments
Post a Comment