WP7/WPF/XNA/and more…

Project Euler problem 57~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The fractions contain a numerator with more digits than denominator: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_froce_construct_each_fraction_number_and_compare);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         struct fraction
 15:         {
 16:             public int[] numerator;
 17:             public int[] denominator;
 18:         }
 19: 
 20:         /// <summary>
 21:         /// basically brute force and find out the exact fraction for each iteration and compare the length
 22:         /// since the the iteration goes like this, 
 23:         /// 1 + 1/(2+1/2) = 1 + a (iteration 2) seed = 1/(2+1/2)
 24:         /// 1 + 1/(2+1/(2+1/2)) = 1 + 1 / 2 + a (iteration 3) seed = 1/(2+1/(2+1/2)) = 1 + 1/(2+a)
 25:         /// so on...
 26:         /// </summary>
 27:         static int brute_froce_construct_each_fraction_number_and_compare()
 28:         {
 29:             var counter = 0;
 30:             var seed = add_fraction_and_flip(TWO_OVER_ONE, ONE_OVER_TWO);
 31:             var result = new fraction();
 32:             for (int i = 1; i < 1000; i++)
 33:             {
 34:                 seed = add_fraction_and_flip(TWO_OVER_ONE, seed);
 35:                 result = add_fraction(ONE_OVER_ONE, seed);
 36:                 
 37:                 if (result.numerator.Length > result.denominator.Length)
 38:                     counter++;
 39: 
 40:                 //Console.WriteLine(string.Format("i:{0} {1}/{2}",
 41:                 //    i + 1,
 42:                 //    result.numerator.Reverse().Aggregate(new StringBuilder(), (s, n) => s.Append(n)).ToString(),
 43:                 //    result.denominator.Reverse().Aggregate(new StringBuilder(), (s, n) => s.Append(n)).ToString()));
 44:             }
 45:             return counter;
 46:         }
 47: 
 48:         static readonly fraction ONE_OVER_ONE = new fraction() { numerator = new int[] { 1 }, denominator = new int[] { 1 } };
 49:         static readonly fraction TWO_OVER_ONE = new fraction() { numerator = new int[] { 2 }, denominator = new int[] { 1 } };
 50:         static readonly fraction ONE_OVER_TWO = new fraction() { numerator = new int[] { 1 }, denominator = new int[] { 2 } };
 51: 
 52:         static fraction add_fraction(fraction a, fraction b)
 53:         {
 54:             var result = new fraction();
 55:             result.denominator = multiply(a.denominator, b.denominator);
 56:             result.numerator = addition(multiply(a.numerator, b.denominator), multiply(b.numerator, a.denominator));
 57:             return result;
 58:         }
 59: 
 60:         static fraction add_fraction_and_flip(fraction a, fraction b)
 61:         {
 62:             var result = new fraction();
 63:             result.denominator = addition(multiply(a.numerator, b.denominator), multiply(b.numerator, a.denominator));
 64:             result.numerator = multiply(a.denominator, b.denominator);
 65:             return result;
 66:         }
 67: 
 68:         static int[] addition(int[] a, int[] b)
 69:         {
 70:             var len = a.Length > b.Length ? a.Length : b.Length;
 71:             var result = new List<int>(len);
 72:             int carry = 0;
 73:             int x, y, sum;
 74:             for (int i = 0; i < len; i++)
 75:             {
 76:                 x = i < a.Length ? a[i] : 0;
 77:                 y = i < b.Length ? b[i] : 0;
 78: 
 79:                 sum = x + y + carry;
 80:                 result.Add(sum % 10);
 81:                 carry = sum / 10;
 82:             }
 83:             if (carry > 0)
 84:                 result.Add(carry);
 85:             return result.ToArray<int>();
 86:         }
 87: 
 88:         static int[] multiply(int[] a, int[] b)
 89:         {
 90:             var result = new List<int>();
 91:             int shift, product, i, j;
 92:             var index = 0;
 93:             for (i = 0; i < a.Length; i++)
 94:             {
 95:                 shift = index;
 96:                 for (j = 0; j < b.Length; j++)
 97:                 {
 98:                     product = a[i] * b[j];
 99:                     if (shift >= result.Count)
100:                         result.Add(0);
101:                     result[shift] += product;
102:                     shift++;
103:                 }
104:                 index++;
105:             }
106: 
107:             var carry = 0;
108:             for (i = 0; i < result.Count; i++)
109:             {
110:                 result[i] += carry;
111:                 carry = result[i] / 10;
112:                 result[i] = result[i] % 10;
113:             }
114:             if (carry > 0)
115:                 result.Add(carry);
116: 
117:             return result.ToArray<int>();
118:         }
119: 
120:         static Stopwatch stopwatch = new Stopwatch();
121:         static void TestBenchSetup()
122:         {
123:             // Uses the second Core or Processor for the Test
124:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
125:             // Prevents "Normal" processes from interrupting Threads
126:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
127:             // Prevents "Normal" Threads from interrupting this thread
128:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
129:         }
130:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
131:         static void TestBenchLoader(Func<int> test_method)
132:         {
133:             stopwatch.Reset();
134:             stopwatch.Start();
135:             var result = 0;
136:             long avg_tick = 0;
137:             long avg_ms = 0;
138:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
139:             // stabilizes the CPU cache and pipeline.
140:             {
141:                 result = test_method(); // Warmup
142:             }
143:             stopwatch.Stop();
144:             for (int repeat = 0; repeat < 20; ++repeat)
145:             {
146:                 stopwatch.Reset();
147:                 stopwatch.Start();
148:                 result = test_method();
149:                 stopwatch.Stop();
150:                 avg_tick += stopwatch.ElapsedTicks;
151:                 avg_ms += stopwatch.ElapsedMilliseconds;
152:             }
153:             avg_tick = avg_tick / 20;
154:             avg_ms = avg_ms / 20;
155:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
156:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
157:         }
158:     }

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