Wednesday, August 17, 2016

Rounding the k-th root of n

Consider the problem of finding the $k$-th root of a number $n\geq 0$ and rounding it to the nearest integer, i.e. find $[\sqrt[k]{n}]$, where $[x]$ is $x$ rounded to the nearest integer. This can be easily computed in many computer languages using floating point arithmetic, but care must be taken for large $n$ to ensure enough significant digits are available. On the other hand, languages such as Python has built-in support for integers of arbitrary sizes and will automatically allocate more space to fit the number under consideration. This can be used to compute $[\sqrt[k]{n}]$ using only integer arithmetic without worrying whether there are enough precision in the floating point representation.

Let $i$ be the largest integer such that $i \leq \sqrt[k]{n}$. The number $i$ can be computed using integer arithmetic with an iterative Newton's method.
Since $n \geq 0$, $[\sqrt[k]{n}] = i+1$ if $\sqrt[k]{n}-i \geq \frac{1}{2}$ and $[\sqrt[k]{n}] = i$ otherwise. The condition $\sqrt[k]{n}-i \geq \frac{1}{2}$ is equivalent to $2^k n \geq (2i+1)^k$ which can be computed using integer arithmetic.

A simple python function using the gmpy2 module to implement this is the following:

from gmpy2 import iroot
def round_root(n,k): # round(k-th root of n), n >= 0
    i = iroot(n,k)[0]
    return int(i) + int(2**k*n >= (2*i+1)**k)

The gmpy2 module also includes the functions isqrt_rem and iroot_rem. The function isqrt_rem(n)returns a pair of numbers $i,j$ such that $i$ is the largest integer $\leq \sqrt{n}$ and $j = n-i^2$.
Similarly, iroot_rem(n,k)returns a pair of numbers $i,j$ such that $i$ is the largest integer $\leq \sqrt[k]{n}$ and $j = n-i^k$.
\begin{eqnarray*}(2i+1)^k &=& (2i)^k + (2i+1)^{k-1} + \\
&&(2i+1)^{k-2}2i + \cdots + (2i+1)(2i)^{k-2} + (2i)^{k-1}\end{eqnarray*}
the condition can be rewritten as:
\begin{eqnarray*}2^k j  &\geq &(2i+1)^{k-1} + (2i+1)^{k-2}2i + \cdots + (2i+1)(2i)^{k-2} + (2i)^{k-1}\\ & \geq & \sum_{m=0}^{k-1} (2i+1)^{k-1-m}(2i)^m \end{eqnarray*}
For $k=2$, this is reduced to: $4j \geq 4i + 1$. A python function implementing $[\sqrt{n}]$ is:

from gmpy2 import isqrt_rem
def round_sqrt(n): # round(square root of n), n >= 0
    i, j = isqrt_rem(n)
    return int(i) + int(4*(j-i) >= 1)

Similarly, for $k=3$, the condition is reduced to $8j \geq 6i(2i+1)+1$.

No comments:

Post a Comment