ObjectiveC/Algorithm/StackOverlowAPI/and more…

Project Euler problem 78~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The least value of n for which p(n) is divisible by one million: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_euler_generating_function);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// similar to solution to problem 76. The difference here p(n) is built from ground up(1,2,3....) until answer is found
 16:         /// so for each p(n), all the info is already calculated(p(n-k)). So array is used instead of dictionary.
 17:         /// in order to avoid overflow, each p(n) result is masked by remainder of 1mil(since the question asked for 1st number that is
 18:         /// divisible by 1mil
 19:         /// </summary>
 20:         static int using_euler_generating_function()
 21:         {
 22:             var map = new int[100000]; // should be big enough
 23:             map[0] = 1;
 24:             int a, b, p1, p2, bound, n, result;
 25:             n = 1;
 26:             while (true)
 27:             {
 28:                 bound = (int)Math.Sqrt(n); // since p(negative number(a or b)) is 0, so stops at x=~x^2
 29:                 result = 0;
 30:                 for (int k = 1, sign = 1; k <= bound; k++, sign = -sign)
 31:                 {
 32:                     a = n - (k * (3 * k - 1) / 2);
 33:                     b = n - (k * (3 * k + 1) / 2);
 34:                     p1 = a <= 0 ? a < 0 ? 0 : 1 : map[a];
 35:                     p2 = b <= 0 ? b < 0 ? 0 : 1 : map[b];
 36:                     result += (sign * (p1 + p2));
 37:                 }
 38:                 map[n] = result % 1000000; // masking
 39:                 if (map[n] == 0)
 40:                     return n;
 41:                 n++;
 42:             }
 43:         }
 44: 
 45:         static Stopwatch stopwatch = new Stopwatch();
 46:         static void TestBenchSetup()
 47:         {
 48:             // Uses the second Core or Processor for the Test
 49:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 50:             // Prevents "Normal" processes from interrupting Threads
 51:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 52:             // Prevents "Normal" Threads from interrupting this thread
 53:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 54:         }
 55:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 56:         static void TestBenchLoader(Func<int> test_method)
 57:         {
 58:             stopwatch.Reset();
 59:             stopwatch.Start();
 60:             var result = 0;
 61:             long avg_tick = 0;
 62:             long avg_ms = 0;
 63:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 64:             // stabilizes the CPU cache and pipeline.
 65:             {
 66:                 result = test_method(); // Warmup
 67:             }
 68:             stopwatch.Stop();
 69:             for (int repeat = 0; repeat < 20; ++repeat)
 70:             {
 71:                 stopwatch.Reset();
 72:                 stopwatch.Start();
 73:                 result = test_method();
 74:                 stopwatch.Stop();
 75:                 avg_tick += stopwatch.ElapsedTicks;
 76:                 avg_ms += stopwatch.ElapsedMilliseconds;
 77:             }
 78:             avg_tick = avg_tick / 20;
 79:             avg_ms = avg_ms / 20;
 80:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 81:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 82:         }
 83:     }

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