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

Project Euler problem 80~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The total of the digital sums of the first one hundred decimal digits for all the irrational square roots: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_BigInteger_with_square_roots_by_subtraction);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// wow this paper pretty much saved the day(http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf)
 16:         /// And i dont want to deal with Big Integer problem so i use .net 4.0 instead.
 17:         /// </summary>
 18:         /// <returns></returns>
 19:         static int using_BigInteger_with_square_roots_by_subtraction()
 20:         {
 21:             var limit = 100;
 22:             var bound = (int)Math.Sqrt(limit);
 23:             var map = new bool[limit + 1];
 24:             var result = 0;
 25:             BigInteger cut_off = BigInteger.Parse(
 26:                 Enumerable.Range(0, 101).Aggregate(new StringBuilder("1"), (s, n) => s.Append("0")).ToString());
 27:             for (int i = 0; i < limit; i++)
 28:             {
 29:                 if (i <= bound)
 30:                     map[i * i] = true; // using this way to mark perfect squares
 31: 
 32:                 if (map[i] == false) // Perfect squares are skipped, The square root of x is rational if and only if x 
 33:                 {                    // is a rational number that can be represented as a ratio of two perfect squares
 34:                     BigInteger a = 5 * i;
 35:                     BigInteger b = 5;
 36:                     while (b < cut_off) // since not every iteration would produce extra digit,
 37:                     {                   // so when b.length == 100, b might not be accurate enough, wait until length is 101
 38:                         if (a >= b)
 39:                         {
 40:                             a = a - b;
 41:                             b += 10;
 42:                         }
 43:                         else
 44:                         {
 45:                             a *= 100;
 46:                             var final_d = b % 10;
 47:                             b -= final_d;
 48:                             b *= 10;
 49:                             b += final_d;
 50:                         }
 51:                     }
 52:                     result += b.ToString().Select(l => Convert.ToInt32(l) - 48).Take(100).Sum();
 53:                 }
 54:             }
 55:             return result;
 56:         }
 57: 
 58:         static Stopwatch stopwatch = new Stopwatch();
 59:         static void TestBenchSetup()
 60:         {
 61:             // Uses the second Core or Processor for the Test
 62:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 63:             // Prevents "Normal" processes from interrupting Threads
 64:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 65:             // Prevents "Normal" Threads from interrupting this thread
 66:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 67:         }
 68:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 69:         static void TestBenchLoader(Func<int> test_method)
 70:         {
 71:             stopwatch.Reset();
 72:             stopwatch.Start();
 73:             long result = 0;
 74:             long avg_tick = 0;
 75:             long avg_ms = 0;
 76:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 77:             // stabilizes the CPU cache and pipeline.
 78:             {
 79:                 result = test_method(); // Warmup
 80:             }
 81:             stopwatch.Stop();
 82:             for (int repeat = 0; repeat < 20; ++repeat)
 83:             {
 84:                 stopwatch.Reset();
 85:                 stopwatch.Start();
 86:                 result = test_method();
 87:                 stopwatch.Stop();
 88:                 avg_tick += stopwatch.ElapsedTicks;
 89:                 avg_ms += stopwatch.ElapsedMilliseconds;
 90:             }
 91:             avg_tick = avg_tick / 20;
 92:             avg_ms = avg_ms / 20;
 93:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 94:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 95:         }
 96:     }

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