GameDev/P7/Algorithm/and more…

Project Euler problem 65~
c#

  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 a1
 37:             {
 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 ms
143:             // 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
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s