lawl~

Project Euler problem 71~

c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The the numerator of the fraction immediately to the left of 3/7: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(test_each_fraction_with_denominator_within_range);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically just test each fracion a/b such that x/d = 3/7, where
 16:         /// d = 9,10,11...1mil
 17:         /// x can be calculated by x = (3*b)/7.
 18:         /// also, since this problem only ask for reduced form. so dont need to worry about where x/d is really 3/7
 19:         /// </summary>
 20:         static int test_each_fraction_with_denominator_within_range()
 21:         {
 22:             var ratio_n = 3;
 23:             var ratio_d = 7;
 24:             var limit = 1000000;
 25:             long max_n = 2;
 26:             long max_d = 5;
 27:             var n = 0;
 28:             for (int d = limit - 1; d > 8; d--) // ends before 8, since the question already stated 1 to 8
 29:             {                                   // also, starting from highest, the higer the number, the closer to the ratio
 30:                 n = (ratio_n * d) / ratio_d;
 31: 
 32:                 if (max_n * d < max_d * n && find_GCD(n, d) == 1) //no going keep trying n, where n-1, n-2, n-3...
 33:                 {
 34:                     max_n = n;
 35:                     max_d = d;
 36:                 }
 37:             }
 38:             return (int)max_n;
 39:         }
 40: 
 41:         /// <summary>
 42:         /// Euclid's algorithm for finding gcd
 43:         /// </summary>
 44:         static int find_GCD(int x, int y)
 45:         {
 46:             while (x > 0)
 47:             {
 48:                 y = y % x;
 49:                 y = y + x; // the next three lines is just swapping x and y
 50:                 x = y - x;
 51:                 y = y - x;
 52:             }
 53:             return y;
 54:         }
 55: 
 56:         static Stopwatch stopwatch = new Stopwatch();
 57:         static void TestBenchSetup()
 58:         {
 59:             // Uses the second Core or Processor for the Test
 60:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 61:             // Prevents "Normal" processes from interrupting Threads
 62:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 63:             // Prevents "Normal" Threads from interrupting this thread
 64:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 65:         }
 66:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 67:         static void TestBenchLoader(Func<int> test_method)
 68:         {
 69:             stopwatch.Reset();
 70:             stopwatch.Start();
 71:             var result = 0;
 72:             long avg_tick = 0;
 73:             long avg_ms = 0;
 74:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 75:             // stabilizes the CPU cache and pipeline.
 76:             {
 77:                 result = test_method(); // Warmup
 78:             }
 79:             stopwatch.Stop();
 80:             for (int repeat = 0; repeat < 20; ++repeat)
 81:             {
 82:                 stopwatch.Reset();
 83:                 stopwatch.Start();
 84:                 result = test_method();
 85:                 stopwatch.Stop();
 86:                 avg_tick += stopwatch.ElapsedTicks;
 87:                 avg_ms += stopwatch.ElapsedMilliseconds;
 88:             }
 89:             avg_tick = avg_tick / 20;
 90:             avg_ms = avg_ms / 20;
 91:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 92:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 93:         }
 94:     }

c++

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