XNA/Algorithm/FP/and more…

Project Euler problem 72~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The elements contained in the set of reduced proper fractions for d ≤ 1,000,000: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_totient_function_to_find_total_RF_for_each_number_as_denominator);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// since the number of reduced fraction for a given denominator is basically the Totient function of that number.
 16:         /// (φ(4)=2, relative prime is 1, 3: reduced fraction with 4 as denominator: 1/4, 3/4, so total is 2 as well)
 17:         /// so the code used in problem 69 and 70 can be reused to calculate Totient function for each base(1,2,3...1mil)
 18:         /// </summary>
 19:         static long using_totient_function_to_find_total_RF_for_each_number_as_denominator()
 20:         {
 21:             var LIMIT = 1000001;
 22:             var bound = LIMIT / 2;
 23:             var primes = new int[LIMIT];
 24:             int s, m, t;
 25:             for (s = 2; s < bound; s++)
 26:             {
 27:                 if (primes[s] == 0)
 28:                 {
 29:                     for (m = s * 2; m < LIMIT; m += s) // m = s * 2 since no point to test prime number(always 1 and itself)
 30:                     {
 31:                         t = primes[m];
 32: 
 33:                         if (t == 0)
 34:                             t = m; // so this is 1st time, mark t to m(the number itself)
 35: 
 36:                         t /= s; // division first to avoid overflow
 37:                         t *= (s - 1);
 38:                         primes[m] = t;
 39:                     }
 40:                 }
 41:             }
 42:             long sum = 0;
 43:             for (s = 2; s < LIMIT; s++)
 44:             {
 45:                 t = primes[s];
 46:                 sum += (t == 0 ? s - 1 : t); // since prime will have zero as value in the array, and basically # of reduced fraction
 47:             }                                // for a prime number is every number blow it. eg: x/5: 1/5, 2/5, 3/5, 4/5 total:(5-1)
 48:             return sum;
 49:         }
 50: 
 51:         static Stopwatch stopwatch = new Stopwatch();
 52:         static void TestBenchSetup()
 53:         {
 54:             // Uses the second Core or Processor for the Test
 55:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 56:             // Prevents "Normal" processes from interrupting Threads
 57:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 58:             // Prevents "Normal" Threads from interrupting this thread
 59:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 60:         }
 61:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 62:         static void TestBenchLoader(Func<long> test_method)
 63:         {
 64:             stopwatch.Reset();
 65:             stopwatch.Start();
 66:             long result = 0;
 67:             long avg_tick = 0;
 68:             long avg_ms = 0;
 69:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 70:             // stabilizes the CPU cache and pipeline.
 71:             {
 72:                 result = test_method(); // Warmup
 73:             }
 74:             stopwatch.Stop();
 75:             for (int repeat = 0; repeat < 20; ++repeat)
 76:             {
 77:                 stopwatch.Reset();
 78:                 stopwatch.Start();
 79:                 result = test_method();
 80:                 stopwatch.Stop();
 81:                 avg_tick += stopwatch.ElapsedTicks;
 82:                 avg_ms += stopwatch.ElapsedMilliseconds;
 83:             }
 84:             avg_tick = avg_tick / 20;
 85:             avg_ms = avg_ms / 20;
 86:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 87:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 88:         }
 89:     }

c++

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