Unity3D/Algorithm/LINQ/and more…

Project Euler problem 97~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The last ten digits of this prime number: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(plain_squaring_by_two_and_using_mask);
  9:             TestBenchLoader(exponentiation_by_squaring_and_using_mask);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         static long plain_squaring_by_two_and_using_mask()
 16:         {
 17:             long num = 2;
 18:             long mask = 10000000000L;
 19:             for (int p = 1; p < 7830457; p++)
 20:             {
 21:                 num *= 2;
 22:                 num %= mask;
 23:             }
 24:             return (num * 28433L + 1) % mask;
 25:         }
 26: 
 27:         /// <summary>
 28:         /// simiar to problem 56
 29:         /// using the exponentiation by squaring to compute the powers. vastly efficient compare with 1st method.
 30:         /// because of the precision of last 10 digits is needed by the question, so not even long is enough to hold
 31:         /// the number of digits required by n = n * n, which both n has to be 10 digits long, so array-based way of storing
 32:         /// the number is used instead. still super fast. 🙂
 33:         /// </summary>
 34:         static long exponentiation_by_squaring_and_using_mask()
 35:         {
 36:             var power = 7830457;
 37:             var r = new int[] { 1 };
 38:             var n = new int[] { 2 };
 39:             var mask = 10;
 40:             while (power > 0)
 41:             {
 42:                 if ((power & 1) == 1)
 43:                     r = multiply_and_mask(r, n, mask);
 44: 
 45:                 power >>= 1;
 46:                 n = multiply_and_mask(n, n, mask);
 47:             }
 48:             r = multiply_and_mask(r, num_to_array(28433), mask);
 49:             r = addition(r, new int[] { 1 });
 50:             long result = r[r.Length - 1];
 51:             for (int i = r.Length - 2; i >= 0; i--)
 52:             {
 53:                 result = result * 10 + r[i];
 54:             }
 55:             return result;
 56:         }
 57: 
 58:         /// <summary>
 59:         /// Schönhage–Strassen algorithm
 60:         /// http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
 61:         /// </summary>
 62:         static int[] multiply_and_mask(int[] a, int[] b, int max_digit)
 63:         {
 64:             var result = new List<int>();
 65:             int shift, product, i, j;
 66:             var index = 0;
 67:             var a_len = a.Length;
 68:             var b_len = b.Length;
 69:             for (i = 0; i < a_len; i++)
 70:             {
 71:                 shift = index;
 72:                 for (j = 0; j < b_len; j++)
 73:                 {
 74:                     product = a[i] * b[j];
 75:                     if (shift >= result.Count)
 76:                         result.Add(0);
 77:                     result[shift] += product;
 78:                     shift++;
 79:                 }
 80:                 index++;
 81:             }
 82: 
 83:             var carry = 0;
 84:             for (i = 0; i < result.Count; i++)
 85:             {
 86:                 result[i] += carry;
 87:                 carry = result[i] / 10;
 88:                 result[i] = result[i] % 10;
 89:             }
 90:             if (carry > 0)
 91:                 result.Add(carry);
 92: 
 93:             return result.Take(Math.Min(result.Count, max_digit)).ToArray<int>();
 94:         }
 95: 
 96:         static int[] addition(int[] a, int[] b)
 97:         {
 98:             var len = Math.Max(a.Length, b.Length);
 99:             var result = new List<int>(len);
100:             int carry = 0;
101:             int x, y, sum;
102:             for (int i = 0; i < len; i++)
103:             {
104:                 x = i < a.Length ? a[i] : 0;
105:                 y = i < b.Length ? b[i] : 0;
106: 
107:                 sum = x + y + carry;
108:                 result.Add(sum % 10);
109:                 carry = sum / 10;
110:             }
111:             if (carry > 0)
112:                 result.Add(carry);
113:             return result.ToArray<int>();
114:         }
115: 
116:         static int[] num_to_array(int n)
117:         {
118:             var result = new List<int>();
119:             do
120:             {
121:                 result.Add(n % 10);
122:             } while ((n /= 10) > 0);
123: 
124:             return result.ToArray();
125:         }
126: 
127:         static Stopwatch stopwatch = new Stopwatch();
128:         static void TestBenchSetup()
129:         {
130:             // Uses the second Core or Processor for the Test
131:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
132:             // Prevents "Normal" processes from interrupting Threads
133:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
134:             // Prevents "Normal" Threads from interrupting this thread
135:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
136:         }
137:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
138:         static void TestBenchLoader(Func<long> test_method)
139:         {
140:             stopwatch.Reset();
141:             stopwatch.Start();
142:             long result = 0;
143:             long avg_tick = 0;
144:             long avg_ms = 0;
145:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
146:             // stabilizes the CPU cache and pipeline.
147:             {
148:                 result = test_method(); // Warmup
149:             }
150:             stopwatch.Stop();
151:             for (int repeat = 0; repeat < 20; ++repeat)
152:             {
153:                 stopwatch.Reset();
154:                 stopwatch.Start();
155:                 result = test_method();
156:                 stopwatch.Stop();
157:                 avg_tick += stopwatch.ElapsedTicks;
158:                 avg_ms += stopwatch.ElapsedMilliseconds;
159:             }
160:             avg_tick = avg_tick / 20;
161:             avg_ms = avg_ms / 20;
162:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
163:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
164:         }
165:     }

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