AI/Algorithm/C#/WP7/Performance/etc…

Project Euler problem 73~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of reduced fraction lie between 1/3 and 1/2 for d<=12000: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_with_euclidean_algorithm_to_find_gcd);
  9:             TestBenchLoader(brute_force_with_seive_to_minimize_gcd_checking);
 10:             TestBenchLoader(using_stern_brocot_tree_to_count_fraction_in_between);
 11: 
 12:             Console.WriteLine("Press any key to exit");
 13:             Console.ReadKey();
 14:         }
 15: 
 16:         /// <summary>
 17:         /// just brute foce every number for each denominator and using euclidean aglorithm test if the fraction is in
 18:         /// reduced form
 19:         /// </summary>
 20:         static int brute_force_with_euclidean_algorithm_to_find_gcd()
 21:         {
 22:             var low_a = 1;
 23:             var low_b = 3;
 24:             var high_a = 1;
 25:             var high_b = 2;
 26:             var max = 12000;
 27:             int p, q, low, high;
 28:             var result = 0;
 29:             for (q = 5; q <= max; q++)
 30:             {
 31:                 low = (low_a * q) / low_b + 1;
 32:                 high = (high_a * q - 1) / high_b;
 33:                 for (p = low; p <= high; p++)
 34:                 {
 35:                     if (find_GCD(p, q) == 1)
 36:                         result++;
 37:                 }
 38:             }
 39:             return result;
 40:         }
 41: 
 42:         /// <summary>
 43:         /// modified version of the first method with seive to reduce number of fraction to test for co-prime
 44:         /// not much improvement, and the map size is too big to fit in cache, lawl
 45:         /// </summary>
 46:         static int brute_force_with_seive_to_minimize_gcd_checking()
 47:         {
 48:             var low_a = 1;
 49:             var low_b = 3;
 50:             var high_a = 1;
 51:             var high_b = 2;
 52:             var max = 12000;
 53:             int p, q, n, m, low, high, count;
 54:             var map = new bool[max + 1, 2000];
 55:             var result = 0;
 56:             for (q = 5; q <= max; q++)
 57:             {
 58:                 low = (low_a * q) / low_b + 1;
 59:                 high = (high_a * q - 1) / high_b;
 60:                 count = high - low + 1;
 61:                 for (p = low; p <= high; p++)
 62:                 {
 63:                     if (map[q, p - low] == false)
 64:                     {
 65:                         for (n = q * 2, m = p * 2; n <= max; n += q, m += p)
 66:                         {
 67:                             map[n, m - (n / 3 + 1)] = true;
 68:                         }
 69: 
 70:                         if (find_GCD(p, q) == 1)
 71:                             result++;
 72:                     }
 73:                 }
 74:             }
 75:             return result;
 76:         }
 77: 
 78:         /// <summary>
 79:         /// using the Stern–Brocot tree. see http://en.wikipedia.org/wiki/Stern-brocot_tree for details
 80:         /// basically an infinite binary search tree(in this case, stops at limit(which is 12k)), in which 
 81:         /// can be used to count number of nodes in bwetween two fractions(1/3, 1/2)
 82:         /// </summary>
 83:         static int using_stern_brocot_tree_to_count_fraction_in_between()
 84:         {
 85:             var limit = 12000;
 86:             Func<int, int, int, int,int> countSB = null;
 87:             countSB = (ln, ld, rn, rd) =>
 88:                 {
 89:                     var mn = ln + rn;
 90:                     var md = ld + rd;
 91:                     if (md > limit)
 92:                         return 0;
 93:                     else
 94:                     {
 95:                         var count = 1;
 96:                         count += countSB(ln, ld, mn, md);
 97:                         count += countSB(mn, md, rn, rd);
 98:                         return count;
 99:                     }
100:                 };
101:             return countSB(1, 3, 1, 2);
102:         }
103: 
104:         static int find_GCD(int x, int y)
105:         {
106:             while (x > 0)
107:             {
108:                 y = y % x;
109:                 y = y + x; // the next three lines is just swapping x and y
110:                 x = y - x;
111:                 y = y - x;
112:             }
113:             return y;
114:         }
115: 
116:         static Stopwatch stopwatch = new Stopwatch();
117:         static void TestBenchSetup()
118:         {
119:             // Uses the second Core or Processor for the Test
120:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
121:             // Prevents "Normal" processes from interrupting Threads
122:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
123:             // Prevents "Normal" Threads from interrupting this thread
124:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
125:         }
126:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
127:         static void TestBenchLoader(Func<int> test_method)
128:         {
129:             stopwatch.Reset();
130:             stopwatch.Start();
131:             var result = 0;
132:             long avg_tick = 0;
133:             long avg_ms = 0;
134:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
135:             // stabilizes the CPU cache and pipeline.
136:             {
137:                 result = test_method(); // Warmup
138:             }
139:             stopwatch.Stop();
140:             for (int repeat = 0; repeat < 20; ++repeat)
141:             {
142:                 stopwatch.Reset();
143:                 stopwatch.Start();
144:                 result = test_method();
145:                 stopwatch.Stop();
146:                 avg_tick += stopwatch.ElapsedTicks;
147:                 avg_ms += stopwatch.ElapsedMilliseconds;
148:             }
149:             avg_tick = avg_tick / 20;
150:             avg_ms = avg_ms / 20;
151:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
152:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
153:         }
154:     }

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