I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest algorithms for computing square and square root, and how should I be approaching this i.e.
- Computing $\sqrt{y}$ and comparing it with $x$
OR - Computing $x^2$ and comparing it with $y$
So as to write a code that has minimum time complexity.
distances between perfect squares increase
- I don't understand what you want to say. You can compare two numbers in $O(n)$ time. $\endgroup$