- The A-Z of Programming Languages: Objective-C
- Five Really Handy Google Command Line Tricks [Command Line]
- http://nehe.gamedev.net/
- A good repartition algorithm
- http://en.wikipedia.org/wiki/Greedy_algorithm
- What problems have you solved using bloom filters?
- Stack Overflow Releases API Into Public Beta (Vineel Shah)
- Whatever Happened to Voice Recognition?
- How to cheat on video encoder comparisons
- Wow, a task bar, what a novel idea

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The least value of n for which p(n) is divisible by one million: ");`

6:7: TestBenchSetup();8: TestBenchLoader(using_euler_generating_function);9:`10: Console.WriteLine("Press any key to exit");`

11: Console.ReadKey();12: }13:`14: /// <summary>`

`15: /// similar to solution to problem 76. The difference here p(n) is built from ground up(1,2,3....) until answer is found`

`16: /// so for each p(n), all the info is already calculated(p(n-k)). So array is used instead of dictionary.`

`17: /// in order to avoid overflow, each p(n) result is masked by remainder of 1mil(since the question asked for 1st number that is`

`18: /// divisible by 1mil`

`19: /// </summary>`

20: static int using_euler_generating_function()21: {22: var map = new int[100000]; // should be big enough23: map[0] = 1;`24: int a, b, p1, p2, bound, n, result;`

25: n = 1;26: while (true)27: {28: bound = (int)Math.Sqrt(n); // since p(negative number(a or b)) is 0, so stops at x=~x^229: result = 0;30: for (int k = 1, sign = 1; k <= bound; k++, sign = -sign)31: {32: a = n - (k * (3 * k - 1) / 2);33: b = n - (k * (3 * k + 1) / 2);34: p1 = a <= 0 ? a < 0 ? 0 : 1 : map[a];35: p2 = b <= 0 ? b < 0 ? 0 : 1 : map[b];36: result += (sign * (p1 + p2));37: }`38: map[n] = result % 1000000; // masking`

`39: if (map[n] == 0)`

`40: return n;`

41: n++;42: }43: }44:45: static Stopwatch stopwatch = new Stopwatch();46: static void TestBenchSetup()47: {`48: // Uses the second Core or Processor for the Test`

`49: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);`

`50: // Prevents "Normal" processes from interrupting Threads`

51: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;`52: // Prevents "Normal" Threads from interrupting this thread`

53: Thread.CurrentThread.Priority = ThreadPriority.Highest;54: }`55: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx`

56: static void TestBenchLoader(Func<int> test_method)57: {58: stopwatch.Reset();59: stopwatch.Start();60: var result = 0;`61: long avg_tick = 0;`

`62: long avg_ms = 0;`

63: while (stopwatch.ElapsedMilliseconds < 1200) // A Warmup of 1000-1500 ms`64: // stabilizes the CPU cache and pipeline.`

65: {`66: result = test_method(); // Warmup`

67: }68: stopwatch.Stop();69: for (int repeat = 0; repeat < 20; ++repeat)70: {71: stopwatch.Reset();72: stopwatch.Start();73: result = test_method();74: stopwatch.Stop();75: avg_tick += stopwatch.ElapsedTicks;76: avg_ms += stopwatch.ElapsedMilliseconds;77: }78: avg_tick = avg_tick / 20;79: avg_ms = avg_ms / 20;80: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",81: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));82: }83: }c++

Advertisements