- Closures in C# can be evil (Marlon Grech)
- Video Games: Time not Included
- Interviewing programmers: coding test example
- Apple’s forgotten founder still wandering in the desert
- Google I/O 2010 Videos are up available (many of them anyway). You might be particularly interested in Google Storage for Developers, Building high-throughput data pipelines with Google App Engine, Batch data processing with App Engine, BigQuery and Prediction APIs, Measure in milliseconds redux: Meet Speed Tracer
- How do I convert an ANSI string directly to UTF-8?
- Diving into the RichTextBox (Silverlight TV #31)
- Most elegant way to expand card hand suits
- Best algorithm for finding the combination of a word?

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained: ");`

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

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

`15: /// armed with the research results and solutions from problem 64 and 65(basically this problem is`

`16: /// a combination of 64 and 65 code).`

`17: /// base on this page http://en.wikipedia.org/wiki/Pell%27s_equation, the convergents serve as x and y in the`

`18: /// equation, finding the first convergent that produces x and y that can solve the equation is the minimum x and y.`

`19: /// since i havent wrote a compare and substract method for the array base int. so i just use .net 4.0 BigInteger`

`20: /// implementation. (will update with array base int solution later)`

`21: /// </summary>`

22: static int using_pells_equation_with_continued_fractions_and_convergents()23: {24: var limit = 1000;`25: var bound = (int)Math.Sqrt(limit);`

26: var map = new bool[limit + 1];27: BigInteger result = 0;28: BigInteger tmp;`29: int largest = 0;`

30:31: for (int i = 0; i < limit; i++)32: {`33: if (i <= bound)`

34: map[i * i] = true; // using this way to mark perfect squares35:36: if (map[i] == false) // perfect squares are skipped37: {38: tmp = find_convergent(i);`39: if (result < tmp)`

40: {41: result = tmp;42: largest = i;43: }44: }45: }`46: return largest;`

47: }48:49: static BigInteger find_convergent(int i)50: {`51: // for finding a0,a1,a2......`

`52: var a0 = (int)Math.Sqrt(i);`

53: var m = 0;54: var d = 1;55: var a = a0;56:`57: // for finding convergent`

58: BigInteger h_2 = 0;59: BigInteger h_1 = 1;60: BigInteger h = a * h_1 + h_2;61: BigInteger k_2 = 1;62: BigInteger k_1 = 0;63: BigInteger k = a * k_1 + k_2;64: BigInteger approx = 0;65: while (true)66: {67: m = d * a - m;68: d = (i - m * m) / d;69: a = (a0 + m) / d;70:71: h_2 = h_1;72: h_1 = h;73: h = a * h_1 + h_2;74:75: k_2 = k_1;76: k_1 = k;77: k = a * k_1 + k_2;78: approx = h * h - i * k * k;79:80: if (approx == 1) // so minimal x is found`81: return h;`

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

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

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

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

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

96: static void TestBenchLoader(Func<int> test_method)97: {98: stopwatch.Reset();99: stopwatch.Start();`100: long result = 0;`

`101: long avg_tick = 0;`

`102: long avg_ms = 0;`

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

105: {`106: result = test_method(); // Warmup`

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

Advertisements