Python 中的 1000 位数字

Question

我在解决 Euler 项目时遇到了一个问题，该问题问我前 1000 位斐波那契数的索引。

我首先使用了这段代码，但花费了太多时间。

def fibonacci(num):
    if (num==0):
        return 0;
    if(num==1):
        return 1;
    return fibonacci(num-1) + fibonacci(num-2);


def numOfDigits(num):
    numOfDigits = 0;
    while (num>0):
        num = num/10;
        numOfDigits += 1;
    return numOfDigits;

def main():
    n=0;
    while(n>=0):
        fib = fibonacci(n);
        num = numOfDigits(fibonacci(n));
        print n,"\t",fib;
        if(num>=1000):
            break;
        n+=1;
    print "answer:",n;
main();

然后我用 google 搜索了一下，发现 binnet's formula 使它变得非常快。

import math as mt;

def fibonacci(num):
    phi = (mt.sqrt(5)+1.00)/2.00;
    return ((phi**num)-((-phi)**(-num)))/mt.sqrt(5);

def numOfDigits(num):
    numOfDigits = 0;
    while (num>0):
        num = num/10;
        numOfDigits += 1;
    return numOfDigits;

def main():
    n=0;
    while(n>=0):
        fib = fibonacci(n);
        num = numOfDigits(fibonacci(n));
        print n,"\t",fib;
        if(num>=1000):
            break;
        n+=1;
    print "answer:",n;
main();

但是问题就出现在这里：

1471    1.17851144788e+307
1472    1.9068715788e+307
1473    3.08538302668e+307
1474    4.99225460548e+307
Traceback (most recent call last):
  File "src/ThousandDigitFibonacciNum.py", line 29, in <module>
    main();
  File "src/ThousandDigitFibonacciNum.py", line 22, in main
    fib = fibonacci(n);
  File "src/ThousandDigitFibonacciNum.py", line 10, in fibonacci
    return ((phi**num)-((-phi)**(-num)))/mt.sqrt(5);
OverflowError: (34, 'Result too large')

第一个疑惑是结果太大return还是计算不了？那么解决这个问题的方法是什么？

Answer 1

对于每个 n，您正在重新计算所有斐波那契数 F(1)...F(n-1) 以便计算 F(n)。相反，您只能计算每个斐波那契数一次，检查每个数是否具有适当的位数：

def fibo():
    a = 0
    b = 1
    while True:
        yield a
        a, b = b, a+b

for index, number in enumerate(fibo()):
    if len(str(number)) == 1000:
        print(index)
        break

Python 中的 1000 位数字

1000-Digit Number in Python

python-2.7

fibonacci

largenumber