WP7

Project Euler problem 20~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("Find the sum of the digits in the number 100!");
  8:             sw.Start();
  9:             var sum1 = factorial(100);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("for loop and Schönhage–Strassen multiplication(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("Press any key to exit");
 16:             Console.ReadKey();
 17:         }
 18: 
 19:         /// <summary>
 20:         /// store number in int array, and use Schönhage–Strassen algorithm to do multiplication
 21:         /// the reason to do this is because the number would get far bigger than double or int64
 22:         /// </summary>
 23:         /// <param name="max">the last number, in this problem 100</param>
 24:         /// <returns>sum of all </returns>
 25:         static int factorial(int max)
 26:         {
 27:             var a = new int[1] { 1 };
 28:             var b = new int[max.ToString().Length];
 29:             var num = 0;
 30:             for (int i = 1; i <= max; i++)
 31:             {
 32:                 num = i;
 33:                 for (int j = b.Length - 1; j >= 0; j--)
 34:                 {
 35:                     b[j] = num % 10;
 36:                     num = num / 10;
 37:                 }
 38:                 a = multiply(a, b);
 39:                 //Console.WriteLine(a.Aggregate(string.Empty, (str, n) => str += n));
 40:             }
 41:             return a.Sum();
 42:         }
 43: 
 44:         /// <summary>
 45:         /// Schönhage–Strassen algorithm
 46:         /// http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
 47:         /// </summary>
 48:         /// <param name="a">previous number</param>
 49:         /// <param name="b">next number to multiply</param>
 50:         /// <returns>the production in array</returns>
 51:         static int[] multiply(int[] a, int[] b)
 52:         {
 53:             var result = new int[a.Length + b.Length];
 54:             var product = 0;
 55:             var index = result.Length - 1;
 56:             var shift = 0;
 57: 
 58:             for (int i = a.Length - 1; i >= 0; i--)
 59:             {
 60:                 shift = 0;
 61:                 for (int j = b.Length - 1; j >= 0; j--)
 62:                 {
 63:                     product = a[i] * b[j];
 64:                     result[index - shift] += product;
 65:                     shift++;
 66:                 }
 67:                 index--;
 68:             }
 69: 
 70:             var carry = 0;
 71:             for (int i = result.Length - 1; i >= 0; i--)
 72:             {
 73:                 result[i] += carry;
 74:                 carry = result[i] / 10;
 75:                 result[i] = result[i] % 10;
 76:             }
 77: 
 78:             return result.SkipWhile(l => l == 0).ToArray<int>();
 79:         }
 80:     }

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