XNA/Algorithm/WP7/VS/and more…

Project Euler problem 76~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of ways can one hundred be written as a sum of at least two positive integers: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_euler_generating_function_with_memoization);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// got the formula from http://mathworld.wolfram.com/PartitionFunctionP.html (#11)
 16:         /// which generates the number partitions p(n)~, using cache to saved all previous calculated results,
 17:         /// which boost the speed tremendously
 18:         /// additional info: http://www.math.clemson.edu/~kevja/PAPERS/ComputingPartitions-MathComp.pdf
 19:         /// </summary>
 20:         static int using_euler_generating_function_with_memoization()
 21:         {
 22:             Func<int, int> p = null;
 23:             Dictionary<int, int> cache = new Dictionary<int, int>();
 24:             p = (n) =>
 25:                 {
 26:                     if (n < 0)      // found out about the case when p(0) and p(negative) on 
 27:                         return 0;   // http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function
 28:                     else if (n == 0)
 29:                         return 1;
 30:                     else
 31:                     {
 32:                         int a, b, p1, p2;
 33:                         var result = 0;
 34:                         for (int k = 1, sign = 1; k <= n; k++)
 35:                         {
 36:                             a = n - (k * (3 * k - 1) / 2);
 37:                             b = n - (k * (3 * k + 1) / 2);
 38:                             p1 = cache.ContainsKey(a) ? cache[a] : (cache[a] = p(a));
 39:                             p2 = cache.ContainsKey(b) ? cache[b] : (cache[b] = p(b));
 40:                             result += (sign * Math.Abs(p1 + p2));
 41:                             sign = -sign;
 42:                         }
 43:                         return result;
 44:                     }
 45:                 };
 46:             return p(100) - 1; // since 100 itself doesnt count(2 or more numbers partitions)
 47:         }
 48: 
 49:         static Stopwatch stopwatch = new Stopwatch();
 50:         static void TestBenchSetup()
 51:         {
 52:             // Uses the second Core or Processor for the Test
 53:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 54:             // Prevents "Normal" processes from interrupting Threads
 55:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 56:             // Prevents "Normal" Threads from interrupting this thread
 57:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 58:         }
 59:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 60:         static void TestBenchLoader(Func<int> test_method)
 61:         {
 62:             stopwatch.Reset();
 63:             stopwatch.Start();
 64:             var result = 0;
 65:             long avg_tick = 0;
 66:             long avg_ms = 0;
 67:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 68:             // stabilizes the CPU cache and pipeline.
 69:             {
 70:                 result = test_method(); // Warmup
 71:             }
 72:             stopwatch.Stop();
 73:             for (int repeat = 0; repeat < 20; ++repeat)
 74:             {
 75:                 stopwatch.Reset();
 76:                 stopwatch.Start();
 77:                 result = test_method();
 78:                 stopwatch.Stop();
 79:                 avg_tick += stopwatch.ElapsedTicks;
 80:                 avg_ms += stopwatch.ElapsedMilliseconds;
 81:             }
 82:             avg_tick = avg_tick / 20;
 83:             avg_ms = avg_ms / 20;
 84:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 85:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 86:         }
 87:     }

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