Let's say I want to find the largest number that when squared doesn't exceed 9223372036854775807. Or any other large number like that. How can I go about finding that? Is there some kind of function that can be applied here?
$\endgroup$ 33 Answers
$\begingroup$For any $N \in \mathbb{N}$ the largest integer $n$ whose square is $n^2 \le N$ is $n = \lfloor \sqrt{N} \rfloor$.
For example $\lfloor \sqrt{9223372036854775807} \rfloor = 3037000499\;$.
$\endgroup$ $\begingroup$To find $\sqrt{N}$, you could use Newton's method on $f(x) = x^2-N$. It should converge pretty fast if $N$ is large. The only snag is that $f(x)$ is concave up, so all the estimates will be too large. You'll have to subtract 1 eventually.
$\endgroup$ $\begingroup$Since $ 9 \cdot 10^{18} < 9223372036854775807 < 16 \cdot 10^{18} $, we can just use bisection on the function $f(x)=x^2-9223372036854775807$ starting with the interval $[3 \cdot 10^{9}, 4 \cdot 10^{9}]$. After about $30$ steps, we get $3037000499$.
$\endgroup$
