Is there an algorithm for calculating a factorial without using System.Numerics library? We receive an int number and we need to return factorial of this number as string(if n = 30, we should return "265252859812191058636308480000000", if n = 70, we should return "11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000" ect. Numbers are very big)

I tried to find out, did anyone already write an article about that, but I didn't find anything.

CodePudding user response：

It suffices to implement multiplication of a large number as a string by a small integer.

Illustration: 12! = 11! x 12 is obtained by multiplying every digit by 12 and summing (with shifts):

 39916800
36
108
 108
   12
    72
     96
       0
        0
---------
479001600

CodePudding user response：

static string FindFactorial(int n)
    {
        int[] result = new int[500000];
        result[0] = 1;
        int resultSize = 1;

        for (int x = 2; x <= n; x  )
            resultSize = Multiply(x, result, resultSize);

        string factorial = "";
        for (int i = resultSize - 1; i >= 0; i--)
            factorial  = result[i].ToString();

        return factorial;
    }

    static int Multiply(int x, int[] result, int resultSize)
    {
        int carry = 0;
        for (int i = 0; i < resultSize; i  )
        {
            int product = result[i] * x   carry;
            result[i] = product % 10;
            carry = product / 10;
        }

        while (carry != 0)
        {
            result[resultSize] = carry % 10;
            carry /= 10;
            resultSize  ;
        }

        return resultSize;
    }

This will work

CodePudding user response：

Well, you have to woark with string representation of non-negative integer values; time to reproduce school algorithms:

Addition:

using System.Linq; // for not to implementing Reverse

...

private static string AddStrings(string left, string right) {
  StringBuilder result = new StringBuilder(Math.Max(left.Length, right.Length)   1);

  int carry = 0;

  for (int i = 0; i < Math.Max(left.Length, right.Length);   i) {
    int sum = (i < left.Length ? left[left.Length - 1 - i] - '0' : 0)  
              (i < right.Length ? right[right.Length - 1 - i] - '0' : 0)  
               carry;

    result.Append(sum % 10);
    carry = sum / 10;
  }

  if (carry > 0)
    result.Append(carry);

  return string.Concat(result.ToString().Reverse());
}

Multiplication:

private static string MultiplyStrings(string left, int digit) {
  if (digit == 0)
    return "0";

  StringBuilder result = new StringBuilder(left.Length   1);

  int carry = 0;

  for (int i = left.Length - 1; i >= 0; --i) {
    int mul = (left[i] - '0') * digit   carry;

    result.Append(mul % 10);
    carry = mul / 10;
  }

  if (carry > 0)
    result.Append(carry);

  return string.Concat(result.ToString().Reverse());
}

private static string MultiplyStrings(string left, string right) {
  string result = "0";

  for (int i = right.Length - 1; i >= 0; --i)
    result = AddStrings(result,
       MultiplyStrings(left, right[i] - '0')   new string('0', right.Length - 1 - i));

  return result;
}

Now you can easily implement factorial:

private static string Factorial(int value) {
  if (value < 0)
    throw new ArgumentOutOfRangeException(nameof(value));

  if (value <= 1)
    return value.ToString();

  string result = "2";

  for (int d = 2; d <= value;   d)
    result = MultiplyStrings(result, d.ToString());

  return result;
}