WPF/3D/OctTree/algorithm/and more…

Project Euler problem 75~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(calculate_every_prime_triplet_and_test_each_s_multuples);
  9:             TestBenchLoader(calculate_every_prime_triplet_using_parent_child_relationships);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// using method IV from http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples
 17:         /// to generate every prime triplet which no side(a,b,c) can be greater than 1.5m /2 = 750000
 18:         /// (For the resulting triple to be primitive, u and v must be co-prime and u must be odd)
 19:         /// thus, u or v cannot exceed 865(for u:  u^2+2uv~750000, for v: 2v^2+2uv~750000)
 20:         /// </summary>
 21:         /// <returns></returns>
 22:         static int calculate_every_prime_triplet_and_test_each_s_multuples()
 23:         {
 24:             var max = 1500000;
 25:             var bound = (int)Math.Sqrt(max / 2 + 1) - 1;
 26: 
 27:             var map = new int[max + 1];
 28:             int u, v, g, h, i, a, b, c, p, m;
 29:             for (u = bound; u > 0; u -= 2)
 30:             {
 31:                 for (v = bound; v > 0; v--)
 32:                 {
 33:                     if (find_GCD(u, v) == 1)
 34:                     {
 35:                         g = u * u;
 36:                         h = 2 * (v * v);
 37:                         i = 2 * u * v;
 38:                         a = g + i;
 39:                         b = h + i;
 40:                         c = g + h + i;
 41:                         p = a + b + c;
 42:                         m = p;
 43:                         while (m <= max) // so here the multiples of the prime triplets are also included
 44:                         {
 45:                             map[m]++;
 46:                             m += p;
 47:                         }
 48:                     }
 49:                 }
 50:             }
 51:             var result = 0;
 52:             for (i = 1; i <= max; i++)
 53:             {
 54:                 if (map[i] == 1)
 55:                     result++;
 56:             }
 57:             return result;
 58:         }
 59: 
 60:         /// <summary>
 61:         /// using Parent/child relationships ways to generate/tranform each triplet(a,b,c) into three more triplets
 62:         /// starts with 3,4,5. stops when a+b+c > limit(1.5m). since it doesnt need to check for GCD, its faster than
 63:         /// first method(not sure if the compiler would turn this into loop rather than recursive calls)
 64:         /// </summary>
 65:         static int calculate_every_prime_triplet_using_parent_child_relationships()
 66:         {
 67:             var max = 1500000;
 68:             var map = new int[max + 1];
 69:             Action<int, int, int> trans = null;
 70:             trans = (a, b, c) =>
 71:                 {
 72:                     var p = a + b + c;
 73:                     if (p <= max)
 74:                     {
 75:                         var m = p;
 76:                         while (m <= max) // so here the multiples of the prime triplets are also included
 77:                         {
 78:                             map[m]++;
 79:                             m += p;
 80:                         }
 81:                         trans(a - 2 * b + 2 * c, 2 * a - b + 2 * c, 2 * a - 2 * b + 3 * c);
 82:                         trans(a + 2 * b + 2 * c, 2 * a + b + 2 * c, 2 * a + 2 * b + 3 * c);
 83:                         trans(-a + 2 * b + 2 * c, -2 * a + b + 2 * c, -2 * a + 2 * b + 3 * c);
 84:                     }
 85:                 };
 86:             trans(3, 4, 5);
 87:             var result = 0;
 88:             for (int i = 1; i <= max; i++)
 89:             {
 90:                 if (map[i] == 1)
 91:                     result++;
 92:             }
 93:             return result;
 94:         }
 95: 
 96:         /// <summary>
 97:         /// use Euclidean algorithm to find GCD, returns 1 if x and y are coprime
 98:         /// http://en.wikipedia.org/wiki/Euclidean_algorithm
 99:         /// </summary>
100:         static int find_GCD(int x, int y)
101:         {
102:             while (x > 0)
103:             {
104:                 y = y % x;
105:                 y = y + x; // the next three lines is just swapping x and y
106:                 x = y - x;
107:                 y = y - x;
108:             }
109:             return y;
110:         }
111: 
112:         static Stopwatch stopwatch = new Stopwatch();
113:         static void TestBenchSetup()
114:         {
115:             // Uses the second Core or Processor for the Test
116:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
117:             // Prevents "Normal" processes from interrupting Threads
118:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
119:             // Prevents "Normal" Threads from interrupting this thread
120:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
121:         }
122:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
123:         static void TestBenchLoader(Func<int> test_method)
124:         {
125:             stopwatch.Reset();
126:             stopwatch.Start();
127:             var result = 0;
128:             long avg_tick = 0;
129:             long avg_ms = 0;
130:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
131:             // stabilizes the CPU cache and pipeline.
132:             {
133:                 result = test_method(); // Warmup
134:             }
135:             stopwatch.Stop();
136:             for (int repeat = 0; repeat < 20; ++repeat)
137:             {
138:                 stopwatch.Reset();
139:                 stopwatch.Start();
140:                 result = test_method();
141:                 stopwatch.Stop();
142:                 avg_tick += stopwatch.ElapsedTicks;
143:                 avg_ms += stopwatch.ElapsedMilliseconds;
144:             }
145:             avg_tick = avg_tick / 20;
146:             avg_ms = avg_ms / 20;
147:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
148:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
149:         }
150:     }

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