GameDev/XNA/C#/Algorithm/and more…

Project Euler problem 87~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The numbers below fifty million can be expressed as the sum: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(plan_brute_force_with_precalculated_primes);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// Just plain three nested loop each testing for double, triple and quad combinations,
 16:         /// since the list for each power primes are sorted by nature, range check is implemented in each loop
 17:         /// to skip unnecessary computation
 18:         /// </summary>
 19:         static int plan_brute_force_with_precalculated_primes()
 20:         {
 21:             // generate primes
 22:             var limit = 50000000;
 23:             var dlimit = (int)Math.Pow(limit, 0.5); // fins the limit for each prime power
 24:             var tlimit = (int)Math.Pow(limit, 1.0 / 3.0);
 25:             var qlimit = (int)Math.Pow(limit, 0.25);
 26:             var max = dlimit + 1;
 27:             var bound = (int)Math.Sqrt(max);
 28:             var primes = new bool[max];
 29:             primes[0] = true;
 30:             primes[1] = true;
 31:             int s, m, n;
 32:             for (s = 2; s <= bound; s++)
 33:             {
 34:                 if (primes[s] == false)
 35:                 {
 36:                     for (m = s * s; m < max; m += s)
 37:                     {
 38:                         primes[m] = true;
 39:                     }
 40:                 }
 41:             }
 42:             // calculate and save double, triple, and quad primes into respective lists
 43:             var dlist = new List<int>();
 44:             var tlist = new List<int>();
 45:             var qlist = new List<int>();
 46:             for (s = 2; s <= dlimit; s++)
 47:             {
 48:                 if (primes[s] == false)
 49:                 {
 50:                     if (s <= dlimit) dlist.Add(s * s);
 51:                     if (s <= tlimit) tlist.Add(s * s * s);
 52:                     if (s <= qlimit) qlist.Add(s * s * s * s);
 53:                 }
 54:             }
 55:             //  brute force loop to find all the possible combinations
 56:             var counter = 0;
 57:             var set = new HashSet<int>(); // used to keep out duplicate sum
 58:             int q, qt, qtd;
 59:             for (s = 0; s < qlist.Count; s++)
 60:             {
 61:                 q = qlist[s];
 62:                 for (m = 0; m < tlist.Count; m++)
 63:                 {
 64:                     qt = q + tlist[m];
 65:                     if (qt >= limit) //  since the lists are in sorted order by nature
 66:                         break;
 67:                     for (n = 0; n < dlist.Count; n++)
 68:                     {
 69:                         qtd = qt + dlist[n];
 70:                         if (qtd >= limit)
 71:                             break;
 72: 
 73:                         if (set.Add(qtd) == true) // where the most of time is spent 😦
 74:                             counter++;
 75:                     }
 76:                 }
 77:             }
 78:             return counter;
 79:         }
 80: 
 81:         static Stopwatch stopwatch = new Stopwatch();
 82:         static void TestBenchSetup()
 83:         {
 84:             // Uses the second Core or Processor for the Test
 85:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 86:             // Prevents "Normal" processes from interrupting Threads
 87:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 88:             // Prevents "Normal" Threads from interrupting this thread
 89:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 90:         }
 91:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 92:         static void TestBenchLoader(Func<int> test_method)
 93:         {
 94:             stopwatch.Reset();
 95:             stopwatch.Start();
 96:             var result = 0;
 97:             long avg_tick = 0;
 98:             long avg_ms = 0;
 99:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
100:             // stabilizes the CPU cache and pipeline.
101:             {
102:                 result = test_method(); // Warmup
103:             }
104:             stopwatch.Stop();
105:             for (int repeat = 0; repeat < 20; ++repeat)
106:             {
107:                 stopwatch.Reset();
108:                 stopwatch.Start();
109:                 result = test_method();
110:                 stopwatch.Stop();
111:                 avg_tick += stopwatch.ElapsedTicks;
112:                 avg_ms += stopwatch.ElapsedMilliseconds;
113:             }
114:             avg_tick = avg_tick / 20;
115:             avg_ms = avg_ms / 20;
116:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
117:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
118:         }
119:     }

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