Find the square root of an integer with trigonometry and Lagrange’s four-square theorem
My friend was solving the following problem during a interview for Citigroup’s IT department.
Find the square root of a integer n, without using the built in sqrt function. (The range of the result was not specified, I assume it’s double)
This is a common interview question.
There are many ways to do it. I want to come up with a way no one else would think of, something that could amaze the interviewer. I mean, she might interviewed enough people to get bored with the standard answers.
I present the following highly inefficient but somewhat creative solution. The code is here.
How does it work?
We know is an integer. By Lagrange’s four-square theorem, for integer . . Thus is the magnitude of the vector . can be calculated by brute force search(therefore runs in time).
Note a simple improvement of the naive algorithm can reduce the computation time to by doing a binary search for the last square.
A much smarter randomized algorithm by Michael O. Rabin and Jeffrey Shallit have a running time of .
A recursive algorithm using the following relation can find the magnitude of any vector(assume ) It’s easy to see, this breaks a -dimension vector into orthogonal vectors of -dimensions and -dimension. We get a right triangle. Trigonometry comes in handy.