Rendering/C#4.0/WP7/and more…

Project Euler problem 58~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The ratio of primes along both diagonals first falls below 10%: ");
  6: 
  7:             TestBenchLoader(parallelized_corner_number_generation_and_primality_test);
  8:             TestBenchSetup(); // moved to here so it wont hinder the multithreaded version 
  9:             TestBenchLoader(generate_each_corner_and_test_for_primality_and_ratio);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14:         /// <summary>
 15:         /// this problem is really similar to question 28, so the forumla 
 16:         /// n^2-cn+c, where c is corner(starting with SE=0, SW=1, NW=2, NE=2) can be reused 🙂
 17:         /// since the corner number gets too large in this problem, generating seive is not feasible
 18:         /// so the old dividing all possible factors primality test is used, and this is where most of the time
 19:         /// is consumed
 20:         /// </summary>
 21:         public static int generate_each_corner_and_test_for_primality_and_ratio()
 22:         {
 23:             var prime_counter = 0.0;
 24:             var total_counter = 1.0;
 25:             var ratio = 0.0;
 26:             int i = 3; //the length, it will always be in odd number
 27:             Func<long, long, long> formula = (n, c) => n * n - c * n + c;
 28:             while (true)
 29:             {
 30:                 if (is_prime(formula(i, 0))) // SE corner
 31:                     prime_counter++;
 32: 
 33:                 if (is_prime(formula(i, 1))) // SW
 34:                     prime_counter++;
 35: 
 36:                 if (is_prime(formula(i, 2))) // NW
 37:                     prime_counter++;
 38: 
 39:                 if (is_prime(formula(i, 3))) // NE
 40:                     prime_counter++;
 41: 
 42:                 total_counter += 4;
 43:                 ratio = prime_counter / total_counter;
 44:                 if (ratio < 0.1)
 45:                     return i;
 46: 
 47:                 i += 2;
 48:             }
 49:         }
 50: 
 51:         class WorkItem
 52:         {
 53:             public int size;
 54:             public int corner;
 55:             public int start_num;
 56:             public bool[,] isPrime;
 57:             public AutoResetEvent signal;
 58:         }
 59: 
 60:         /// <summary>
 61:         /// the multithreaded version, basically divides the corners into 4 separate threads(threadpool)
 62:         /// and processing them in chunks(where the variable chunk_size is controlling)
 63:         /// in this method, the chunk size is 1k, so each corner of each matrix length(3,5,7,9...)
 64:         /// is generated and tested for primality and stored in the result matrix.
 65:         /// after all the corners are tested, the main thread loop though the result and calculates the ratio
 66:         /// performance is a little lower than 3x better compared with single threaded version
 67:         /// the code is programmed in such way that no lock is needed
 68:         /// </summary>
 69:         public static int parallelized_corner_number_generation_and_primality_test()
 70:         {
 71:             var prime_counter = 0.0;
 72:             var total_counter = 1.0;
 73:             var ratio = 0.0;
 74:             var num = 3;
 75:             var chunk_size = 1000;
 76:             var result_size = chunk_size / 2;
 77:             var result = new bool[4, result_size];
 78:             var work_items = Enumerable.Range(0, 4) //creates the workitem list(4 items, one for each corner)
 79:                    .Select(w => new WorkItem
 80:                    {
 81:                        size = chunk_size,
 82:                        corner = w,
 83:                        start_num = num,
 84:                        isPrime = result,
 85:                        signal = new AutoResetEvent(false)
 86:                    }).ToList();
 87: 
 88:             while (true)
 89:             {
 90:                 foreach (var item in work_items)
 91:                 {
 92:                     ThreadPool.QueueUserWorkItem((o) =>
 93:                     {
 94:                         var work_item = o as WorkItem;
 95:                         var start = work_item.start_num;
 96:                         var end = start + work_item.size;
 97:                         var corner = work_item.corner;
 98:                         var index = 0;
 99:                         var i = 0;
100:                         for (i = start; i < end; i += 2) //only half of the chunk is calculated(skips even number)
101:                         {
102:                             work_item.isPrime[corner, index++] = is_prime(calculate_corner(i, corner));
103:                         }
104: 
105:                         work_item.signal.Set();
106:                     }, item);
107:                 }
108: 
109:                 work_items.ForEach(w => w.signal.WaitOne());
110: 
111:                 for (int i = 0; i < result_size; i++) //ratio calculation
112:                 {
113:                     if (result[0, i])
114:                         prime_counter++;
115: 
116:                     if (result[1, i])
117:                         prime_counter++;
118: 
119:                     if (result[2, i])
120:                         prime_counter++;
121: 
122:                     if (result[3, i])
123:                         prime_counter++;
124: 
125:                     total_counter += 4;
126:                     ratio = prime_counter / total_counter;
127:                     if (ratio < 0.1)
128:                         return num + i * 2;
129:                 }
130: 
131:                 num += chunk_size; //advance the chunk starting number 
132:                 work_items.ForEach(w => //prep the work items for next chunk calculation
133:                 {
134:                     w.start_num = num; 
135:                     w.signal.Reset();
136:                 });
137:             }
138:         }
139: 
140:         static long calculate_corner(long n, int c)
141:         {
142:             return n * n - c * n + c;
143:         }
144: 
145:         static bool is_prime(long n)
146:         {
147:             if (n <= 1)
148:                 return false;
149:             var limit = (long)Math.Sqrt(n) + 1;
150:             for (long i = 2; i < limit; i++)
151:             {
152:                 if (n % i == 0)
153:                     return false;
154:             }
155:             return true;
156:         }
157: 
158:         static Stopwatch stopwatch = new Stopwatch();
159:         static void TestBenchSetup()
160:         {
161:             // Uses the second Core or Processor for the Test
162:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
163:             // Prevents "Normal" processes from interrupting Threads
164:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
165:             // Prevents "Normal" Threads from interrupting this thread
166:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
167:         }
168:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
169:         static void TestBenchLoader(Func<int> test_method)
170:         {
171:             stopwatch.Reset();
172:             stopwatch.Start();
173:             var result = 0;
174:             long avg_tick = 0;
175:             long avg_ms = 0;
176:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
177:             // stabilizes the CPU cache and pipeline.
178:             {
179:                 result = test_method(); // Warmup
180:             }
181:             stopwatch.Stop();
182:             for (int repeat = 0; repeat < 20; ++repeat)
183:             {
184:                 stopwatch.Reset();
185:                 stopwatch.Start();
186:                 result = test_method();
187:                 stopwatch.Stop();
188:                 avg_tick += stopwatch.ElapsedTicks;
189:                 avg_ms += stopwatch.ElapsedMilliseconds;
190:             }
191:             avg_tick = avg_tick / 20;
192:             avg_ms = avg_ms / 20;
193:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
194:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
195:         }
196:     }

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