Project Euler # 25: продолжайте получать ошибку переполнения (результат большой) - это связано с вычислением числа Фибоначчи?

Question

Я работаю над решением проблемы Project Euler 25:

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

Моя частькод работает для меньших цифр, но когда я пробую 1000 цифр, я получаю ошибку:

OverflowError: (34, 'Result too large')

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

Вот мой код:

'''
 What is the first term in the Fibonacci sequence to contain 1000 digits
'''

def fibonacci(n):
    phi = (1 + pow(5, 0.5))/2           #Golden Ratio
    return int((pow(phi, n) - pow(-phi, -n))/pow(5, 0.5))   #Formula: http://bit.ly/qDumIg


n = 0
while len(str(fibonacci(n))) < 1000:
    n += 1
print n

Вы знаете, что может быть причиной этой проблемы и как я могу изменить свойкод избежать этой проблемы?

Заранее спасибо.

Answer 1

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

Таким образом, поскольку вы используете аппроксимацию, используяВычисления с плавающей точкой, вы в конечном итоге получите эту проблему.

Вместо этого попробуйте вычислить последовательность Фибоначчи обычным способом, одно число (последовательности) за раз, пока не получите 1000 цифр.

есть.рассчитать 1, 1, 2, 3, 5, 8, 13, 21, 34 и т. д.

Под «обычным способом» я имею в виду следующее:

         /  1                        , n < 3
Fib(n) = |
         \  Fib(n-2) + Fib(n-1)      , n >= 3

Обратите внимание, что «очевидный»«Подход с учетом приведенных выше формул не подходит для этой конкретной проблемы, поэтому я опубликую код для неправильного подхода, просто чтобы убедиться, что вы не тратите время на это:

def fib(n):
    if n <= 3:
        return 1
    else:
        return fib(n-2) + fib(n-1)

n = 1
while True:
    f = fib(n)
    if len(str(f)) >= 1000:
        print("#%d: %d" % (n, f))
        exit()
    n += 1

На моей машине,приведенный выше код начинает работать действительно медленно около 30-го числа Фибоначчи, длина которого все еще составляет всего 6 цифр.

Я изменил рекурсивный подход, описанный выше, чтобы вывести количество вызовов функции fibдля каждого числа, и вот некоторые значения:

#1: 1
#10: 67
#20: 8361
#30: 1028457
#40: 126491971

Я могу показать, что первое число Фибоначчи с 1000 цифрами или более является 4782-м числом в последовательности (если я не просчитался), и поэтому числовызовы функции fib в рекурсивном подходе будут следующими:

И это всего лишь для 4782-го числа.Фактическое значение является суммой всех этих значений для всех чисел Фибоначчи от 1 до 4782. Нет никакого способа, которым это когда-либо завершится.

Фактически, если бы мы дали коду 1 год времени выполнения(упрощено до 365 дней), и, предполагая, что машина может совершать 10.000.000.000 вызовов каждую секунду, алгоритм получит до 83-го числа, которое по-прежнему всего 18 цифр.

Answer 2

Вы можете использовать трюк с скользящим окном , чтобы вычислять члены последовательности Фибоначчи итеративно, а не использовать закрытую форму (или делать это рекурсивно, как обычно это определено).

Версия Python для поиска fib(n) выглядит следующим образом:

def fib(n):
    a = 1
    b = 1
    for i in range(2, n):
        b = a + b
        a = b - a
    return b

Это работает, когда F (1) определяется как 1, как в Project Euler 25.

Я не буду давать точное решение проблемы здесь, но приведенный выше код может быть переработан, так что он отслеживает n, пока не будет достигнуто значение часового (10**999).

Answer 3

На самом деле, хотя приведенный выше совет, чтобы избежать чисел с плавающей точкой, как правило, хороший совет для задач Project Euler, в данном случае он неверен. Числа Фибоначчи могут быть вычислены по формуле F_n = phi ^ n / sqrt (5), так что первое число Фибоначчи, превышающее тысячу цифр, может быть вычислено как 10 ^ 999

Answer 4

Такое итеративное решение без проблем выполняется. Я получаю ответ менее чем за секунду.

def fibonacci():
    current = 0 
    previous = 1
    while True:
        temp = current
        current = current + previous
        previous = temp
        yield current


def main():
for index, element in enumerate(fibonacci()):
    if len(str(element)) >= 1000:
        answer = index + 1 #starts from 0
        break
print(answer)

Answer 5

Вы можете использовать тип данных Decimal.Это немного медленнее, но вы сможете иметь произвольную точность.

Итак, ваш код:

'''
What is the first term in the Fibonacci sequence to contain 1000 digits
'''

from Decimal import *

def fibonacci(n):
    phi = (Decimal(1) + pow(Decimal(5), Decimal(0.5))) / 2           #Golden Ratio
    return int((pow(phi, Decimal(n))) - pow(-phi, Decimal(-n)))/pow(Decimal(5), Decimal(0.5)))


n = 0
while len(str(fibonacci(n))) < 1000:
    n += 1
print n

Answer 6

Вот мое очень простое решение

list = [1,1,2]
for i in range(2,5000):
    if len(str(list[i]+list[i-1])) == 1000:
        print (i + 2)
        break
    else:
        list.append(list[i]+list[i-1])

Это своего рода "мошеннический" способ сделать это, но если вы измените 1000 на любое число, кроме одного, оно получится правильно.

Answer 7

import math as m
import time
start = time.time()
fib0 = 0
fib1 = 1
n = 0
k = 0
count = 1    
while k<1000 :
        n = fib0 + fib1
        k = int(m.log10(n))+1
        fib0 = fib1
        fib1 = n
        count += 1
print n 
print count
print time.time()-start

занимает 0,005388 с на моем компьютере.ничего не делал, просто следовал простому коду.Итерация всегда будет лучше.Рекурсия тоже заняла много времени.Также используется математическая функция для вычисления количества цифр в номере вместо того, чтобы брать число в списке и повторять его.Экономит много времени