- How to intersect a Ray with a terrain model?
- CPU Skinning
- Collision
- XNA Debugging Toolkit
- WP7 XNA Education Roadmap
- Move all zero values in a big array to its front portion in a Time Efficiency way
- How Zynga Survived FarmVille

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum: ");`

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

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

`15: /// (pretty much the same code from problem 69)`

`16: /// since Sieve of Eratosthenes basically test each number by checking if it is multiple of the current`

`17: /// "known" primes, essentially prime factorization(if each tested primes are saved). By combining this with the formula`

`18: /// on computing euler's function(http://en.wikipedia.org/wiki/Totient_function). the primes array itself save each`

`19: /// successive calculated totient result as more primes are being tested.`

`20: /// e.g:`

`21: /// f(36) = (2^2 * 3^2) = 36(1 - 1/2)(1 - 1/3) = ((36/2)*(36*(2-1))((36/3)*(36*(3-1)) =12;`

`22: /// so when 2 becomes current prime factor to test:`

`23: /// when it hits n, which is 36.`

`24: /// 1. if primes[36] == 0, change it to 36`

`25: /// 2. do ((primes[36]/2)*(primes[36]*(2-1)) now primes[36]=18`

`26: /// 3. later on when 3 becomes current prime factor to test`

`27: /// 4. do ((primes[36]/3)*(primes[36]*(3-1)) now primes[36]=12 (for n=36, this is it)`

`28: /// </summary>`

29: static int using_sieve_to_find_prime_factors_and_calculate_eulers_function()30: {31: var LIMIT = 10000000;32: var bound = LIMIT / 2;33: var primes = new int[LIMIT];`34: int s, m, t;`

`35: for (s = 2; s < bound; s++)`

36: {`37: if (primes[s] == 0)`

38: {39: for (m = s * 2; m < LIMIT; m += s) // m = s * 2 since no point to test prime number(always 1 and itself)40: {41: t = primes[m];42:`43: if (t == 0)`

`44: t = m; // so this is 1st time, mark t to m(the number itself)`

45:`46: t /= s; // division first to avoid overflow`

47: t *= (s - 1);48: primes[m] = t;49: }50: }51: }`52: double cur = 0;`

53: double min = int.MaxValue;54: var n = 0;55: for (s = LIMIT - 1; s >= 2; s--) // since the problem asks for minimum, the number is likely to be close to LIMIT56: {57: t = primes[s];`58: if (t != 0)`

59: {`60: cur = s / (double)t;`

`61: if (min > cur && isPerm(s, t))`

62: {63: min = cur;64: n = s;65: }66: }67: }`68: return n;`

69: }70:`71: /// <summary>`

`72: /// basically just checking if two numbers are permutation of each other`

`73: /// </summary>`

74: static bool isPerm(int original, int candidate)75: {76: var map = new int[10];`77: while (original > 0)`

78: {79: map[original % 10]++;80: original /= 10;81: map[candidate % 10]--;82: candidate /= 10;83: }`84: return map.All(n => n == 0);`

85: }86:87: static Stopwatch stopwatch = new Stopwatch();88: static void TestBenchSetup()89: {`90: // Uses the second Core or Processor for the Test`

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

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

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

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

98: static void TestBenchLoader(Func<int> test_method)99: {100: stopwatch.Reset();101: stopwatch.Start();102: var result = 0;`103: long avg_tick = 0;`

`104: long avg_ms = 0;`

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

107: {`108: result = test_method(); // Warmup`

109: }110: stopwatch.Stop();111: for (int repeat = 0; repeat < 20; ++repeat)112: {113: stopwatch.Reset();114: stopwatch.Start();115: result = test_method();116: stopwatch.Stop();117: avg_tick += stopwatch.ElapsedTicks;118: avg_ms += stopwatch.ElapsedMilliseconds;119: }120: avg_tick = avg_tick / 20;121: avg_ms = avg_ms / 20;122: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",123: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));124: }125: }c++

Advertisements