GameDev/WP7/C#/and more…

Project Euler problem 104~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_Binet_formula_for_1st_9_digits_and_modulo_for_last_9_digits);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// by using Binet's Formula to approximate nth Fibonacci number, and combine this formula with logarithm
 16:         /// to get first 9 digits from the fib number.
 17:         /// as for the last 9 digits, the simple iteration and build up(combine with modulo) does the job well
 18:         /// see (http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html)
 19:         /// awesomely awesome link about Fibonacci number
 20:         /// </summary>
 21:         static int using_Binet_formula_for_1st_9_digits_and_modulo_for_last_9_digits()
 22:         {
 23:             var f1 = 1;
 24:             var f2 = 1;
 25:             var fn = f1 + f2;
 26:             var n = 2;
 27:             var map = new int[10];
 28:             var phi = (1 + Math.Sqrt(5)) / 2;
 29:             Func<int, bool> check_perm = num =>
 30:                 {
 31:                     map[1] = 0; map[2] = 0; map[3] = 0;
 32:                     map[4] = 0; map[5] = 0; map[6] = 0;
 33:                     map[7] = 0; map[8] = 0; map[9] = 0;
 34: 
 35:                     var rem = 0;
 36:                     var pass = true;
 37:                     while (num > 0)
 38:                     {
 39:                         num = Math.DivRem(num, 10, out rem);
 40:                         if (rem == 0 || map[rem] != 0)
 41:                         {
 42:                             pass = false;
 43:                             break;
 44:                         }
 45:                         map[rem] = 1;
 46:                     }
 47:                     return pass == true && map[1] == 1 && map[2] == 1 && map[3] == 1
 48:                                         && map[4] == 1 && map[5] == 1 && map[6] == 1
 49:                                         && map[7] == 1 && map[8] == 1 && map[9] == 1;
 50:                 };
 51:             var found = false;
 52:             while (found == false)
 53:             {
 54:                 fn = (f1 + f2) % 1000000000;
 55:                 f1 = f2;
 56:                 f2 = fn;
 57:                 n++;
 58: 
 59:                 if (check_perm(fn) == true) // only calculate the 1st 9 digits if last 9 digits are good
 60:                 {
 61:                     var step1 = n * Math.Log10(phi) - Math.Log10(5) / 2; // Log(phi^nth / √5)
 62:                     var step2 = Math.Pow(10, step1 - (int)step1) * 100000000; // only need the fraction part and turn it to int
 63:                     var step3 = (int)step2; // only need the int part
 64:                     found = check_perm(step3);
 65:                 }
 66:             }
 67:             return n;
 68:         }
 69: 
 70:         static Stopwatch stopwatch = new Stopwatch();
 71:         static void TestBenchSetup()
 72:         {
 73:             // Uses the second Core or Processor for the Test
 74:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 75:             // Prevents "Normal" processes from interrupting Threads
 76:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 77:             // Prevents "Normal" Threads from interrupting this thread
 78:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 79:         }
 80:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 81:         static void TestBenchLoader(Func<int> test_method)
 82:         {
 83:             stopwatch.Reset();
 84:             stopwatch.Start();
 85:             long result = 0;
 86:             long avg_tick = 0;
 87:             long avg_ms = 0;
 88:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 89:             // stabilizes the CPU cache and pipeline.
 90:             {
 91:                 result = test_method(); // Warmup
 92:             }
 93:             stopwatch.Stop();
 94:             for (int repeat = 0; repeat < 20; ++repeat)
 95:             {
 96:                 stopwatch.Reset();
 97:                 stopwatch.Start();
 98:                 result = test_method();
 99:                 stopwatch.Stop();
100:                 avg_tick += stopwatch.ElapsedTicks;
101:                 avg_ms += stopwatch.ElapsedMilliseconds;
102:             }
103:             avg_tick = avg_tick / 20;
104:             avg_ms = avg_ms / 20;
105:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
106:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
107:         }
108:     }

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