Без подписи долго не выйдет за пределы 93-го числа Фибоначчи?

Question

Вот код, который я написал для нахождения n-го числа Фибоначчи:

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. Я думаю / знаю, что это из-за 64-битного размера unsigned long long. Я новичок в C ++, но есть ли способы обойти это, чтобы я мог получить ответ на что-то вроде fib (9999)?

Спасибо

Answer 1

http://gmplib.org/

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

Основными целевыми приложениями для GMP являются приложения и исследования в области криптографии, приложения для обеспечения безопасности в Интернете, системы алгебры, исследования в области вычислительной алгебры и т. Д. *

Answer 2

Используйте библиотеку bigint. В Интернете есть много всего (например, здесь и здесь ) или сворачивайте свои собственные.

РЕДАКТИРОВАТЬ: кататься самостоятельно гораздо сложнее, чем я ожидал. Арифметика не самая сложная часть; распечатывает результат в десятичной форме.