F#/WPF/DropBox/WP7/GoogleMap/and more…

Project Euler problem 63~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The numbers of n-digit positive integers exist which are also an nth power: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_list_to_store_number_to_avoid_overflow);
  9:             TestBenchLoader(crazy_math_formula);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// basically the idea is that only number below two digits can have such number that equal to nth power
 17:         /// since two digits number will always have more digits than its nth power eg. 10^1=10(2), 10^2=100(3)
 18:         /// and since for single digit number, the most additional digit that can be add is 1. 
 19:         /// eg. 9^1=3(no additional digits), 9^2=81(one additional digits), 9^3=729(one additional digits)
 20:         /// so at any given time, if power becomes bigger than digits count, then digit count will not be able to catch
 21:         /// up. Since the "product" will overflow, List of int and simple_multiply method is used for multiplication
 22:         /// </summary>
 23:         static int using_list_to_store_number_to_avoid_overflow()
 24:         {
 25:             int num, power, digits;
 26:             var count = 1; // for 1^1
 27:             var product = new List<int>();
 28:             for (num = 2; num < 10; num++)
 29:             {
 30:                 product.Clear();
 31:                 product.Add(1);
 32:                 for (power = 1; true; power++)
 33:                 {
 34:                     simple_multiply(product, num);
 35:                     digits = product.Count;
 36: 
 37:                     if (power > digits)
 38:                         break;
 39: 
 40:                     if (power == digits)
 41:                         count++;
 42:                 }
 43:             }
 44:             return count;
 45:         }
 46: 
 47:         /// <summary>
 48:         /// from the problem's discussion post (from Alvaro)
 49:         /// You know that x^n has n digits when 
 50:         ///     10^(n-1) <= x^n < 10^n 
 51:         /// First of all, x < 10. So we only have to try x={1, 2, 3, ..., 9}. 
 52:         /// The next thing to notice is that the left inequality is true for small values of n, 
 53:         /// but the 10^(n-1) part grows faster than the x^n part. All you have to do is find out when they meet. 
 54:         /// This can be done like this
 55:         /// 10^(n-1)=x^n => 0.1*10^n=x^n => log(0.1)+n*log(10)=n*log(x)
 56:         /// => log(10)=n*(log(10)-log(x)) => n=log(10)/(log(10)-log(x))
 57:         /// That value of n is already not good, so we have to round down to find out the largest integer 
 58:         /// for which the inequality holds true. 
 59:         /// </summary>
 60:         static int crazy_math_formula()
 61:         {
 62:             int num;
 63:             var result = 0;
 64:             var count = 0;
 65:             for (num = 1; num < 10; num++)
 66:             {
 67:                 count = (int)Math.Floor(Math.Log(10) / (Math.Log(10) - Math.Log(num)));
 68:                 result += count;
 69:             }
 70:             return result;
 71:         }
 72: 
 73:         static List<int> tmpList = new List<int>();
 74:         static void simple_multiply(List<int> a, int b)
 75:         {
 76:             int i;
 77:             tmpList.Clear();
 78:             var len = a.Count;
 79:             for (i = 0; i < len; i++)
 80:             {
 81:                 tmpList.Add(a[i] * b);
 82:             }
 83:             var carry = 0;
 84:             len = tmpList.Count;
 85:             for (i = 0; i < len; i++)
 86:             {
 87:                 tmpList[i] += carry;
 88:                 carry = tmpList[i] / 10;
 89:                 tmpList[i] = tmpList[i] % 10;
 90:                 a[i] = tmpList[i];
 91:             }
 92:             if (carry > 0)
 93:                 a.Add(carry);
 94:         }
 95: 
 96:         static Stopwatch stopwatch = new Stopwatch();
 97:         static void TestBenchSetup()
 98:         {
 99:             // Uses the second Core or Processor for the Test
100:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
101:             // Prevents "Normal" processes from interrupting Threads
102:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
103:             // Prevents "Normal" Threads from interrupting this thread
104:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
105:         }
106:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
107:         static void TestBenchLoader(Func<int> test_method)
108:         {
109:             stopwatch.Reset();
110:             stopwatch.Start();
111:             long result = 0;
112:             long avg_tick = 0;
113:             long avg_ms = 0;
114:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
115:             // stabilizes the CPU cache and pipeline.
116:             {
117:                 result = test_method(); // Warmup
118:             }
119:             stopwatch.Stop();
120:             for (int repeat = 0; repeat < 20; ++repeat)
121:             {
122:                 stopwatch.Reset();
123:                 stopwatch.Start();
124:                 result = test_method();
125:                 stopwatch.Stop();
126:                 avg_tick += stopwatch.ElapsedTicks;
127:                 avg_ms += stopwatch.ElapsedMilliseconds;
128:             }
129:             avg_tick = avg_tick / 20;
130:             avg_ms = avg_ms / 20;
131:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
132:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
133:         }
134:     }

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