Keyframe/ReverseEngineering/F#inGame/and more…

Project Euler problem 48~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000)");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(only_calculate_last_10_digits_for_each_number_and_its_power);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// lets say the question is find the last 2 digits of 17^1 + 17^2 + ... +17^5
 16:         /// if we just take the last 2 digits in each iteration: 
 17:         /// n:1             (17)      1*17=17             1*17=(17)
 18:         /// n:2            2(89)      17*17=289           17*17=2(89)                                  
 19:         /// n:3           49(13)      289*17=4913         89*17=15(13)
 20:         /// n:4          835(21)      4913*17=83521       13*17=2(21)
 21:         /// n:5        14198(57)      83521*17=1418857    21*17=3(57)
 22:         ///               =1(97)                               =1(97)
 23:         /// this work because 289*17 = (200+89)*17 = 200*17 + 89*17 = 3400 + 1513
 24:         /// </summary>
 25:         static long only_calculate_last_10_digits_for_each_number_and_its_power()
 26:         {
 27:             long mask = 10000000000;
 28:             long result = 0;
 29:             long num, power, tmp;
 30:             for (num = 1; num <= 1000; num++)
 31:             {
 32:                 tmp = num;
 33:                 for (power = 1; power < num; power++)
 34:                 {
 35:                     tmp = (tmp * num) % mask;
 36:                 }
 37:                 result = (result + tmp) % mask;
 38:             }
 39:             return result;
 40:         }
 41: 
 42:         static Stopwatch stopwatch = new Stopwatch();
 43:         static void TestBenchSetup()
 44:         {
 45:             // Uses the second Core or Processor for the Test
 46:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 47:             // Prevents "Normal" processes from interrupting Threads
 48:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 49:             // Prevents "Normal" Threads from interrupting this thread
 50:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 51:         }
 52:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 53:         static void TestBenchLoader(Func<long> test_method)
 54:         {
 55:             stopwatch.Reset();
 56:             stopwatch.Start();
 57:             long result = 0;
 58:             long avg_tick = 0;
 59:             long avg_ms = 0;
 60:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 61:             // stabilizes the CPU cache and pipeline.
 62:             {
 63:                 result = test_method(); // Warmup
 64:             }
 65:             stopwatch.Stop();
 66:             for (int repeat = 0; repeat < 20; ++repeat)
 67:             {
 68:                 stopwatch.Reset();
 69:                 stopwatch.Start();
 70:                 result = test_method();
 71:                 stopwatch.Stop();
 72:                 avg_tick += stopwatch.ElapsedTicks;
 73:                 avg_ms += stopwatch.ElapsedMilliseconds;
 74:             }
 75:             avg_tick = avg_tick / 20;
 76:             avg_ms = avg_ms / 20;
 77:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 78:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 79:         }
 80:     }

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