The Art Gallery Guardian

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.

Problem1

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 nn is an integer. By Lagrange’s four-square theorem, n=a2+b2+c2+d2n=a^2+b^2+c^2+d^2 for integer a,b,c,da,b,c,d. n=a2+b2+c2+d2\sqrt{n} = \sqrt{a^2+b^2+c^2+d^2}. Thus n\sqrt{n} is the magnitude of the vector [a,b,c,d][a,b,c,d]. a,b,c,da,b,c,d can be calculated by brute force search(therefore runs in O(n2)O(n^2) time).

Note a simple improvement of the naive algorithm can reduce the computation time to O(n32logn)O(n^\frac{3}{2} \log n) 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 O(log2n)O(\log^2 n).

A recursive algorithm using the following relation can find the magnitude of any vector(assume ai0a_i\neq 0) [a0,...,an1,an]=ansin(tan1(an[a0,...,an1]))|[a_0,...,a_{n-1},a_n]| = \frac{a_n}{\sin(\tan^{-1}(\frac{a_n}{|[a_0,...,a_{n-1}]|}))} It’s easy to see, this breaks a nn-dimension vector into orthogonal vectors of n1n-1-dimensions and 11-dimension. We get a right triangle. Trigonometry comes in handy.

Posted by Chao Xu on .
Tags: math.