Факториал от большого числа

Верно ли, что факториал от значения 2020 равен числу из этого файла (число нужно мысленно вытянуть в строчку) или нашему алгоритму просто не хватает возможностей даже на такое значение? Думается, что реализованное "школьное" умножение всё-таки других ограничений, кроме размера буфера, не имеет.

Для факториала от 100, по крайней мере, всё похоже:

Factorial from 100=
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000
Stirling's formula: 9.32485e+157

Проверка (имеющая смысл только для достаточно больших чисел) делается через главный член формулы Стирлинга, но для 2020 она, конечно, уже благополучно выдаст бесконечность.

Ниже приводится листинг консольной программы на C++, проверенной в Visual Studio 2019.

 2020f.txt (факториал от 2020) (6 Кб)

#include <iostream>
#define _USE_MATH_DEFINES
#include <ATLComTime.h>
#include <cmath>
using namespace std;

#define MAX 10000 /* максимальное количество цифр */

int multiply(int x, int res[], int res_size) { 
 //Умножить x на res[] "по-школьному". Вернёт новый размер res_size
 int carry = 0;
 for (int i = 0; i < res_size; i++) {
  int prod = res[i] * x + carry;
  res[i] = prod % 10;
  carry = prod / 10;
 }
 while (carry) {
  res[res_size] = carry % 10;
  carry = carry / 10;
  res_size++;
 }
 return res_size;
}

void factorial (int n) {
 int res[MAX];
 res[0] = 1;
 int res_size = 1;
 for (int x = 2; x <= n; x++) res_size = multiply(x, res, res_size);
 cout << "Factorial from " << n << "=" << endl;
 for (int i = res_size - 1; i >= 0; i--) cout << res[i];
}

int main() {
 int n = 2020;
 factorial (n);
 //Проверка по формуле Стирлинга
 double d = sqrt(2* M_PI * n) * pow (n/exp(1.),n);
 cout << endl << "Stirling's formula: " << d;
 cin.get(); return 0;
}

Про число пи в C++ см. здесь.

22.10.2020, 12:29 [1351 просмотр]