ParallelProgramming/WPF/NoSql/and more…

Project Euler problem 45~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The next triangle number that is also pentagonal and hexagonal?");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(incrementally_generate_each_type_of_number_and_compare);
  9:             TestBenchLoader(skip_generate_triangle_number_with_overflow_check);
 10:             TestBenchLoader(skip_generate_triangle_number_without_overflow_check);
 11:             TestBenchLoader(only_generate_hexagonal_and_check_if_its_pentagonal);
 12: 
 13:             Console.WriteLine("Press any key to exit");
 14:             Console.ReadKey();
 15:         }
 16: 
 17:         /// <summary>
 18:         /// since Hexagonal number grow the fastest(t:0.5x p:1.5x h:2x)
 19:         /// so for each H(n) as n++, let P(n) and T(n) catches, and there can be only 4 outcomes
 20:         /// P(n) > H(n) || P(n) == H(n)
 21:         /// T(n) > H(n) || T(n) == H(n)
 22:         /// so if P(n) == H(n) and T(n) == H(n), then thats the answer
 23:         /// </summary>
 24:         /// <returns></returns>
 25:         static long incrementally_generate_each_type_of_number_and_compare()
 26:         {
 27:             long tn = 285;
 28:             long pn = 165;
 29:             long hn = 144;
 30:             long t = 0;
 31:             long p = 0;
 32:             long h = 0;
 33:             while (true)
 34:             {
 35:                 hn++;
 36:                 h = hn * (2 * hn - 1);
 37: 
 38:                 while (t < h)
 39:                 {
 40:                     t = tn * (tn + 1) / 2;
 41:                     tn++;
 42:                 }
 43: 
 44:                 while (p < h)
 45:                 {
 46:                     p = pn * (3 * pn - 1) / 2;
 47:                     pn++;
 48:                 }
 49: 
 50:                 if (t == p && p == h)
 51:                     return t;
 52:             }
 53:         }
 54: 
 55:         /// <summary>
 56:         /// from the question's discussion post, learned the fact that
 57:         /// Every hexagonal number is a triangular number(http://en.wikipedia.org/wiki/Hexagonal_number)
 58:         /// so we just need to check pentagonal number
 59:         /// this method use the .net built-in checked keyword for overflow checking
 60:         /// it took me a while to realize that tn, pn, and hn has to be long as well
 61:         /// (i was using var pn = 164, and then infinite loop)
 62:         /// since hn * (2 * hn - 1) can overflow if hn is type int32 (int32 * int32) produce int32,
 63:         /// even though when we get the answer, tn=55386, pn=31978 and hn=27694
 64:         /// there is performance penality when using checked keywoard
 65:         /// </summary>
 66:         /// <returns></returns>
 67:         static long skip_generate_triangle_number_with_overflow_check()
 68:         {
 69:             long pn = 165;
 70:             long hn = 144;
 71:             long p = 0;
 72:             long h = 0;
 73:             while (true)
 74:             {
 75:                 h = checked(hn * (2 * hn - 1));
 76:                 hn++;
 77: 
 78:                 while (p < h)
 79:                 {
 80:                     p = checked(pn * (3 * pn - 1) / 2);
 81:                     pn++;
 82:                 }
 83: 
 84:                 if (p == h)
 85:                     return p;
 86:             }
 87:         }
 88: 
 89:         /// <summary>
 90:         /// same as method above, but without checked keyword
 91:         /// </summary>
 92:         /// <returns></returns>
 93:         static long skip_generate_triangle_number_without_overflow_check()
 94:         {
 95:             long pn = 165;
 96:             long hn = 144;
 97:             long p = 0;
 98:             long h = 0;
 99:             while (true)
100:             {
101:                 hn++;
102:                 h = hn * (2 * hn - 1);
103: 
104:                 while (p < h)
105:                 {
106:                     p = pn * (3 * pn - 1) / 2;
107:                     pn++;
108:                 }
109: 
110:                 if (p == h)
111:                     return p;
112:             }
113:         }
114: 
115:         /// <summary>
116:         /// instead of playing "catch up", just check for every hexagonal number, if it is also a 
117:         /// Pentagonal number by using the formula(same as problem 44)
118:         /// </summary>
119:         /// <returns></returns>
120:         static long only_generate_hexagonal_and_check_if_its_pentagonal()
121:         {
122:             long hn = 144;
123:             long h = 0;
124:             double pn = 0;
125:             while (true)
126:             {
127:                 hn++;
128:                 h = hn * (2 * hn - 1);
129:                 pn = (Math.Sqrt(24 * h + 1) + 1) / 6;
130:                 
131:                 if (pn == (int)pn)
132:                     return h;
133:             }
134:         }
135: 
136:         static Stopwatch stopwatch = new Stopwatch();
137:         static void TestBenchSetup()
138:         {
139:             // Uses the second Core or Processor for the Test
140:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
141:             // Prevents "Normal" processes from interrupting Threads
142:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
143:             // Prevents "Normal" Threads from interrupting this thread
144:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
145:         }
146:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
147:         static void TestBenchLoader(Func<long> test_method)
148:         {
149:             stopwatch.Reset();
150:             stopwatch.Start();
151:             long result = 0;
152:             long avg_tick = 0;
153:             long avg_ms = 0;
154:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
155:             // stabilizes the CPU cache and pipeline.
156:             {
157:                 result = test_method(); // Warmup
158:             }
159:             stopwatch.Stop();
160:             for (int repeat = 0; repeat < 20; ++repeat)
161:             {
162:                 stopwatch.Reset();
163:                 stopwatch.Start();
164:                 result = test_method();
165:                 stopwatch.Stop();
166:                 avg_tick += stopwatch.ElapsedTicks;
167:                 avg_ms += stopwatch.ElapsedMilliseconds;
168:             }
169:             avg_tick = avg_tick / 20;
170:             avg_ms = avg_ms / 20;
171:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
172:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
173:         }
174:     }

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