- Implementing map-reduce in F# (James)
- Essential Tools for the WPF Novice (Michael Sorens)
- How about a Zune-style ChildWindow? (Jeff Wilcox)
- Dropbox API and RestSharp for a C# developer
- Beautiful Google Doodles (1998 – 2010)
- Talking Reactive Extensions
- PDX Code Camp Session: WP7 Tips Tricks
- Book Review: JavaScript – The Good Parts
- How Google Maps splits the world in 2^20 256×256 tiles (’06)
- Google’s Pacman Source Code

`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