WinPhone7/GraphDB/Xaml/and more…

Project Euler problem 56~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The the maximum digital sum: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_and_test_each_number_with_limited_range);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// bascially testing each possible combination of number and power,
 16:         /// but skipped alot of loops with range set to 90 for both (see q's post)
 17:         /// </summary>
 18:         static int brute_force_and_test_each_number_with_limited_range()
 19:         {
 20:             var max = 0;
 21:             var sum = 0;
 22:             int a, b;
 23:             for (a = 90; a < 100; a++)
 24:             {
 25:                 for (b = 90; b < 100; b++)
 26:                 {
 27:                     sum = exponentiation_by_squaring(a, b);
 28:                     if (sum > max)
 29:                         max = sum;
 30:                 }
 31:             }
 32:             return max;
 33:         }
 34: 
 35:         /// <summary>
 36:         /// see http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Computation_by_powers_of_2
 37:         /// the number is stored in array, and using the support method static int[] multiply(int[] a, int[] b)
 38:         /// for multiplication.
 39:         /// the return value is not the actual result, but the sum of all digits of the result
 40:         /// </summary>
 41:         static int exponentiation_by_squaring(int num, int power)
 42:         {
 43:             var r = new int[] { 1 };
 44:             var n = num_to_array(num);
 45:             while (power > 0)
 46:             {
 47:                 if ((power & 1) == 1)
 48:                     r = multiply(r, n);
 49: 
 50:                 power >>= 1;
 51:                 n = multiply(n, n);
 52:             }
 53:             return r.Sum();
 54:         }
 55: 
 56:         /// <summary>
 57:         /// Schönhage–Strassen algorithm
 58:         /// http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
 59:         /// </summary>
 60:         static int[] multiply(int[] a, int[] b)
 61:         {
 62:             var result = new List<int>();
 63:             int shift, product, i, j;
 64:             var index = 0;
 65:             var a_len = a.Length;
 66:             var b_len = b.Length;
 67:             for (i = 0; i < a_len; i++)
 68:             {
 69:                 shift = index;
 70:                 for (j = 0; j < b_len; j++)
 71:                 {
 72:                     product = a[i] * b[j];
 73:                     if (shift >= result.Count)
 74:                         result.Add(0);
 75:                     result[shift] += product;
 76:                     shift++;
 77:                 }
 78:                 index++;
 79:             }
 80: 
 81:             var carry = 0;
 82:             for (i = 0; i < result.Count; i++)
 83:             {
 84:                 result[i] += carry;
 85:                 carry = result[i] / 10;
 86:                 result[i] = result[i] % 10;
 87:             }
 88:             if (carry > 0)
 89:                 result.Add(carry);
 90: 
 91:             return result.ToArray<int>();
 92:         }
 93: 
 94:         static int[] num_to_array(int n)
 95:         {
 96:             var result = new List<int>();
 97:             do
 98:             {
 99:                 result.Add(n % 10);
100:             } while ((n /= 10) > 0);
101: 
102:             return result.ToArray();
103:         }
104: 
105:         static Stopwatch stopwatch = new Stopwatch();
106:         static void TestBenchSetup()
107:         {
108:             // Uses the second Core or Processor for the Test
109:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
110:             // Prevents "Normal" processes from interrupting Threads
111:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
112:             // Prevents "Normal" Threads from interrupting this thread
113:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
114:         }
115:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
116:         static void TestBenchLoader(Func<int> test_method)
117:         {
118:             stopwatch.Reset();
119:             stopwatch.Start();
120:             var result = 0;
121:             long avg_tick = 0;
122:             long avg_ms = 0;
123:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
124:             // stabilizes the CPU cache and pipeline.
125:             {
126:                 result = test_method(); // Warmup
127:             }
128:             stopwatch.Stop();
129:             for (int repeat = 0; repeat < 20; ++repeat)
130:             {
131:                 stopwatch.Reset();
132:                 stopwatch.Start();
133:                 result = test_method();
134:                 stopwatch.Stop();
135:                 avg_tick += stopwatch.ElapsedTicks;
136:                 avg_ms += stopwatch.ElapsedMilliseconds;
137:             }
138:             avg_tick = avg_tick / 20;
139:             avg_ms = avg_ms / 20;
140:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
141:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
142:         }
143:     }

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