Огромный Фибоначчи по модулю оптимизации м в Python 3


Я делаю какой-то алгоритм проектирования онлайн-курса как способ обучения, а также алгоритмы и Python. Одна из этих проблем требует, чтобы я написал код для поиска "огромное число Фибоначчи по модулю M". Код работает, но для некоторых входов (например, 99999999999999999 100000), Это превышает выделенный лимит времени. Однако, я не вижу способа улучшения производительности.

Вот описание проблемы:

Введение Проблема

Числа Фибоначчи определяются следующим образом:

Ф(0) = 0, Ф(1) = 1 и F(Я) = Ф(я−1) + ф(я−2) для i ≥ 2.

Описание Проблемы

Задача: даны два целых числа n и M, выходная мощность F(Н) м мод (то есть остаток F(н) при делении на M).

Формат ввода: входной файл содержит два целых числа n и M приведены в одной строке (через пробел).

Ограничения: 1 ≤ н ≤ 10^18 , 2 ≤ м ≤ 10^5 .

Выходной формат: выходная мощность f(n) с модом м

Сроки:с: 1 сек, на C++: 1 сек, Ява: 1,5 сек, питона: 5 сек. На C#: 1,5 сек, Хаскелл: 2 сек, яваскрипт: 3 сек, Рубин: 3 сек, Скала: 3 сек. Ограничение По Памяти: 512 Мб

Образец:

Input:

    281621358815590 30524

Output:

    11963

Вот код:

#!/usr/bin/python3

from sys import stdin              

def get_fibonacci_huge(n, m):
    fibonacciNumbers = [0, 1, 1]
    pisanoNumbers = [0, 1, 1]
    pisanoPeriod = 3

    for i in range(2, n):
        if pisanoNumbers[i - 1] == 0 and pisanoNumbers[i] == 1:
            pisanoPeriod = i - 1
            break;

        nextFibonacci = fibonacciNumbers[i - 1] + fibonacciNumbers[i];

        fibonacciNumbers.append(nextFibonacci)
        pisanoNumbers.append(nextFibonacci % m)
    else:
        pisanoPeriod = None # If we exhausted all values up to n, then the pisano period could not be determined. 

    if pisanoPeriod is None:
        return pisanoNumbers[n]
    else:
        return pisanoNumbers[n % pisanoPeriod]

if __name__ == '__main__':
    dataEntry = stdin.readline()
    n, m = map(int, dataEntry.split())
    print(get_fibonacci_huge(n, m))

Для ввода 99999999999999999 100000Она занимает около 5.10 секунд, а максимальный срок составляет 5,00 секунд.

Как заполнить Python и алгоритмы новичок, любой входной ценится.



Комментарии
2 ответа

Числа Фибоначчи растут экспоненциально. Это означает, что количество бит, представляющих их растет линейно, а так же сложность вычислений nextFibonacci. Его результаты в общую квадратичную сложность вашего цикла.

Хорошая новость заключается в том, что вам не нужно вычислять числа Фибоначчи на всех. Вам нужно лишь вычислить числа Пизано. Они подчиняются подобные повторения,

    p[n+1] = (p[n] + p[n-1]) % m

и в силу по модулю они никогда не превышают m. Сложность индивидуального дополнение остается постоянной, а общая сложность становится линейной.

(Крошечные дополнительно: \$ (а + б)\ \textrm{мод}\ с\экв\ а \textrm{мод}\ с\ + с\ \textrm{мод}\ с\$)

5
ответ дан 14 марта 2018 в 12:03 Источник Поделиться

Предположим, что вы внедрили предложение по ВНП, так что теперь строка выглядит следующим образом:

nextFibonacci = (fibonacciNumbers[i - 1] + fibonacciNumbers[i]) % m

Может есть еще лучше? На писано срок по модулю \$м\ долл на большинство \$6м\$ и поэтому период нахождения подход принимает \$О(М)\$ шагов, каждый из которых предполагает сложение чисел с \О(\журналов м)\$ цифр по общему времени выполнения \$О(М\журналов м)\$.

Существует альтернативный подход, который является вычисление \ФП\$му числу Фибоначчи по модулю \$м$ с помощью повторения $$ \eqalign{F_{2П−1} &= F_{н}^2 + F_{П−1}^2 \\ F_{2Н} &= (2F_{П−1} + F_{Н}) F_{Н}}. $$ Это может быть эффективно реализована с помощью рекурсии и мемоизация, например, вы могли бы использовать @functools.lru_cache декоратор, как это:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
"""Return the nth Fibonacci number modulo m."""
if n <= 1:
return n
elif n % 2:
a = fibonacci_modulo(n // 2, m)
b = fibonacci_modulo(n // 2 + 1, m)
return (a * a + b * b) % m
else:
a = fibonacci_modulo(n // 2 - 1, m)
b = fibonacci_modulo(n // 2, m)
return (2 * a + b) * b % m

Это принимает \$О((\зарегистрируйте N)^2)\$ умножений чисел с \О(\журналов м)\$ цифр, для общего времени выполнения \$о((\журнала N \журналов м)^2)\$. Так что этот подход будет улучшение на период нахождения в случаях, когда $$(\зарегистрируйте N)^2\журнал м ≪ м.$$ Например, в случае \$Н=10^{17}-1, М=10^5\$ дан в самом вопросе, мы \$(\зарегистрируйте N)^2\журнал м \приблизительно 6000\$ и на этом тесте fibonacci_modulo гораздо быстрее, чем get_fibonacci_huge:

>>> n = 10**17 - 1
>>> m = 10**5
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.09250206896103919
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.0001637069508433342

(Обратите внимание на использование cache_clear чтобы убедиться, что у нас есть "очистить кэш", и поэтому сроки сравнение справедливо.)

4
ответ дан 14 марта 2018 в 04:03 Источник Поделиться