Неподписанный Long Long не пойдет вне 93-го числа Фибоначчи?
Вот код, который я написал для нахождения энного Числа Фибоначчи:
unsigned long long fib(int n)
{
unsigned long long u = 1, v = 1, t;
for(int i=2; i<=n; i++)
{
t = u + v;
u = v;
v = t;
}
return v;
}
В то время как алгоритм работает довольно быстро, вывод начинает волноваться когда n> 93. Я думаю/знаю, что это из-за неподписанного длинного long's 64 бита размером. Я плохо знаком с C++, но являюсь там способами обойти это так, я могу добраться, ответ чего-то любят выдумку (9999)?
Спасибо
2 ответа
GMP - это свободная библиотека для арифметики произвольной точности, работающая со знаковыми целыми числами, рациональными числами и числами с плавающей точкой. Практических ограничений на точность нет, кроме тех, которые подразумеваются доступной памятью в машине, на которой работает GMP. GMP имеет богатый набор функций, и эти функции имеют обычный интерфейс.
Основными целевыми приложениями для GMP являются приложения и исследования в области криптографии, приложения для обеспечения безопасности в Интернете, системы алгебры, исследования в области вычислительной алгебры и т.д....
Используйте библиотеку bigint. Их много в сети (например, здесь и здесь) или создайте свою собственную.
РЕДАКТИРОВАНИЕ: Накатать свой собственный гораздо сложнее, чем я ожидал. Арифметика - это не самая сложная часть, это распечатка результата в десятичной форме.