Python斐波那契没有无限精度？

发布于 2024-12-09 02:47:17 字数 667 浏览 0 评论 0原文

我尝试在 python 中编写一个快速斐波那契算法，该算法可用于极大的值，但我不断得到负值，所以我假设它没有正确使用长整型？

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

而不是像所有斐波那契数那样的正值。

有人可以帮忙解决这个问题吗？或者更好地帮助我编写一个改进的、高效的和无限准确的斐波那契序列代码？我的大部分谷歌搜索都会产生糟糕的基本缓慢递归斐波那契算法。

原文

I'm try to write a fast fibonacci algorithm in python that can be used for extremely large values, but I keep getting negative values, so I'm assuming its not properly using 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)

Which gives me output:

-1323752223
-6246583658587674878
-4953053512429003327

instead of positive values like all fibonacci numbers should be.

Can someone help troubleshoot this? Or better yet help me write an improved, efficient and infinetly accurate fibonnaci sequence code? Most of my googling yields terrible basic slow recursive fibonnacci algorithms.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

栀子花开つ 2024-12-16 02:47:17

您看到溢出。假设 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在计算中使用更大的整数值。

You are seeing overflow. Assuming a long is 32-bit, the range of values that it can store is -2^31 .. 2^31 - 1 and the 47th fibonacci number is 2971215073.

To do this accurately you need larger integers. Python supports them natively, but I dont think numpy supports them ...

As a pure python example:

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

This forces python to use larger integer values in calculation.

回复收藏 0 原文

圈圈圆圆圈圈 2024-12-16 02:47:17

您可以通过将 dtype 设置为 object: 来使 numpy 使用 Python 任意精度整数：

>>> 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 可以进行很好的对数评估。 [实际上，维基百科列出了对此的概括，甚至更好。]

你真的需要速度吗？

You can make numpy use Python arbitrary-precision integers by setting the dtype to object:

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

but I don't know how much that will help. Usually if you want a really fast implementation of some recursive function like this, you use the various identities to do reductions. For example, using the identity F(2*n) = F(n+1)^2-F(n-1)^2 allows a nice logarithmic evaluation. [Actually, Wikipedia lists a generalization of this which is even better.]

Is there some reason you really need speed?

回复收藏 0 原文

凉墨 2024-12-16 02:47:17

关于 python 中的“高效且无限准确的斐波那契序列代码”：通过利用 numpy ufunc< 的 out 参数，可以快速轻松地计算这样的简单递归序列/代码>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
>>>

Regarding "efficient and infinetly accurate fibonnaci sequence code" in python: Simple recursion series like this can be computed fast and easy by exploiting the out argument of numpy ufuncs. Precision by appropriate data type.

Albeit in the case of fibonacci numbers with standard seeds - there are not much within reasonable numerical scope and you could exploit advanced mathematical properties - this might be of general interest:

>>> 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
>>>

回复收藏 0 原文

~没有更多了~