- Emacs isn’t for everyone
- Apple faking 489 to 815 PPI on iPhone 4 ads
- Two small issues with Windows Phone 7 ApplicationBar buttons (and workaround)
- A Non-Mathematical Introduction to Using Neural Networks
- A Common Framework for Storytelling in Games
- Emulating old-school sprite flickering (theory and concept)
- books for xna
- Up- vector to rotation
- What’s wrong with the architecture of a game object drawing and updating itself?

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("Thevalue of n ≤ 1,000,000 for which n/φ(n) is a maximum: ");`

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

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

`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 = 1000000;32: var bound = LIMIT / 2;33: var primes = new int[LIMIT + 1];`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 max = 0;`

54: var n = 0;55: for (s = 2; s <= LIMIT; s++) // basically loop through the whole array and calculate max56: {57: t = primes[s];`58: if (t != 0)`

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

`61: if (max < cur)`

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

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

`72: /// from the problem's official answer.`

`73: /// basically the number would be the the largest number within bound(1mil) that only has prime factors`

`74: /// with power of 1, so baically 2*3*5*7*11*13*17 = 510510 (dang!)`

`75: /// </summary>`

76: static int smart_totient_formula_observation()77: {78: var LIMIT = 1000000;79: var num = 4;80: var n = 2 * 3;81: var result = 0;82: while (true)83: {`84: if (isPrime(num))`

85: {86: n *= num;`87: if (n <= LIMIT)`

88: result = n;`89: else`

`90: return result;`

91: }92: num++;93: }94: }95:96: static bool isPrime(int n)97: {`98: if (n <= 1)`

99: return false;`100: var limit = (int)Math.Sqrt(n) + 1;`

101: for (int i = 2; i < limit; i++)102: {`103: if (n % i == 0)`

104: return false;105: }106: return true;107: }108:109: static Stopwatch stopwatch = new Stopwatch();110: static void TestBenchSetup()111: {`112: // Uses the second Core or Processor for the Test`

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

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

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

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

120: static void TestBenchLoader(Func<int> test_method)121: {122: stopwatch.Reset();123: stopwatch.Start();124: var result = 0;`125: long avg_tick = 0;`

`126: long avg_ms = 0;`

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

129: {`130: result = test_method(); // Warmup`

131: }132: stopwatch.Stop();133: for (int repeat = 0; repeat < 20; ++repeat)134: {135: stopwatch.Reset();136: stopwatch.Start();137: result = test_method();138: stopwatch.Stop();139: avg_tick += stopwatch.ElapsedTicks;140: avg_ms += stopwatch.ElapsedMilliseconds;141: }142: avg_tick = avg_tick / 20;143: avg_ms = avg_ms / 20;144: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",145: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));146: }147: }c++

Advertisements