- Headhunters, what to watch out for…
- http://creators.xna.com/en-us/article/datastructures
- What kind of data processing problems would CUDA help with?
- How did this programmer achieve this calculator inside of a game?
- Introduction to Event Driven Programming in C# (Richard McClutchen)
- Windows Phone 7 View Model Style Video Player (Alan Beasley)
- Colin Melia on OData with Silverlight
- Toughest Developer Puzzle Ever 2
- Ask HN: What to do about a boring job ?
- A Google Go Talk : programming
- GCC starts move towards implementation in C++
- Hacker Monthly #1 – June 2010 is here
- What every programmer should know about memory, Part 1
- Windows User Interface Guidelines, Kirill Osenkov
- Can the daily scrum be a waste of time?
- The Vast and Endless Sea
- Video: Hardcore production debugging in .NET – Ingo Rammer
- How do we raise our game?

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The numbers of continued fractions for N ≤ 10000 have an odd period: ");`

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

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

`15: /// using the formula from`

`16: /// http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion`

`17: /// which made the whole problem pretty simple. bool[] array is used to keep track of perfect square,`

`18: /// since the range is not big(10k), so its fine~`

`19: /// </summary>`

20: static int using_iterative_algorithm_to_calculate_continued_fraction_expansion()21: {22: var limit = 10000;`23: var bound = (int)Math.Sqrt(limit);`

24: var map = new bool[limit + 1];25: var result = 0;26:27: for (int i = 2; i <= limit; i++)28: {`29: if (i <= bound)`

30: map[i * i] = true; // using this way to mark perfect squares31:32: if (map[i] == false) // perfect squares are skipped33: {`34: var a0 = (int)Math.Sqrt(i);`

35: var m = 0;36: var d = 1;37: var a = a0;`38: var counter = -1; // since the 1st iteration is not part of number chains`

39: var m1 = int.MinValue; // reset m1 and d1`40: var d1 = int.MinValue;`

41: while (true)42: {43: counter++;44:`45: if (counter == 1)`

46: {`47: m1 = m; // so these two are marked as head of the period`

48: d1 = d;49: }50:51: m = d * a - m;52: d = (i - m * m) / d;53: a = (a0 + m) / d;54:55: if (m == m1 && d == d1) // so end of period is found`56: break;`

57: }`58: if ((counter & 1) != 0)`

59: result++;60: }61: }`62: return result;`

63: }64:65: static Stopwatch stopwatch = new Stopwatch();66: static void TestBenchSetup()67: {`68: // Uses the second Core or Processor for the Test`

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

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

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

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

76: static void TestBenchLoader(Func<int> test_method)77: {78: stopwatch.Reset();79: stopwatch.Start();`80: long result = 0;`

`81: long avg_tick = 0;`

`82: long avg_ms = 0;`

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

85: {`86: result = test_method(); // Warmup`

87: }88: stopwatch.Stop();89: for (int repeat = 0; repeat < 20; ++repeat)90: {91: stopwatch.Reset();92: stopwatch.Start();93: result = test_method();94: stopwatch.Stop();95: avg_tick += stopwatch.ElapsedTicks;96: avg_ms += stopwatch.ElapsedMilliseconds;97: }98: avg_tick = avg_tick / 20;99: avg_ms = avg_ms / 20;100: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",101: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));102: }103: }c++

`1: int using_iterative_algorithm_to_calculate_continued_fraction_expansion()`

2: {`3: int result = 0;`

4: for (double i = 2; i <= 10000; i++)5: {6: if (is_perfect_square(i) == false) // perfect squares are skipped7: {8: int a0 = (int)sqrt(i);`9: int m = 0;`

`10: int d = 1;`

`11: int a = a0;`

12: int counter = -1; // since the 1st iteration is not part of number chains13: int m1 = INT_MIN; // reset m1 and d1`14: int d1 = INT_MIN;`

15: while (true)16: {17: counter++;18:`19: if (counter == 1)`

20: {`21: m1 = m; // so these two are marked as head of the period`

22: d1 = d;23: }24:25: m = d * a - m;26: d = (i - m * m) / d;27: a = (a0 + m) / d;28:29: if (m == m1 && d == d1) // so end of period is found`30: break;`

31: }`32: if ((counter & 1) != 0)`

33: result++;34: }35: }`36: return result;`

37: }38:`39: //http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer/295678#295678`

40: int is_perfect_square(int n)41: {42: int h = n & 0xF; // h is the last hex "digit"`43: if (h > 9)`

`44: return 0;`

`45: // Use lazy evaluation to jump out of the if statement as soon as possible`

`46: if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)`

47: {48: int t = (int) floor( sqrt((double) n) + 0.5 );`49: return t*t == n;`

50: }`51: return 0;`

52: }

Advertisements