Is this number a perfect square?

When solving an algorithm problem, the size of the input will likely dictate the approach to be taken to solve it. For the following problem: "determine whether the number N is a perfect where N is <= 1,000,000. You can't use the SQRT operator", you can solve it by writing a simple O(N) loop. However, if the problem statement has N equals to this number:

165427932084831047046609078136342385692486778784193040575415275237601141991915477442845407673976779988232591513989058207150
467947523250038046743349535213521742642331376230769593309027187809744543689481194688348037467758678555486040607128113607782
083765614731180084729138856439466527641625533551140106381117226415600300034739904992269491478944475237827791509015498086952
540122244942342301906037349725404262930038509928927062527110279498414480102632727349285397856356384385317530337640402344225
257713111998890184844181150362794164888726083850881120857078821273038738588588961135056057777457454067942853805232017960397
050978282050240191161275882625340545212046053301789937251365351417557092804151385075718501245599282033350446561924254192091
369795348600116773792501535164938937988045822175670418981501598859205041941367469757259417288920323424307954390472898807024
169866780317563095596730093961453540231766035422026363095231945382670048030322566319763733609680577338280082965098102753044
938539186285154045953674169373914742467656886829914286825370454961565065712545956696734216204413321639282355852267935369390
44505866991230361009997941512327874199719123344

Then it is a different matter altogether. Such a problem should automatically trigger the most common time-complexities and their relationships:

O(1) < O(lgN) < O(lgN*lgN) < O(sqrt(N)) < O(N) < O(N*lgN) < O(N*N)

We know that O(N) won't work for the above input, hence we need to evaluate the other options less than O(N). O(sqrt(N)) won't work either as the square root of such a big number will remain a big, intractable number (intractable from a Big-O standpoint). This post will solve this problem using a O(lgN) algorithm. That would be suitable for our input size. I did not count how many digits there are in N, but let's suppose that it contains 1,000,000 digits (which it doesn't), in this case lg(10^1,000,000) ~= 4,000,000. Hence to solve the problem we'd need a for-loop with 4,000,000 iterations. Runs in a blink of an eye.

The most common O(lgN) algorithm is a binary search whereas on each iteration of the algorithm we cut the search space by half (remember that the notation "lgN" refers to the logarithm of N on base 2, whereas "logN" refers to the logarithm of N on base e, and logK(N) is the logarithm of N on base K). To solve the problem using binary search, we first find the lower and upper bounds for the search. We can do that by finding two perfect squares, one before N and one after N, relatively close together. That operation takes O(lgN). Next comes the binary search itself. We cut down the search by half at each step, and at the end either we'll find the square root of N, or the lower boundary will cross the upper boundary, we halt, and the number is not a perfect square. We make use of the BigInteger C# class for convenience. Here is the code:

        public static bool IsPerfectSquareBS(BigInteger n,

                                             ref BigInteger sqr)

        {

            sqr = -1;

            if (n < 0)

            {

                return false;

            }

            else if(n == 0 || n == 1)

            {

                sqr = n;

                return true;

            }

            //Find the lower and upper limits

            BigInteger lower = 1;

            BigInteger upper = 2;

            while(n < (lower * lower) || n > (upper * upper))

            {

                lower = upper;

                upper *= upper;

            }

            //Binary search

            while (lower + 1 < upper)

            {

                BigInteger mid = (lower + upper) / 2;

                BigInteger midSq = mid * mid;

                if (midSq == n)

                {

                    sqr = mid;

                    return true;

                }

                else if (midSq > n)

                {

                    upper = mid;

                }

                else

                {

                    lower = mid;

                }

            }

            return false;

        }
 
The answer to the original problem is yes, that number is a perfect square, and its square root is this one:

406728327123684670272930339169392162537633039383763635353442424384940383635112526326364646565768768797979808089897976867634
783749384937597485838392930832498748564857938430923028494856487594384039230394584584758456387483492830283497485684759394029
403586485783948932893028494758465873498320390238937583487329389282982981992939249349374938042343483948374837483749283934837
493894865757456464654545343432323131423535464657657687698798037328374364537327464646282983937454736319204644648364820298465
4732943747648374643837646362555515325337741359876723359467901178556591424572448536812