Solution for project euler problem 66

Problem 66

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;

namespace Problem_66
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int max = (int) Math.Sqrt(1000);
            int[] squares = new int[max + 1];
            for (int i = 0; i <= max; i++)
                squares[i] = i*i;

            int dOfLargestX = 0;
            BigInteger largestX = 0;

            for (int d = 1; d <= 1000; d++)
            {
                if (squares.Contains(d))
                    continue;
                Convergent convergent = FindConvergent(d);
                if (convergent.Numerator != 0)
                {
                    if (convergent.Numerator > largestX)
                    {
                        largestX = convergent.Numerator;
                        dOfLargestX = d;
                    }
                }
                else
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                    Console.WriteLine("Did not solve {0}.", d);
                    Console.ForegroundColor = ConsoleColor.Gray;
                }
            }

            sw.Stop();
            Console.WriteLine("The largest X was {0} found with D{1}", largestX, dOfLargestX);
            Console.WriteLine("Took {0} ms.", sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
        static bool SolvesDiophantineEquation(BigInteger x, BigInteger y, BigInteger d)
        {
            return x * x - (d * y * y) == 1;
        }
        static int pow = 1000;
        private static BigInteger multi = BigInteger.Pow(10, pow);
        private static BigInteger squaredMulti = multi*multi;
        static Convergent FindConvergent(int d)
        {
            
            List<Convergent> convergents = new List<Convergent>() {new Convergent{Numerator=0,Denominator=1},new Convergent {Numerator = 1, Denominator = 0}};
            BigInteger r = Sqrt(d*multi);
            r *= multi;
            r /= BigInteger.Pow(10, pow/2);
            while(true)
            {
                BigInteger integerPart = (r/multi)*multi;
                BigInteger fractional = r - integerPart;

                BigInteger numerator = convergents[convergents.Count - 1].Numerator * integerPart/multi + convergents[convergents.Count - 2].Numerator;
                BigInteger denominator = convergents[convergents.Count - 1].Denominator * integerPart/multi + convergents[convergents.Count - 2].Denominator;

                convergents.Add(new Convergent {Numerator = numerator, Denominator = denominator});
                if (SolvesDiophantineEquation(numerator, denominator, d))
                    return convergents.Last();
                if (fractional == 0)
                    break;
               
                BigInteger reciprocal = squaredMulti/fractional;
                r = reciprocal;
            }

            return new Convergent {Numerator = 0, Denominator = 0};
        }
        struct Convergent
        {
            public BigInteger Numerator;
            public BigInteger Denominator;
        }
        //copy pasted from http://stackoverflow.com/questions/3432412/calculate-square-root-of-a-biginteger-system-numerics-biginteger
        public static BigInteger Sqrt(BigInteger n)
        {
            if (n == 0) return 0;
            if (n > 0)
            {
                int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2)));
                BigInteger root = BigInteger.One << (bitLength / 2);

                while (!isSqrt(n, root))
                {
                    root += n / root;
                    root /= 2;
                }

                return root;
            }

            throw new ArithmeticException("NaN");
        }
        private static Boolean isSqrt(BigInteger n, BigInteger root)
        {
            BigInteger lowerBound = root * root;
            BigInteger upperBound = (root + 1) * (root + 1);

            return (n >= lowerBound && n < upperBound);
        }
        //end of copy paste
    }
}