XNA/C#/Go/OData/and more…

Project Euler problem 64~
c#:

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The numbers of continued fractions for N ≤ 10000 have an odd period: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_iterative_algorithm_to_calculate_continued_fraction_expansion);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// using the formula from
 16:         /// http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion
 17:         /// which made the whole problem pretty simple. bool[] array is used to keep track of perfect square,
 18:         /// since the range is not big(10k), so its fine~
 19:         /// </summary>
 20:         static int using_iterative_algorithm_to_calculate_continued_fraction_expansion()
 21:         {
 22:             var limit = 10000;
 23:             var bound = (int)Math.Sqrt(limit);
 24:             var map = new bool[limit + 1];
 25:             var result = 0;
 26: 
 27:             for (int i = 2; i <= limit; i++)
 28:             {
 29:                 if (i <= bound)
 30:                     map[i * i] = true; // using this way to mark perfect squares
 31: 
 32:                 if (map[i] == false) // perfect squares are skipped
 33:                 {
 34:                     var a0 = (int)Math.Sqrt(i);
 35:                     var m = 0;
 36:                     var d = 1;
 37:                     var a = a0;
 38:                     var counter = -1; // since the 1st iteration is not part of number chains
 39:                     var m1 = int.MinValue; // reset m1 and d1
 40:                     var d1 = int.MinValue;
 41:                     while (true)
 42:                     {
 43:                         counter++;
 44:                         
 45:                         if (counter == 1)
 46:                         {
 47:                             m1 = m; // so these two are marked as head of the period
 48:                             d1 = d;
 49:                         }
 50: 
 51:                         m = d * a - m;
 52:                         d = (i - m * m) / d;
 53:                         a = (a0 + m) / d;
 54: 
 55:                         if (m == m1 && d == d1) // so end of period is found
 56:                             break;
 57:                     }
 58:                     if ((counter & 1) != 0)
 59:                         result++;
 60:                 }
 61:             }
 62:             return result;
 63:         }
 64: 
 65:         static Stopwatch stopwatch = new Stopwatch();
 66:         static void TestBenchSetup()
 67:         {
 68:             // Uses the second Core or Processor for the Test
 69:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 70:             // Prevents "Normal" processes from interrupting Threads
 71:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 72:             // Prevents "Normal" Threads from interrupting this thread
 73:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 74:         }
 75:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 76:         static void TestBenchLoader(Func<int> test_method)
 77:         {
 78:             stopwatch.Reset();
 79:             stopwatch.Start();
 80:             long result = 0;
 81:             long avg_tick = 0;
 82:             long avg_ms = 0;
 83:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 84:             // stabilizes the CPU cache and pipeline.
 85:             {
 86:                 result = test_method(); // Warmup
 87:             }
 88:             stopwatch.Stop();
 89:             for (int repeat = 0; repeat < 20; ++repeat)
 90:             {
 91:                 stopwatch.Reset();
 92:                 stopwatch.Start();
 93:                 result = test_method();
 94:                 stopwatch.Stop();
 95:                 avg_tick += stopwatch.ElapsedTicks;
 96:                 avg_ms += stopwatch.ElapsedMilliseconds;
 97:             }
 98:             avg_tick = avg_tick / 20;
 99:             avg_ms = avg_ms / 20;
100:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
101:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
102:         }
103:     }

c++

  1: int using_iterative_algorithm_to_calculate_continued_fraction_expansion()
  2: {
  3:     int result = 0;
  4:     for (double i = 2; i <= 10000; i++)
  5:     {
  6:         if (is_perfect_square(i) == false) // perfect squares are skipped
  7:         {
  8:             int a0 = (int)sqrt(i);
  9:             int m = 0;
 10:             int d = 1;
 11:             int a = a0;
 12:             int counter = -1; // since the 1st iteration is not part of number chains
 13:             int m1 = INT_MIN; // reset m1 and d1
 14:             int d1 = INT_MIN;
 15:             while (true)
 16:             {
 17:                 counter++;
 18:                 
 19:                 if (counter == 1)
 20:                 {
 21:                     m1 = m; // so these two are marked as head of the period
 22:                     d1 = d;
 23:                 }
 24: 
 25:                 m = d * a - m;
 26:                 d = (i - m * m) / d;
 27:                 a = (a0 + m) / d;
 28: 
 29:                 if (m == m1 && d == d1) // so end of period is found
 30:                     break;
 31:             }
 32:             if ((counter & 1) != 0)
 33:                 result++;
 34:         }
 35:     }
 36:     return result;
 37: }
 38: 
 39: //http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer/295678#295678
 40: int is_perfect_square(int n)
 41: {
 42:     int h = n & 0xF;  // h is the last hex "digit"
 43:     if (h > 9)
 44:         return 0;
 45:     // Use lazy evaluation to jump out of the if statement as soon as possible
 46:     if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
 47:     {
 48:         int t = (int) floor( sqrt((double) n) + 0.5 );
 49:         return t*t == n;
 50:     }
 51:     return 0;
 52: }

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