В чем ошибка в коде, который расчитывает период Пизано?

Question

[keddad]

Дано: алгоритмическая задача. Необходимо найти модуль от деления n-ного числа Фибоначи на m. Задача решается вычислением периода Пизано и использованием его вместо модуля от исходного n-ного числа (т.к. n может быть очень большим). Я пришел к, как мне казалось, милому и простому решению:

vector<unsigned long long> cache = {0, 1};
vector<unsigned long long> seq = {0, 1};

unsigned long long fib(int n) {
    if (n >= cache.size()) {
        cache.push_back(fib(n-1) + fib(n-2));
    }
    return cache[n];
}

int main() {
    unsigned long long n, m;
    cin >> n >> m;

    for (int i = 2;; ++i) {
        seq.push_back(fib(i) % m);
        if(seq[i] == 1 && seq[i-1] == 0) {
            seq.pop_back();
            seq.pop_back();
            break;
        }
    }

    cout << seq[n % seq.size()];
}

Его можно оптимизировать по памяти, если не хранить seq, но это мелочь. Проблема в том, что это решение работает только для малых чисел. Так, при n=2015 и m=3, выводится 1 - это правильный ответ. Но на больших последовательностях (n=239, m=100) начинает получаться фигня. Я нашел решение этой задачи (ссылка) - идейно оно почти такое же, кроме упомянутой оптимизации. В чем может быть ошибка в моем коде?

Comments

[Евгений Шатунов]

keddad , как соотносятся порядки n и результата fib?

[keddad]

Евгений Шатунов, если честно, понятия не имею. На этот вопрос вообще можно ответить для рекурсивно заданной функции, не имея n?

[keddad]

keddad, под "большими последовательностями" я подразумевал скорее увеличение m, если вы про это. Проблема, кажется, в расчете периода Пизано, а не самих чисел Фибоначчи

[Евгений Шатунов]

keddad, да, на этот вопрос всегда можно ответить. Или в теоретическом плане. Или в прикладном плане.
Меняй порядок n и смотри на изменение порядка результата fib. Так ты определишь практическое соотношение порядков.
Скорее всего, так ты и ответ на свой вопрос сразу найдешь.

[keddad]

Евгений Шатунов, хм, и правда, эта реализация fib() начинает выдавать странные результаты на больших числах. Не вполне понятно, правда, чем это вызвано, но буду думать. Спасибо!

[Евгений Шатунов]

keddad, это вызвано переполнением разрядов. Максимальным значением для uint64_t является 18446744073709551615. Числа Фибоначи довольно быстро выбиваются за этот предел.

И здесь я задам тебе следующий вопрос. Интересуют ли тебя в числе Фибоначи разряды старше искомого модуля?
Обрати внимание, как именно автор найденного тобой кода работает с m.

Answer 1

[Wataru]

У вас при вычислении cache числа не берутся по модулю. А значит очень быстро переполняют long long и случается фигня. Ведь цикл может начаться на очень больших числах. Вам надо всегда при вычислении брать по модулю m.

И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);