- Chapter 10: Game Development and the Rise of Casual Games – by David Wesley
- Basic Manipulation Event Handling in Windows Phone 7 (Charles Petzold)
- Detecting loops in a linked list – the Tortoise and Hare
- A Beginner’s Guide to Trail Running, Matthew Frazier
- Parallel Programming in .NET Framework 4: Getting Started – Alexandra Rusina starts a new series of posts looking at the Parallel programming capabilities of the .NET 4 release, beginning with an introductory look at the Task Parallel Library
- MEF has shipped!!!
- Best algorithm for finding the combination of a word?
- Is there a faster alternative to using textures in XNA?
1: class Program2: {3: static void Main(string[] args)4: {5: Console.WriteLine("The sum of digits in the numerator of the 100^(th) convergent of the continued fraction for e: ");6:7: TestBenchSetup();8: TestBenchLoader(using_convergents_and_formula_to_calculate_numerator);9:10: Console.WriteLine("Press any key to exit");11: Console.ReadKey();12: }13:14: /// <summary>15: /// base on the following links:16: /// http://en.wikipedia.org/wiki/Simple_continued_fraction17: /// http://mathworld.wolfram.com/ContinuedFraction.html18: /// by calculating the [a0:a1,a2,a3,a4......] the numerator and denominator can be calculated with the following19: /// forumla: numerator: pn = an*pn_1 + pn_220: /// denominator: qn = an*qn_1 + qn_2 (for this problem, just the numerator is needed)21: /// the key here is to generate an: since the problem gives some initial values of an22: /// e = [2; 1,(2),1,1,(4),1,1,(6),1,1,(8) ... , 1,2k,1, ...]. there is a pattern:, every 3rd term is incremented by 2 of23: /// the previous 3rd term(except for the first 2 term, a1 and a2), while the rest is always 124: /// since numerator would get too big, so the int array is used.25: /// runs less than 1k ticks on my machine, the compiler or the .net runtime must be doing some voodoo optimizations.26: /// </summary>27: static int using_convergents_and_formula_to_calculate_numerator()28: {29: var every_third = 0;30: var a = 2;31: var p_2 = new int[] { 0 }; // p(n-1)32: var p_1 = new int[] { 1 }; // p(n-2)33: var p = addition(multiply(num_to_array(a), p_1), p_2);34:35: var counter = -1;36: while (counter++ < 98) // since counter starts at -1(for the ++ thing), and starts at a137: {38: if ((counter + 2) % 3 == 0)39: {40: every_third += 2;41: a = every_third;42: }43: else44: a = 1;45:46: p_2 = p_1;47: p_1 = p;48: p = addition(multiply(num_to_array(a), p_1), p_2);49: }50: return p.Sum();51: }52:53: static int[] num_to_array(int n)54: {55: // same alogorithm as itoa056: var result = new List<int>();57: do58: {59: result.Add(n % 10);60: } while ((n /= 10) > 0);61:62: return result.ToArray();63: }64:65: /// <summary>66: /// Schönhage–Strassen algorithm67: /// http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm68: /// </summary>69: /// <param name="a">previous number</param>70: /// <param name="b">next number to multiply</param>71: /// <returns>the product</returns>72: static int[] multiply(int[] a, int[] b)73: {74: var result = new List<int>();75: int shift, product, i, j;76: var index = 0;77: for (i = 0; i < a.Length; i++)78: {79: shift = index;80: for (j = 0; j < b.Length; j++)81: {82: product = a[i] * b[j];83: if (shift >= result.Count)84: result.Add(0);85: result[shift] += product;86: shift++;87: }88: index++;89: }90:91: var carry = 0;92: for (i = 0; i < result.Count; i++)93: {94: result[i] += carry;95: carry = result[i] / 10;96: result[i] = result[i] % 10;97: }98: if (carry > 0)99: result.Add(carry);100:101: return result.ToArray<int>();102: }103:104: static int[] addition(int[] a, int[] b)105: {106: var len = a.Length > b.Length ? a.Length : b.Length;107: var result = new List<int>(len);108: int carry = 0;109: int x, y, sum;110: for (int i = 0; i < len; i++)111: {112: x = i < a.Length ? a[i] : 0;113: y = i < b.Length ? b[i] : 0;114:115: sum = x + y + carry;116: result.Add(sum % 10);117: carry = sum / 10;118: }119: if (carry > 0)120: result.Add(carry);121: return result.ToArray<int>();122: }123:124: static Stopwatch stopwatch = new Stopwatch();125: static void TestBenchSetup()126: {127: // Uses the second Core or Processor for the Test128: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);129: // Prevents "Normal" processes from interrupting Threads130: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;131: // Prevents "Normal" Threads from interrupting this thread132: Thread.CurrentThread.Priority = ThreadPriority.Highest;133: }134: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx135: static void TestBenchLoader(Func<int> test_method)136: {137: stopwatch.Reset();138: stopwatch.Start();139: long result = 0;140: long avg_tick = 0;141: long avg_ms = 0;142: while (stopwatch.ElapsedMilliseconds < 1200) // A Warmup of 1000-1500 ms143: // stabilizes the CPU cache and pipeline.144: {145: result = test_method(); // Warmup146: }147: stopwatch.Stop();148: for (int repeat = 0; repeat < 20; ++repeat)149: {150: stopwatch.Reset();151: stopwatch.Start();152: result = test_method();153: stopwatch.Stop();154: avg_tick += stopwatch.ElapsedTicks;155: avg_ms += stopwatch.ElapsedMilliseconds;156: }157: avg_tick = avg_tick / 20;158: avg_ms = avg_ms / 20;159: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",160: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));161: }162: }c++
#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;vector<int> num_to_vector(int n);vector<int> addition(const vector<int> &a, const vector<int> &b);vector<int> multiply(const vector<int> &a, const vector<int> &b);int using_convergents_and_formula_to_calculate_numerator();int main(){cout << "The sum of digits in the numerator of the 100^(th) convergent of the continued fraction for e:\n";int answer = using_convergents_and_formula_to_calculate_numerator();cout <<"using_convergents_and_formula_to_calculate_numerator way: "<< answer;cout <<"\nPress any key to exit";string input = "";getline(cin, input);return 0;}int using_convergents_and_formula_to_calculate_numerator(){int every_third = 0;int a = 2;vector<int> p_2 = num_to_vector(0);vector<int> p_1 = num_to_vector(1);vector<int> p = addition(multiply(num_to_vector(a), p_1), p_2);int counter = -1;while (counter++ < 98){if ((counter + 2) % 3 == 0){every_third += 2;a = every_third;}elsea = 1;p_2 = p_1;p_1 = p;p = addition(multiply(num_to_vector(a), p_1), p_2);}int p_len = p.size();int sum = 0;for (int i = 0; i < p_len; i++){sum += p[i];}return sum;}vector<int> num_to_vector(int n){vector<int> result;do{result.push_back(n % 10);} while ((n /= 10) > 0);return result;}vector<int> addition(const vector<int> &a, const vector<int> &b){int a_len = a.size();int b_len = b.size();int len = max(a_len, b_len);vector<int> result;int x = 0;int y = 0;int sum = 0;int carry = 0;for (int i = 0; i < len; i++){x = i < a_len ? a[i] : 0;y = i < b_len ? b[i] : 0;sum = x + y + carry;result.push_back(sum % 10);carry = sum / 10;}if(carry > 0)result.push_back(carry);return result;}vector<int> multiply(const vector<int> &a, const vector<int> &b){vector<int> result;int shift = 0;int product = 0;int index = 0;int a_len = a.size();int b_len = b.size();for (int i = 0; i < a_len; i++){shift = index;for (int j = 0; j < b_len; j++){product = a[i] * b[j];if (shift >= result.size())result.push_back(0);result[shift] += product;shift++;}index++;}int carry = 0;int result_len = result.size();for (int i = 0; i < result_len; i++){result[i] += carry;carry = result[i] / 10;result[i] = result[i] % 10;}if (carry > 0)result.push_back(carry);return result;}
Advertisements
