Closure/GoogleIO/C#/Algorithm/SL/and more…

Project Euler problem 66~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_pells_equation_with_continued_fractions_and_convergents);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// armed with the research results and solutions from problem 64 and 65(basically this problem is 
 16:         /// a combination of 64 and 65 code). 
 17:         /// base on this page http://en.wikipedia.org/wiki/Pell%27s_equation, the convergents serve as x and y in the 
 18:         /// equation, finding the first convergent that produces x and y that can solve the equation is the minimum x and y.
 19:         /// since i havent wrote a compare and substract method for the array base int. so i just use .net 4.0 BigInteger
 20:         /// implementation. (will update with array base int solution later)
 21:         /// </summary>
 22:         static int using_pells_equation_with_continued_fractions_and_convergents()
 23:         {
 24:             var limit = 1000;
 25:             var bound = (int)Math.Sqrt(limit);
 26:             var map = new bool[limit + 1];
 27:             BigInteger result = 0;
 28:             BigInteger tmp;
 29:             int largest = 0;
 30:             
 31:             for (int i = 0; i < limit; i++)
 32:             {
 33:                 if (i <= bound)
 34:                     map[i * i] = true; // using this way to mark perfect squares
 35: 
 36:                 if (map[i] == false) // perfect squares are skipped
 37:                 {
 38:                     tmp = find_convergent(i);
 39:                     if (result < tmp)
 40:                     {
 41:                         result = tmp;
 42:                         largest = i;
 43:                     }
 44:                 }
 45:             }
 46:             return largest;
 47:         }
 48: 
 49:         static BigInteger find_convergent(int i)
 50:         {
 51:             // for finding a0,a1,a2......
 52:             var a0 = (int)Math.Sqrt(i);
 53:             var m = 0;
 54:             var d = 1;
 55:             var a = a0;
 56: 
 57:             // for finding convergent
 58:             BigInteger h_2 = 0; 
 59:             BigInteger h_1 = 1; 
 60:             BigInteger h = a * h_1 + h_2;
 61:             BigInteger k_2 = 1;
 62:             BigInteger k_1 = 0;
 63:             BigInteger k = a * k_1 + k_2;
 64:             BigInteger approx = 0;
 65:             while (true)
 66:             {
 67:                 m = d * a - m;
 68:                 d = (i - m * m) / d;
 69:                 a = (a0 + m) / d;
 70: 
 71:                 h_2 = h_1;
 72:                 h_1 = h;
 73:                 h = a * h_1 + h_2;
 74: 
 75:                 k_2 = k_1;
 76:                 k_1 = k;
 77:                 k = a * k_1 + k_2;
 78:                 approx = h * h - i * k * k;
 79: 
 80:                 if (approx == 1) // so minimal x is found
 81:                     return h;
 82:             }
 83:         }
 84: 
 85:         static Stopwatch stopwatch = new Stopwatch();
 86:         static void TestBenchSetup()
 87:         {
 88:             // Uses the second Core or Processor for the Test
 89:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 90:             // Prevents "Normal" processes from interrupting Threads
 91:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 92:             // Prevents "Normal" Threads from interrupting this thread
 93:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 94:         }
 95:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 96:         static void TestBenchLoader(Func<int> test_method)
 97:         {
 98:             stopwatch.Reset();
 99:             stopwatch.Start();
100:             long result = 0;
101:             long avg_tick = 0;
102:             long avg_ms = 0;
103:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
104:             // stabilizes the CPU cache and pipeline.
105:             {
106:                 result = test_method(); // Warmup
107:             }
108:             stopwatch.Stop();
109:             for (int repeat = 0; repeat < 20; ++repeat)
110:             {
111:                 stopwatch.Reset();
112:                 stopwatch.Start();
113:                 result = test_method();
114:                 stopwatch.Stop();
115:                 avg_tick += stopwatch.ElapsedTicks;
116:                 avg_ms += stopwatch.ElapsedMilliseconds;
117:             }
118:             avg_tick = avg_tick / 20;
119:             avg_ms = avg_ms / 20;
120:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
121:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
122:         }
123:     }

c++ (under construction)

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s