Python Фибоначчи не имеет бесконечной точности? - PullRequest
Новая
       13

Python Фибоначчи не имеет бесконечной точности?

0 голосов
/ 10 октября 2011

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

fibonacci_matrix = numpy.matrix([[1,1],[1,0]])
def fib(n):
  return (fibonacci_matrix**(n-1)) [0,0]

fibonacci_matrix2 = numpy.matrix([[1L,1L],[1L,0L]])
def fib2(n):
  return (fibonacci_matrix2**(n-1)) [0,0]

def fib3(n):
  if n in [1,2]:
    return 1L
  else:
    return long(long(fib2(n-1))+long(fib2(n-2)))

print fib(47)
print fib2(93)
print fib3(95)

Что дает мне вывод: 

-1323752223
-6246583658587674878
-4953053512429003327

вместо положительных значений, как и все числа Фибоначчи.

Может ли кто-нибудь помочь решить эту проблему? Или еще лучше, помогите мне написать улучшенный, эффективный и бесконечно точный код последовательности Фибоначчи? Большая часть моего поиска в Google приводит к ужасным базовым медленным рекурсивным алгоритмам Фибоначчи.

Ответы [ 3 ]

4 голосов
/ 10 октября 2011

Вы можете заставить numpy использовать целые числа Python произвольной точности, установив dtype в object: 

>>> fibonacci_matrix = numpy.matrix([[1,1],[1,0]], dtype=object)
>>> def fib(n): return (fibonacci_matrix**(n-1)) [0,0]
>>> 
>>> fib(100)
    354224848179261915075L

но я не знаю, насколько это поможет. Обычно, если вы хотите действительно быструю реализацию некоторой рекурсивной функции, подобной этой, вы используете различные идентификаторы для выполнения сокращений. Например, использование тождества F (2 * n) = F (n + 1) ^ 2-F (n-1) ^ 2 позволяет получить хорошую логарифмическую оценку. [На самом деле, в Википедии приведено обобщение, которое даже лучше.]

Есть ли какая-то причина, по которой вам действительно нужна скорость?

4 голосов
/ 10 октября 2011

Вы видите переполнение.Предполагая, что long является 32-битным, диапазон значений, которые он может хранить, равен -2^31 .. 2^31 - 1, а 47-е число Фибоначчи - 2971215073.

Чтобы сделать это точно, вам нужны большие целые числа.Python поддерживает их изначально, но я не думаю, что numpy поддерживает их ...

В качестве чистого примера Python: 

def fib4(n):
    x=[1,1]
    for i in xrange(n-2):
        x.append(x[-1]+x[-2])
    return x[-1]

Это заставляет Python использовать в вычислении большие целые значения.

0 голосов
/ 04 августа 2016

Относительно " эффективного и бесконечно точного кода последовательности Фибоначчи " в python: простые серии рекурсии, подобные этой, можно быстро и легко вычислить, используя аргумент out для numpy ufunc s.Точность по соответствующему типу данных.

Хотя и в случае чисел Фибоначчи со стандартными семенами - их не так много в разумных количественных пределах, и вы можете использовать расширенные математические свойства - это может представлять общий интерес: 

>>> a = np.zeros(102, object)
>>> a[1] = 1; a[0] = 0
>>> np.add(a[:-2], a[1:-1], out=a[2:])
array([1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
       2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
       317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
       14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
       ....
       7540113804746346429, 12200160415121876738, 19740274219868223167,
       31940434634990099905, 51680708854858323072, 83621143489848422977,
       135301852344706746049, 218922995834555169026, 354224848179261915075,
       573147844013817084101], dtype=object)
>>> a[100]
354224848179261915075L
>>> a[51]**2 - a[49]**2
354224848179261915075L
>>>
...