反向斐波那契algorithm？

对于任意的n有很多种计算F（n）的方法，其中许多有很好的运行时和内存使用。

但是，假设我想问一个相反的问题：

给定F（n）n> 2，n是什么？

（因为F（1）= F（2）= 1，所以n> 2限制在那里，并且没有明确的逆）。

什么是解决这个问题最有效的方法？ 通过枚举Fibonacci数字并在达到目标数字时停止，这很容易在线性时间内完成，但有没有更快的方法做到这一点？

编辑：目前，这里发布的最好的解决scheme运行在O（log n）时间使用O（log n）内存，假设math运算在O（1）运行，并且机器字可以容纳任何数字在O（1）空间。 我很好奇，如果可以减less内存需求，因为你可以使用O（1）空间来计算斐波纳契数。

Answer 1

由于OP询问了不涉及任何浮点计算的matrix解决scheme，在这里。 我们可以用这种方法来实现O(logn)复杂度，假设数字操作具有O(1)复杂性。

我们来看下面的结构的2x2matrixA

 1 1 1 0 

现在考虑vector(8, 5) ，存储两个连续的斐波那契数。 如果你乘以这个matrix，你会得到(8*1 + 5*1, 8*1 + 5*0) = (13, 8) – 下一个斐波那契数。
如果我们推广， A^n * (1, 0) = (f(n), f(n - 1)) 。

实际的algorithm需要两步。

1. 计算A^2 ， A^4 ， A^8等，直到我们通过所需的数字。
2. 用n计算能力做一个二分search。

在附注中，formsf(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(nt)可以像这样呈现。

Answer 2

维基百科给出了结果

 n(F) = Floor[ Log(F Sqrt(5))/Log(Phi) + 1/2] 

Phi是黄金比例。

Answer 3

如果你可以很容易地解释二进制F（n）

你可能会怀疑常数1.7和1.1。 这些工作，因为d * 1.44042009041 + C永远不会非常接近一个整数。

如果有兴趣，我可以在明天发布一个派生。

这里是一个表格，n = 2到91，表示地板前的公式结果：

  n formula w/o floor F(n) F(n) in binary 2 2.540 1 1 3 3.981 2 10 4 4.581 3 11 5 5.421 5 101 6 6.862 8 1000 7 7.462 13 1101 8 8.302 21 10101 9 9.743 34 100010 10 10.343 55 110111 11 11.183 89 1011001 12 12.623 144 10010000 13 13.223 233 11101001 14 14.064 377 101111001 15 15.504 610 1001100010 16 16.104 987 1111011011 17 17.545 1597 11000111101 18 18.385 2584 101000011000 19 19.825 4181 1000001010101 20 20.425 6765 1101001101101 21 21.266 10946 10101011000010 22 22.706 17711 100010100101111 23 23.306 28657 110111111110001 24 24.147 46368 1011010100100000 25 25.587 75025 10010010100010001 26 26.187 121393 11101101000110001 27 27.028 196418 101111111101000010 28 28.468 317811 1001101100101110011 29 29.068 514229 1111101100010110101 30 30.508 832040 11001011001000101000 31 31.349 1346269 101001000101011011101 32 32.789 2178309 1000010011110100000101 33 33.389 3524578 1101011100011111100010 34 34.230 5702887 10101110000010011100111 35 35.670 9227465 100011001100110011001001 36 36.270 14930352 111000111101000110110000 37 37.111 24157817 1011100001001111001111001 38 38.551 39088169 10010101000111000000101001 39 39.151 63245986 11110001010000111010100010 40 40.591 102334155 110000110010111111011001011 41 41.432 165580141 1001110111101000110101101101 42 42.032 267914296 1111111110000000110000111000 43 43.472 433494437 11001110101101001100110100101 44 44.313 701408733 101001110011101010010111011101 45 45.753 1134903170 1000011101001010011111110000010 46 46.353 1836311903 1101101011100111110010101011111 47 47.193 2971215073 10110001000110010010010011100001 48 48.634 4807526976 100011110100011010000101001000000 49 49.234 7778742049 111001111101001100010111100100001 50 50.074 12586269025 1011101110001100110011100101100001 51 51.515 20365011074 10010111101110110010110100010000010 52 52.115 32951280099 11110101100000011001010000111100011 53 53.555 53316291173 110001101001111001100000101001100101 54 54.396 86267571272 1010000010101111100101010110001001000 55 55.836 139583862445 10000001111111110110001011011010101101 56 56.436 225851433717 11010010010101110010110110001011110101 57 57.276 365435296162 101010100010101101001000001100110100010 58 58.717 591286729879 1000100110101011011011110111110010010111 59 59.317 956722026041 1101111011000001000100111001011000111001 60 60.157 1548008755920 10110100001101100100000110001001011010000 61 61.598 2504730781961 100100011100101101100101101010100100001001 62 62.198 4052739537881 111010111110011010000110011011101111011001 63 63.038 6557470319842 1011111011011000111101100000110010011100010 64 64.478 10610209857723 10011010011001100001110010100010000010111011 65 65.078 17167680177565 11111001110100101001011110101000010110011101 66 66.519 27777890035288 110010100001110001011010001001010011001011000 67 67.359 44945570212853 1010001110000010110100101111110010101111110101 68 68.800 72723460248141 10000100010010001000000000000111101001001001101 69 69.400 117669030460994 11010110000010011110100110000101111111001000010 70 70.240 190392490709135 101011010010100100110100110001101101000010001111 71 71.681 308061521170129 1000110000010111000101001100010011100111011010001 72 72.281 498454011879264 1110001010101011101011110010100001001111101100000 73 73.121 806515533049393 10110111011000010110000111110110100110111000110001 74 74.561 1304969544928657 100101000101101110011100110001010110000110110010001 75 75.161 2111485077978050 111100000000110001001101110000001010111101111000010 76 76.602 3416454622906707 1100001000110011111101010100001100001000100101010011 77 77.442 5527939700884757 10011101000111010000111000010001101100000010100010101 78 78.042 8944394323791464 11111110001101110000100010110011001101000111001101000 79 79.483 14472334024676221 110011011010101000001011011000100111001001001101111101 80 80.323 23416728348467685 1010011001100010110001111101111000000110010000111100101 81 81.764 37889062373143906 10000110100110111110011011000111100111111011010101100010 82 82.364 61305790721611591 11011001110011010100101010110110101000101101011101000111 83 83.204 99194853094755497 101100000011010010011000101111110010000101000110010101001 84 84.644 160500643816367088 1000111010001101100111110000110100111001010110001111110000 85 85.244 259695496911122585 1110011010100111111010110110110011001001111111000010011001 86 86.085 420196140727489673 10111010100110101100010100111101000000011010101010010001001 87 87.525 679891637638612258 100101101111011101011101011110011011001101010100010100100010 88 88.125 1100087778366101931 111101000100010011000000000110000011010000101001100110101011 89 89.566 1779979416004714189 1100010110011110000011101100100011110011101111101111011001101 90 90.406 2880067194370816120 10011111111000000011011101101010100001101110100111100001111000 91 91.846 4660046610375530309 100000010101011110011111011001111000000001100100101011101000101 

“

Answer 4

通过计算无界词语来衡量内存使用情况是很愚蠢的，但只要是模型，就有一个O（log n）时间，类似于Nikita Rybak的O（1）词语解决scheme，实质上是通过Zeckendorf表示来计算n基于斐波纳契数（YO DAWG）。

定义matrix

  1 1 A = , 1 0 

满足

  F(m + 1) F(m) A^m = . F(m) F(m - 1) 

我们将使用序列A^F(k)来代替序列A^(2^k) A^F(k) 。 后一个序列具有可以用matrix乘法向前移动的特性

 A^F(k + 1) = A^F(k - 1) * A^F(k) 

后面是matrix的逆和乘法

 A^F(k - 1) = A^F(k + 1) (A^F(k))^-1, 

所以我们可以build立一个只有八 六十二个单词的双向迭代器，假设我们把所有东西都存储为有理数（以避免假设存在单位成本差异）。 其余的只是适应这个O（1） – 空间algorithmfind一个Zeckendorf表示。

 def zeck(n): a, b = (0, 1) while b < n: a, b = (b, a + b) yield a n1 = a while n1 < n: a, b = (b - a, a) if n1 + a <= n: yield a n1 += a a, b = (b - a, a) >>> list(zeck(0)) [0] >>> list(zeck(2)) [1, 1] >>> list(zeck(12)) [8, 3, 1] >>> list(zeck(750)) [610, 89, 34, 13, 3, 1] 

Answer 5

已经certificate，fib n的公式为：其中phi = (1+sqrt(5)) / 2 fib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5) phi = (1+sqrt(5)) / 2 ，黄金分割号码。 （见这个链接 ）。

你可以尝试find一个与上面的fib函数相反的math运算，或者在32/64的运算中进行二分search（取决于你的可search最大值有多大）来find匹配数字的n（通过计算fib来尝试每个n （n），根据fib（n）与给定的斐波那契数相比，将样本空间分成两部分。

编辑：@ rcollyer的解决scheme更快，因为我在O（lg n），他发现的是在O（1）=常量时间。

Answer 6

所以我正在考虑这个问题，我认为有可能在O（lg n）时间内使用O（lg n）内存。 这是基于这样一个事实

F（n）=（1 /√5）（Φn – φn）

其中Φ=（1 +√5）/ 2和φ= 1 – Φ。

第一个观察是对于任何n> 1，φn <1。这意味着对于任何n> 2，我们都有

F（n）=⌊Φn /√5⌋

现在，取n并以二进制写成b _k-1 b _k-2 … b ₁ b ₀ 。 这意味着

n = 2 ^k-1 b _k-1 + 2 ^k-2 b _k-2 + … + 2 ¹ b ₁ + 2 ⁰ b ₀ 。

这意味着

F（n）=⌊Φ2 ^k-1 b _k-1 + 2 ^k-2 b _k-2 + … + 2 ¹ b ₁ + 2 ⁰ b ₀ /√5⌋

或者，更可读，那

F（n）=Φ2 ^k-1 b _k- 1Φ2 ^k-2 b _k-2 …Φ2 ¹ b 1Φ2 ⁰ b ₀ /√5⌋

这提示了以下algorithm。 首先，开始计算所有k的Φ2 k，直到你计算一个数字Φz，使得⌊Φz /√5⌋大于你的数字F（n）。 现在，从那里，通过这种方式产生的Φ的所有权力迭代。 如果当前数字大于Φ的指示功率，则将其除以Φ的幂数，并logging该数字除以该数值。 这个过程基本上是通过减去一次可以减less的2的最大次幂来恢复n的一个比特。 因此，一旦你完成了，你会findn。

这个algorithm的运行时间是O（lg n），因为你可以通过重复平方生成Φ2 ⁱ ，我们只生成O（lg n）项。 内存使用量为O（lg n），因为我们存储了所有这些值。

Answer 7

您可以在O（1）时间和O（1）空间中find任何Fib（n）的n。

您可以使用定点CORDICalgorithm仅使用移位计算ln（）并添加整数数据types。

如果x = Fib（n），那么n可以通过确定

  n = int(2.0801 * ln(x) + 2.1408) 

CORDIC运行时间由所需的精确度决定。 这两个浮点值将被编码为定点值。

这个提议的唯一问题是，它返回的数字不是斐波那契数列的值，但是原始问题明确指出函数的input是Fib（n），这意味着只有有效的斐波纳契数是用过的。

Answer 8

编辑：没关系。 提问者在评论中指出，求幂绝对不是一个固定的时间。

---

幂指数是math运算之一，你可以在不变的时间吗？ 如果是这样，我们可以通过闭式公式计算F（n）在恒定时间内。 然后，给定一些F，我们可以做到以下几点：

1. 计算F（1），F（2），F（4），F（16），F（256）…直到F（2 ^ k）<= F <F（2 ^ {k + 1}）
2. 在2 ^ k和2 ^ {k + 1}之间进行二进制search直到F（i）<= F <F（i + 1）

如果F = F（n），那么第一部分取k = 0（log（n））步。 第二部分是在O（2 ^ k）大小范围内的二进制search，所以它也需要k = 0（log（n））。 所以，总的来说，我们在O（1）空间中有O（log（n））的时间，如果我们在O（1）的时间中有指数运算，

Answer 9

斐波那契数列公式的封闭forms是：

 Fn = Round(φ^n / Sqrt(5)) 

其中φ是黄金比例。

如果我们忽略舍入因子，这是可逆的，反函数是：

 F(-1)n= log(n*Sqrt(5))/logφ 

因为我们忽略了舍入因子，所以可以计算公式中的误差。 然而，如果我们认为如果区间[n *φ-1 / n，n *φ+ 1 / n]包含一个自然数，则n是一个Fibonacci数，则：

如果区间[n *φ-1 / n，n *φ+ 1 / n]包含一个自然数并且Fibonacci序列中的数字指数由四舍五入log（n * Sqrt（5）给出），则数是一个斐波那契数。 ）/logφ

这应该在（伪）恒定时间内可行，取决于用于计算对数和平方根等的algorithm。

编辑：φ=（1 + Sqrt（5））/ 2

Answer 10

这可能类似于user635541的答案。 我不完全明白他的做法。

使用其他答案中讨论的Fibonacci数的matrix表示，我们得到一个方法，从F_n和F_m到F_{n+m}和F_{nm}在常量时间，只使用加，乘，减和除不！看到更新 ）。 我们也有一个零（单位matrix），所以它是一个math小组！

通常在进行二分查找时，我们也需要一个除法运算符来取平均值。 或者至less除以2.然而，如果我们想从F_{2n}去F_n它需要一个平方根。 幸运的是，事实certificate，加号和减号是我们所需要的对数时间“接近”二分查找！

维基百科写道这个方法，讽刺地叫做Fibonacci_search ，但这篇文章写得不是很清楚，所以我不知道它跟我的方法是否一模一样。 理解用于斐波纳契search的斐波纳契数与我们正在寻找的数没有任何关系是非常重要的。 这有点令人困惑。 为了演示这种方法，下面首先使用加号和减号来实现标准的“二分查找”

 def search0(test): # Standard binary search invariants: # i <= lo then test(i) # i >= hi then not test(i) # Extra invariants: # hi - lo = b # a, b = F_{k-1}, F_k a, b = 0, 1 lo, hi = 0, 1 while test(hi): a, b = b, a + b hi = b while b != 1: mi = lo + a if test(mi): lo = mi a, b = 2*a - b, b - a else: hi = mi a, b = b - a, a return lo >>> search0(lambda n: n**2 <= 25) 5 >>> search0(lambda n: 2**n <= 256) 8 

这里test是一些布尔函数; a和b是连续斐波那契数f_k和f_{k-1} ，使得出上界hi和下界lo之间的差总是f_k 。 我们需要a和b所以我们可以有效地增加和减less隐式variablesk 。

好的，那我们怎么用这个来解决这个问题呢？ 我发现围绕我们的斐波那契表示创build一个包装，这隐藏了matrix细节。 在实践中（斐波那契search器有这样的事情吗？）， 你会想要手动内联一切 。 这样可以避免matrix中的冗余，并在matrix求逆的基础上做一些优化。

 import numpy as np class Fib: def __init__(self, k, M): """ `k` is the 'name' of the fib, eg k=6 for F_6=8. We need this to report our result in the very end. `M` is the matrix representation, that is [[F_{k+1}, F_k], [F_k, F_{k-1}]] """ self.k = k self.M = M def __add__(self, other): return Fib(self.k + other.k, self.M.dot(other.M)) def __sub__(self, other): return self + (-other) def __neg__(self): return Fib(-self.k, np.round(np.linalg.inv(self.M)).astype(int)) def __eq__(self, other): return self.k == other.k def value(self): return self.M[0,1] 

但是代码确实起作用，所以我们可以按如下方式进行testing。 注意，当我们的对象是整数而不是斐波那契数组时，search函数有多less不同。

 def search(test): Z = Fib(0, np.array([[1,0],[0,1]])) # Our 0 element A = Fib(1, np.array([[1,1],[1,0]])) # Our 1 element a, b = Z, A lo, hi = Z, A while test(hi.value()): a, b = b, a + b hi = b while b != A: mi = lo + a if test(mi.value()): lo = mi a, b = a+ab, ba else: hi = mi a, b = ba, a return lo.k >>> search(lambda n: n <= 144) 12 >>> search(lambda n: n <= 0) 0 

剩下的问题是，是否有一个有效的searchalgorithmmonoids。 这是一个不需要减/加法逆。 我的猜测是：没有减去，你需要额外的记忆尼基塔Rybak。

更新

我只是意识到我们根本不需要分工。 F_nmatrix的行列式只是(-1)^n ，所以我们实际上可以做所有的事情而不分割。 在下面我删除了所有的matrix代码，但我保留了Fib类，只是因为一切都非常混乱，否则。

 class Fib2: def __init__(self, k, fp, f): """ `fp` and `f` are F_{k-1} and F_{k} """ self.k, self.fp, self.f = k, fp, f def __add__(self, other): fnp, fn, fmp, fm = self.fp, self.f, other.fp, other.f return Fib2(self.k + other.k, fn*fm+fnp*fmp, (fn+fnp)*fm+fn*fmp) def __sub__(self, other): return self + (-other) def __neg__(self): fp, f = self.f + self.fp, -self.f return Fib2(-self.k, (-1)**self.k*fp, (-1)**self.k*f) def __eq__(self, other): return self.k == other.k def value(self): return self.f def search2(test): Z = Fib2(0, 1, 0) A = Fib2(1, 0, 1) ... >>> search2(lambda n: n <= 280571172992510140037611932413038677189525) 200 >>> search2(lambda n: n <= 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125) 2000 >>> search2(lambda n: n <= ) 20000 

这一切都像一个魅力。 我唯一担心的是这种计算复杂性的主导，我们可能刚刚做了一个顺序search。 或者实际上，只要看一下数字就可以告诉你几乎所有你正在看的东西。 虽然这不是很有趣。