Hi guys.

I'm trying to calculate factorial numbers. I need to get the value of 100! for example.

What variable should i use? I tried double, but I don't think I get the right answer. After i get the value of the factorial, I need to get the sum of the digits. This is what I've been trying.



the sum of the digits of the number 100! is 659 according to my little app. But this is not the right value. What am I missing here?

My TI-83+ won't even calculate the factorial of a number as high as 100. There is no data type that can store numerical values that large. The only way i see to do something like that is to treat a string as a number, because it has a virtually infinite size. Then, you would have to make a method that would multiply a numerical value by that string manually, since you can't just do int * string. Another method is to have an integer array, with each element representing one digit in the actual factorial. That is how most small pi and e calculators work.

For the sum of the digits, what i would do is convert the number (100) to a string, and illiterate through each char in that string. Then you could convert that char back to an integer, and add it to the sum variable.

If I am not mistaken, 25! is too large for .Net to handle.

this is a sad thing

@jacobjordan can you give me some more details about what can I do?

Basically what i am saying for the factorial is since you can't fit 100! in any numerical data type, store the value in a string. For example, you couldn't store a value like 999999999999999999999999999999999 as a double because it's far too large, but you could put that in a string. But then, it wouldn't be a numerical data type, so you couldn't multiply it by by a numerical value using the * operator. That means you would have to write a method to multiply a numerical integer by a string that represents a number. To do that, think back to elementary school math when you first learned to multiply. You start at the left of the big number, and multiply each digit by the small number. Then carry, and you know the rest. Now, all you have to do is implement that in code.

Here is a method i just wrote that should do that

        /// <summary>
        /// Multiplies a string representing a number by a numerical int.
        /// </summary>
        public static string MultiplyString(int NumericValue, string StringValue)
        {
            string Product = StringValue;
            int Carry = 0; //This will hold the carry
            int Position;

            //Illiterate through each digit in StringValue
            for (Position = StringValue.Length; Position >= 1; Position--)
            {
                string Digit = Product.Substring(Position - 1, 1); //Get the digit in StringValue at the current index
                int DigitInt = int.Parse(Digit); //Parse that digit to an int
                int CurrentProduct = DigitInt * NumericValue; //Multiply it by NumericValue
                if (Carry != 0)
                {
                    CurrentProduct += Carry % 10; // add the last digit in carry onto CurrentProduct
                    Carry /= 10; //Take the digit we just added onto CurrentProduct off Carry
                }
                int CurrentCarry = CurrentProduct / 10; //Take all but the last digit off CurrentProduct and add it to carry.
                CurrentProduct %= 10; //Make CurrentProduct so it only holds the last digit
                Carry += CurrentCarry; //Add CurrentCarry onto Carry
                //Lastly, replace the current digit in Product with CurrentProduct
                Product = Product.Remove(Position - 1, 1);
                Product = Product.Insert(Position - 1, CurrentProduct.ToString());
            }

            //Add the remaining carry onto the front of Product
            if (Carry != 0)
            {
                Product = Carry.ToString() + Product;
            }
            return Product;
        }

Works like a charm. Pass that a string number as big as your heart desires.

Now then, to make that do a factorial, try this

string b;
while (a <= 100)
{
     b = MultiplyString( a, b );
     a++;
}

This post has been edited by jacobjordan: 30 Jun, 2009 - 01:54 PM

thx very much jacob

Another way to achieve it is to add reference to your C# project to this file in .NET-tab:
vjslib

Add using:
using java.math;

And now you can use java's BigInteger class. It can store quite big values, like 2^1000 which converted to string was over 300 characters long.

Also .NET Framework 4 is supposed to have its own BigInteger when it is released (or maybe already in beta?)

For posterity reasons, I'll add my implementation. I wrote mine before I saw jacob's implementation, and jacob's code totally blows mine out of the water in terms of both efficiency and conciseness. I guess we learned math a little differently in our elementary schools, lol, or I'm just not as sharp. The main difference is my code strictly performs single digit multiplication and addition:

        static string Factorial(int n)
        {
            string result = n.ToString();
            if (n > 1)
                result = Multiply(Factorial(n - 1), result);
            return result;
        }
        static string Multiply(string num1, string num2)
        {
            StringBuilder sb = new StringBuilder();
            int powerOfTen = 0;
            List<string> results = new List<string>();

            for (int i = num1.Length-1; i >= 0; i--)
            {
                int carryOver = 0;
                sb.Length = 0;
                for (int j = num2.Length-1; j >= 0; j--)
                {
                    int current = Int32.Parse(num1[i].ToString()) * Int32.Parse(num2[j].ToString()) + carryOver;
                    carryOver = current / 10;
                    current %= 10;
                    sb.Insert(0, current);
                }
                if (carryOver > 0)
                    sb.Insert(0, carryOver);
                results.Add(sb.ToString().PadRight(sb.Length+powerOfTen, '0'));
                powerOfTen++;
            }

            return AddAll(results);
        }
        static string AddAll(List<string> numbers)
        {
            string result = "0";
            if (numbers.Count == 0)
                return result;
            else if (numbers.Count == 1)
                result = numbers[0];
            else
            {
                result = numbers[0];
                for (int i = 1; i < numbers.Count; i++)
                    result = Add(result, numbers[i]);
            }
            result = result.TrimStart('0');
            if (result.Length == 0)
                return "0";
            return result;
        }
        static string Add(string num1, string num2)
        {
            StringBuilder sb = new StringBuilder();
            string left = num1;
            string right = num2;
            if (left.Length > right.Length)
                right = right.PadLeft(left.Length, '0');
            else if (right.Length > left.Length)
                left = left.PadLeft(right.Length, '0');
            int carryOver = 0;
            for (int i = left.Length - 1; i >= 0; i--)
            {
                int current = Int32.Parse(left[i].ToString()) + Int32.Parse(right[i].ToString()) + carryOver;
                carryOver = current / 10;
                current %= 10;
                sb.Insert(0, current);
            }
            if (carryOver > 0)
                sb.Insert(0, carryOver);
            return sb.ToString();
        }