back on track

Project Euler problem 101~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of FITs for the BOPs: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_Lagrange_polynomial_to_find_fits);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// using the Lagrange polynomial(http://en.wikipedia.org/wiki/Lagrange_polynomial) to find fits.(thx google!)
 16:         /// the actual coding implementation is bascially compute and store all the numerator portion in (top), and 
 17:         /// denominator portion in (bot), and at the end, combine with nth term from 10th degree poly function from
 18:         /// the question.
 19:         /// the 10th degree poly question can be simplify to such term by:
 20:         /// 1 - n + n^2 - n^3 + n^4 - n^5 + n^6 - n^7 + n^8 - n^9 + n^10
 21:         /// 1 - n(1 - n + n^2 - n^3 + n^4 - n^5 + n^6 - n^7 + n^8 - n^9)
 22:         /// 1 - n(1 - n(1-n......1-n(1-n))))))))...
 23:         /// </summary>
 24:         static long using_Lagrange_polynomial_to_find_fits()
 25:         {
 26:             // calculate the tenth degree polynomial generating function from the question
 27:             Func<int, long> tensPoly = n =>
 28:                 {
 29:                     long seed = 1 - n;
 30:                     for (int i = 0; i < 9; i++)
 31:                     {
 32:                         seed = 1 - n * seed;
 33:                     }
 34:                     return seed;
 35:                 };
 36:             var f = Enumerable.Range(1, 10).Select(n => tensPoly(n)).ToArray();
 37:             // Lagrange interpolating polynomial
 38:             Func<int, long> lagrange = n =>
 39:                 {
 40:                     long nth = 0;
 41:                     for (int i = 0; i < n; i++)
 42:                     {
 43:                         var top = 1;
 44:                         var bot = 1;
 45:                         for (int j = 0; j < n; j++)
 46:                         {
 47:                             if (i != j)
 48:                             {
 49:                                 top *= (n - j);
 50:                                 bot *= (i - j);
 51:                             }
 52:                         }
 53:                         nth += (f[i] * top / bot);
 54:                     }
 55:                     return nth;
 56:                 };
 57:             //  using Lagrange interpolating polynomial to find sum of FITs
 58:             long result = 0;
 59:             for (int i = 1; i < 11; i++)
 60:             {
 61:                 result += lagrange(i);
 62:             }
 63:             return result;
 64:         }
 65: 
 66:         static Stopwatch stopwatch = new Stopwatch();
 67:         static void TestBenchSetup()
 68:         {
 69:             // Uses the second Core or Processor for the Test
 70:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 71:             // Prevents "Normal" processes from interrupting Threads
 72:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 73:             // Prevents "Normal" Threads from interrupting this thread
 74:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 75:         }
 76:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 77:         static void TestBenchLoader(Func<long> test_method)
 78:         {
 79:             stopwatch.Reset();
 80:             stopwatch.Start();
 81:             long result = 0;
 82:             long avg_tick = 0;
 83:             long avg_ms = 0;
 84:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 85:             // stabilizes the CPU cache and pipeline.
 86:             {
 87:                 result = test_method(); // Warmup
 88:             }
 89:             stopwatch.Stop();
 90:             for (int repeat = 0; repeat < 20; ++repeat)
 91:             {
 92:                 stopwatch.Reset();
 93:                 stopwatch.Start();
 94:                 result = test_method();
 95:                 stopwatch.Stop();
 96:                 avg_tick += stopwatch.ElapsedTicks;
 97:                 avg_ms += stopwatch.ElapsedMilliseconds;
 98:             }
 99:             avg_tick = avg_tick / 20;
100:             avg_ms = avg_ms / 20;
101:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
102:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
103:         }
104:     }

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