How can I find the largest perfect square in a really big number.

Question

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?

Answer 1

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\;$.

Answer 2

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.

Answer 3

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$.