- 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 Program
2: {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_fraction
17: /// http://mathworld.wolfram.com/ContinuedFraction.html
18: /// by calculating the [a0:a1,a2,a3,a4......] the numerator and denominator can be calculated with the following
19: /// forumla: numerator: pn = an*pn_1 + pn_2
20: /// 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 an
22: /// 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 of
23: /// the previous 3rd term(except for the first 2 term, a1 and a2), while the rest is always 1
24: /// 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: else
44: 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 itoa0
56: var result = new List<int>();57: do
58: {59: result.Add(n % 10);60: } while ((n /= 10) > 0);
61:62: return result.ToArray();
63: }64:65: /// <summary>
66: /// Schönhage–Strassen algorithm
67: /// http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
68: /// </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 Test
128: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
129: // Prevents "Normal" processes from interrupting Threads
130: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;131: // Prevents "Normal" Threads from interrupting this thread
132: Thread.CurrentThread.Priority = ThreadPriority.Highest;133: }134: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
135: 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(); // Warmup
146: }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;}else
a = 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