Unlocked 100 problems solved achievement~

Project Euler problem 100~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of blue discs that the box would contain: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_recurring_quadratic_Diophantine_equation);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// (where x = blue)
 16:         /// (where y = total disks)
 17:         /// x/y * (x-1)/(y-1) = 1/2
 18:         /// becomes
 19:         /// 2*x^2 - y^2 - 2*x + y = 0
 20:         /// use
 21:         /// http://www.alpertron.com.ar/QUAD.HTM
 22:         /// to get the following:
 23:         /// Xn+1 = P Xn + Q Yn + K 
 24:         /// Yn+1 = R Xn + S Yn + L 
 25:         /// P = 3
 26:         /// Q = 2
 27:         /// K = -2
 28:         /// R = 4
 29:         /// S = 3
 30:         /// L = -3
 31:         /// </summary>
 32:         static long using_recurring_quadratic_Diophantine_equation()
 33:         {
 34:             long x = 85; // from question's description
 35:             long y = 120;
 36:             long x_tmp, y_tmp;
 37:             long limit = 1000000000000L;
 38:             while (y < limit)
 39:             {
 40:                 x_tmp = 3 * x + 2 * y - 2;
 41:                 y_tmp = 4 * x + 3 * y - 3;
 42:                 x = x_tmp;
 43:                 y = y_tmp;
 44:             }
 45:             return x;
 46:         }
 47: 
 48:         static Stopwatch stopwatch = new Stopwatch();
 49:         static void TestBenchSetup()
 50:         {
 51:             // Uses the second Core or Processor for the Test
 52:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 53:             // Prevents "Normal" processes from interrupting Threads
 54:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 55:             // Prevents "Normal" Threads from interrupting this thread
 56:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 57:         }
 58:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 59:         static void TestBenchLoader(Func<long> test_method)
 60:         {
 61:             stopwatch.Reset();
 62:             stopwatch.Start();
 63:             long result = 0;
 64:             long avg_tick = 0;
 65:             long avg_ms = 0;
 66:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 67:             // stabilizes the CPU cache and pipeline.
 68:             {
 69:                 result = test_method(); // Warmup
 70:             }
 71:             stopwatch.Stop();
 72:             for (int repeat = 0; repeat < 20; ++repeat)
 73:             {
 74:                 stopwatch.Reset();
 75:                 stopwatch.Start();
 76:                 result = test_method();
 77:                 stopwatch.Stop();
 78:                 avg_tick += stopwatch.ElapsedTicks;
 79:                 avg_ms += stopwatch.ElapsedMilliseconds;
 80:             }
 81:             avg_tick = avg_tick / 20;
 82:             avg_ms = avg_ms / 20;
 83:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 84:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 85:         }
 86:     }

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