Project Euler # 25 - Можно ли еще улучшить производительность?

#python #python-3.x

Вопрос:

12-й член, F12, является первым членом, содержащим три цифры.

Какой индекс первого члена в последовательности Фибоначчи должен содержать 1000 цифр?

 a = 1 
b = 1
i = 2
while(1):
    c = a   b
    i  = 1
    length = len(str(c))
    if length == 1000:
        print(i)
        break
    a = b
    b = c

Я получил ответ (работает достаточно быстро). Просто смотрю, есть ли лучший способ для этого вопроса

1. вы можете использовать dis для проверки своих версий

2. Если ваш код работает и вам нужны советы о том, как его улучшить, попробуйте форум Code Review SE .

3. Конечно, производительность можно улучшить. Вы можете решить проблему намного быстрее, потому что есть точная формула для вычисления n-го числа Фибоначчи — math.hmc.edu/funfacts/ffiles/10002.4-5.shtml . Я думаю, возможен даже алгоритм O (1).

Ответ №1:

Если вы ответили на вопрос, вы найдете множество объяснений ответов в теме проблемы. Решение, которое вы опубликовали, в значительной степени в порядке. Вы можете получить небольшое ускорение, просто проверяя, что ваш c>=10^999 на каждом шаге вместо того, чтобы сначала преобразовывать его в строку.

Лучший метод — использовать тот факт, что, когда числа Фибоначчи становятся достаточно большими, числа Фибоначчи сходятся к round(phi**n/(5**.5)) где phi=1.6180... золотое сечение и round(x) округляется x до ближайшего целого числа. Давайте рассмотрим общий случай нахождения первого числа Фибоначчи, состоящего из более чем m цифр. Затем мы ищем n такое, чтобы round(phi**n/(5**.5)) >= 10**(m-1)

Мы можем легко решить эту проблему, просто взяв лог обеих сторон и наблюдая за этим log(phi)*n - log(5)/2 >= m-1 , а затем решая для n .

Если вам интересно: «Откуда мне знать, что он сошелся на число n th?» Ну, вы можете проверить сами, или вы можете посмотреть в Интернете.

Кроме того, я думаю, что подобные вопросы относятся либо к Code Review SE, либо к Computer Science SE. Даже Math Overflow может быть хорошим местом для вопросов Project Euler, поскольку многие из них основаны на теории чисел.

Ответ №2:

Ваше решение полностью подходит для # 25 в project euler. Однако, если вы действительно хотите оптимизировать скорость здесь, вы можете попытаться вычислить Фибоначчи, используя тождества, о которых я писал в этом сообщении в блоге: https://sloperium.github.io/calculating-the-last-digits-of-large-fibonacci-numbers.html

 from functools import lru_cache


@lru_cache(maxsize=None)
def fib4(n):
    if n <= 1:
        return n

    if n % 2:
        m = (n   1) // 2
        return fib4(m) ** 2   fib4(m - 1) ** 2
    else:
        m = n // 2
        return (2 * fib4(m - 1)   fib4(m)) * fib4(m)


def binarySearch( length):
    first = 0
    last = 10**5
    found = False

    while first <= last and not found:
        midpoint = (first   last) // 2
        length_string = len(str(fib4(midpoint)))
        if length_string == length:
            return midpoint -1
        else:
            if length < length_string:
                last = midpoint - 1
            else:
                first = midpoint   1

print(binarySearch(1000))

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