Как работать с большими числами в C++?

Question

[rustam6548]

У меня задание по комбинаторике. Нужно найти количество способов чего-то. Я разработал код, вроде выдаёт правильный ответ. Но только во входных данных такие данные, что надо как-то работать с факториалом 250. Я использовал long double, но он вмещает максимум факториал 170. Есть ли какое-то решение? Помогите, пожалуйста.

Функция факториал:

long double tmp1 = 1;
long double tmp2 = 1;
long double tmp3 = 1;

long double factorial(int num, int tmpNum) {
	long double res = 1;
	for (int i = 1; i <= num; i++) {
		res *= i;
		if (i == 170) {
			for (int t = i; t <= num; t++) {
				if (tmpNum == 1) tmp1 *= t;
				if (tmpNum == 2) tmp2 *= t;
				if (tmpNum == 3) tmp3 *= t;
			}
			break;
		}

	}
	return res;
}

main:

long double result = factorial(bills + k, 1) / factorial(bills, 2) * (1.0 / factorial(k, 3));
if (!(tmp1 == 1) || !(tmp2 == 1) || !(tmp3 == 1)) {
	result += tmp1 / tmp2 * (1.0 / tmp3);
}

Answer 1

[Wataru]

Если числа такие большие, что ответ никуда не влезает, то надо писать длинную арифметику. Цифры числа храните в массиве, складывайте/умножайте в столбик. Удобно хранить числа развернутыми. Гуглите "длинная арифметика" - найдете и код с примерами и кучу статей.

Но вам это, скорее всего, и не надо. В комбинаторных задачах часто все сокращается и можно получить ответ не считая очень большие числа.

Ваш код так ужасен, что я не могу понять, что вам там надо подсчитать в итоге, но уже брасается в глаза, что у вас там считается число сочетаний. Во-первых, можно считать (n-k+1*k+2*..*n)/k!, что уже дает более мелкие числа.

Потом, можно считать треугольником паскаля. Можно даже считать только одну строку, домножая и деля на одно число - тоже не получая в процессе чисел больше ответа.

Если bills не больше 64, то все влезет в стандартный unsigned long long.

Примеры дальше в вашей задаче точно не нужны, но для кругозора опишу и их.

Если в задаче более сложная формула, то можно хранить числа в виде их факторизации на простые числа. Поддерживайте массив в котором будете хранить степени всех простых чисел до некоторого максимального. При умножении прибавляйте, при делении вычитайте. В конце все оставшееся перемножте.

Еще более продвинутый метод: считать по модулю больших простых чисел и в конце, через китайскую теорему об остатках вычислять ответ.

Answer 2

[mayton2019]

В науке и технике такие форматы как double / long double / extended применяются уже давно и их
возможности полностью закрывают все мыслимые вопросы.

Например мы можем посчитать соотношение самой большой длины (диаметр вселенной) на
самую мелкую длину (переменная Планка) и это будет вполне себе число которое ляжет в эти
форматы.

Преподаватель вас заставил считать факториал 250? Это наверное троллинг. Зачем.
Для приближенного подсчета факториала есть например формула Стирлинга. Ее достаточно
чтоб получить порядок числа и первые значимые разряды.

А bigint и арифметикой можно и никогда не закончить вычисления. Это - как в криптографии.
Длину ключа увеличили всего в 2 раза. А всех дата-центров планеты Земля уже не хватает
чтобы в цикле прокрутить просто все значения этого длинного целого.

Answer 3

[Dmitrii]

https://faheel.github.io/BigInt/
https://github.com/Mariotti94/BigFloat
и аналогичные либы.
Для не слишком больших есть Quadruple(128) и Octuple(256) типы.
https://en.wikipedia.org/wiki/Quadruple-precision_...
Внутри, естественно, массивы.

Думаю, проще брать сразу BigFloat и не мучаться с 128/256 битными float'ами