有几十种方法可以计算任意n的F(n)，其中许多方法具有很好的运行时和内存使用率。
然而，假设我想问相反的问题：
给定 n > 2 的 F(n)，n是多少？
（n > 2的限制在这里是因为F(1) = F(2) = 1且没有明确的逆函数）。
解决此问题的最有效方法是什么？ 枚举斐波那契数并在达到目标数字时停止可以在线性时间内轻松完成，但是否有比那更快的方法呢？
编辑：当前，此处发布的最佳解决方案在O（log n）的时间内运行，使用O（log n）的内存，假设数学运算在O（1）时间内运行，并且机器字可以在O（1）空间中保存任何数字。 我想知道是否可能降低内存要求，因为您可以使用O（1）空间计算斐波那契数。
由于 OP 要求矩阵的解法不能涉及任何浮点计算，因此我们可以通过以下方式实现 O(logn) 的复杂度，假设数值操作具有 O(1) 的复杂度。
让我们考虑一个 2x2 矩阵 A，具有以下结构：
1 1
1 0
(8, 5)，它存储两个连续的斐波那契数。如果你将它乘以这个矩阵，你会得到(8*1 + 5*1，8*1 + 5*0) = (13, 8) - 下一个斐波那契数。A^n * (1, 0) = (f(n), f(n - 1))。A^2，A^4，A^8等，直到我们达到所需的数字。A的幂进行二分查找。f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t)的序列都可以用这种方法表示。A ^ 16处传递了f，因此我们在范围[0,16]内进行二分查找。 mid为8，并且我们已经计算出了A ^ 8。 假设f> A ^ 8，则范围缩小为[8,16]。 现在mid为12，但是A ^ 12是A ^ 8 * A ^ 4。 8是当前搜索边界，4是2的幂：因此我们已经计算并可以通过一次乘法计算A ^ 12。 以此类推。 - Nikita Rybakn，因此无法分解它。或者我在你的想法中错过了什么？ - Nikita Rybakn(F) 是计算给定的 F(n) 中 n 的最快方法（忽略了 n(1) 返回 2 的事实）。然而，它并不保证 F 实际上是斐波那契数列的成员（对于很大的 F，其周围的数字将给出相同的结果）。 - Michelle Tilleyphi * n - (1.0 / n) 和 phi * n + (1.0 / n) 是否跨越了一个正整数。例如，对于 n = 144，你会得到 232.9899 和 233.0038，它们跨越了 233。对 n = 143 进行相同的计算得到 231.3718 和 231.3858，因此不是一个斐波那契数。 - Michelle Tilley如果你可以轻松理解F(n)的二进制表示，
你可能会对常数1.7和1.1感到怀疑。它们之所以有效是因为d*1.44042009041... + C很难接近整数。
如果有兴趣，我明天可以发布推导过程。
这里是一个n从2到91的表格，显示了进行floor操作之前的公式结果：
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
按照计算未限定单词数的内存使用量有点愚蠢，但只要这是模型，就有一种类似于Nikita Rybak的O(log n)时间复杂度，O(1)单词数解决方案，其本质上通过计算基于斐波那契数列（YO DAWG）的 Zeckendorf表示法来计算n。
定义矩阵
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 + 1) = A^F(k - 1) * A^F(k)
通过矩阵求逆和乘法进行反向计算
A^F(k - 1) = A^F(k + 1) (A^F(k))^-1,
假设我们将所有内容都存储为有理数（以避免假定存在单位成本除法），那么只需 八 六 十二个单词即可构建双向迭代器。其余的工作只是调整这个O(1)空间算法来查找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]
logn 的内存吗？你是否还制作了所有 A^F(n) 幂的列表？ - Thomas Ahlefib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5)，其中phi = (1+sqrt(5)) / 2，即黄金分割数（参见此链接）。您可以尝试查找上述斐波那契函数的数学反函数，或者在32/64次操作中使用二进制搜索（具体取决于您可搜索的最大值），以找到与给定斐波那契数相匹配的n值（通过计算fib(n)并根据它与给定斐波那契数的大小关系将样本空间分为两部分，然后尝试每个n值）。编辑：@rcollyer的解决方案更快，因为我的解法是O(lg n)，而他发现的解法是O(1)=常量时间。
您可以在O(1)时间和O(1)空间内找到任何Fib(n)的n值。
您可以使用固定点CORDIC算法，仅使用整数数据类型上的移位和加法运算来计算ln()。
如果x = Fib(n)，那么可以通过以下方式确定n：
n = int(2.0801 * ln(x) + 2.1408)
CORDIC运行时间取决于所需的精度级别。这两个浮点值将被编码为定点值。
这个提议唯一的问题是它返回了不在斐波那契数列中的数字的值，但原始问题明确说明函数的输入将是Fib(n)，这意味着只使用有效的斐波那契数。
我认为这个问题可以在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写成二进制形式bk-1bk-2...b1b0。这意味着
n = 2k-1 bk-1 + 2k-2 bk-2 + ... + 21 b1 + 20 b0。
这意味着
F(n) = ⌊ Φ2k-1 bk-1 + 2k-2 bk-2 + ... + 21 b1 + 20 b0 / √5 ⌋
或者，更易读的是
F(n) = ⌊ Φ2k-1 bk-1Φ2k-2 bk-2 ... Φ21 b1Φ20 b0 / √5 ⌋
这表明了以下算法。首先，开始计算所有k的Φ2k，直到你计算出一个数字Φz，使得 ⌊ Φz / √5 ⌋ 大于你的数F(n)。现在，从那里开始，向后迭代通过这种方式生成的所有Φ的幂次。如果当前数字大于指示的Φ的幂次，则将其除以该幂次，并记录该数字被除以该值。这个过程通过一次减去可以获得n的一个位。因此，一旦完成，就会找到n。n 的增加也会遇到相同的问题。只是在这里我们需要很多小数点后面的数字，而使用矩阵乘法时我们需要更大的数字。 - Nikita Rybak斐波那契数列的闭合形式公式为：
Fn = Round(φ^n / Sqrt(5))
其中φ是黄金比例。
如果我们忽略舍入因素，这是可逆的，其反函数为：
F(-1)n= log(n*Sqrt(5))/logφ
由于我们忽略了舍入因子，所以公式中存在一个错误，可以进行计算。然而，如果我们认为一个数字n是斐波那契数，当且仅当区间[n*φ - 1/n, n*φ + 1/n]包含一个自然数时，则：
一个数字是斐波那契数，当且仅当区间[n*φ - 1/n, n*φ + 1/n]包含一个自然数，并且该数字在斐波那契序列中的索引由四舍五入log(n*Sqrt(5))/logφ给出
这应该可以在（伪）常数时间内完成，具体取决于用于计算对数和平方根等的算法。
编辑：φ = (1+Sqrt(5))/2
编辑：没关系了。问者在评论中已经说明指数运算肯定不是常数时间。
指数运算是否是您允许在常数时间内执行的数学运算之一？如果是，我们可以通过闭式公式以常数时间计算F(n)。然后，给定一些F，我们可以执行以下操作：
如果F = F(n)，则第一部分需要k = O(log(n))步。第二部分是对大小为O(2^k)的范围进行二分查找，因此它也需要k = O(log(n))。因此，总体而言，如果我们在O(1)时间内进行指数运算（这是一个很大的“如果”），则我们具有O(log(n))时间和O(1)空间。
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，以便可以高效地增加和减少隐式变量k。
好的，那么我们如何使用它来解决问题呢？我发现创建一个包装器来隐藏矩阵细节对于我们的斐波那契表示法很有用。在实践中（对于斐波那契搜索器而言），您将希望手动内联所有内容。这将使您免受矩阵冗余的困扰，并在矩阵求逆方面进行一些优化。
import numpy as np
class Fib:
def __init__(self, k, M):
""" `k` is the 'name' of the fib, e.g. 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]
然而这段代码确实可用，所以我们可以按照以下方式进行测试。请注意，搜索功能与当我们的对象是整数而不是斐波那契数列时几乎没有什么不同。
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+a-b, b-a
else:
hi = mi
a, b = b-a, a
return lo.k
>>> search(lambda n: n <= 144)
12
>>> search(lambda n: n <= 0)
0
我刚意识到我们根本不需要除法。 F_n矩阵的行列式只是(-1)^n，因此我们实际上可以在不使用除法的情况下完成所有操作。在下面的内容中，我删除了所有矩阵代码，但保留了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 <= 2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125)
20000