任意の n に対して F(n) を計算する方法は数十ありますが、その多くは実行時間とメモリの使用量が大きくなります。
ただし、逆の質問をしたいとします。
n > 2 に対して F(n) が与えられた場合、n は何ですか?
（F（1）= F（2）= 1であり、明確な逆がないため、n> 2の制限があります）。
この問題を解決する最も効率的な方法は何でしょうか? フィボナッチ数を列挙し、目標数に達すると停止することで線形時間でこれを行うのは簡単ですが、それよりも速くこれを行う方法はありますか?
EDIT：現在、ここに投稿された最良の解決策は、O（1）で実行され、機械語がO（1）空間に任意の数を保持できると仮定して、O（log n）メモリを使用してO（log n）時間で実行されます. O(1) 空間を使用してフィボナッチ数を計算できるため、メモリ要件を下げることができるかどうか興味があります。
OPは、浮動小数点計算を含まない行列解について尋ねたので、ここにあります。O(logn)数値演算が複雑であると仮定すると、この方法で複雑さを実現できO(1)ます。
A次の構造を持つ2x2行列を考えてみましょう
1 1
1 0
(8, 5)次に、2 つの連続するフィボナッチ数を格納するvector を考えます。これにこの行列を掛けると(8*1 + 5*1, 8*1 + 5*0) = (13, 8)、次のフィボナッチ数が得られます。
一般化すると、A^n * (1, 0) = (f(n), f(n - 1)).
実際のアルゴリズムは 2 つの手順を実行します。
A^2、A^4、A^8などを、目的の数を超えるまで計算します。nの累乗を計算して、による二分探索を行いAます。余談ですが、フォームの任意のシーケンスをf(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t)このように表示できます。
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
'
無制限の単語をカウントしてメモリ使用量を測定するのはばかげていますが、それがモデルである限り、本質的にZeckendorf 表現を介して計算する Nikita Rybak のソリューションに似たO(log n) 時間、O(1) ワードのソリューションがあります。フィボナッチ数 (YO DAWG) に基づいています。n
マトリックスを定義する
1 1
A = ,
1 0
満たす
F(m + 1) F(m)
A^m = .
F(m) F(m - 1)
sequence の代わりに、 sequenceA^(2^k)を使用しますA^F(k)。後者のシーケンスには、行列乗算で前に進むことができるというプロパティがあります
A^F(k + 1) = A^F(k - 1) * A^F(k)
逆行列と乗算による逆方向
A^F(k - 1) = A^F(k + 1) (A^F(k))^-1,
そのため、すべてを有理数として格納すると仮定すると (単位コスト分割の存在を想定しないようにするため) 、 8 6 12 ワードのみで双方向反復子を作成できます。残りは、ゼッケンドルフ表現を見つけるために、この O(1) 空間アルゴリズムを適応させるだけです。
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]
fib n の公式はfib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5)どこphi = (1+sqrt(5)) / 2、黄金分割数であることが証明されています。（このリンクを参照してください）。
上記の fib 関数の数学的逆関数を見つけようとするか、32/64 操作でバイナリ検索を実行して (検索可能な最大値の大きさに応じて)、数値に一致する n を見つけることができます (fib を計算して各 n を試してください) (n) と fib(n) が指定されたフィボナッチ数とどのように比較されるかに応じて、サンプル空間を 2 つに分割します)。
編集: @rcollyer のソリューションはより高速です。私のソリューションは O(lg n) にあり、彼が見つけたソリューションは O(1) = 定数時間にあるためです。
だから私はこの問題について考えていました.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 を 2 進数で b k-1 b k-2 ...b 1 b 0と書きます。この意味は
n = 2 k-1 b k-1 + 2 k-2 b k-2 + ... + 2 1 b 1 + 2 0 b 0 .
この意味は
F(n) = ⌊ Φ 2 k-1 b k-1 + 2 k-2 b k-2 + ... + 2 1 b 1 + 2 0 b 0 / √5 ⌋
または、より読みやすいように、
F(n) = ⌊ Φ 2 k-1 b k-1 Φ 2 k-2 b k-2 ... Φ 2 1 b 1 Φ 2 0 b 0 / √5 ⌋
これは、次のアルゴリズムを示唆しています。最初に、数値 F(n) よりも大きい⌊ Φ z / √5 ⌋ となるような数値 Φ zを計算するまで、すべての k に対してΦ 2 kの計算を開始します。ここから、この方法で生成した Φ のすべての累乗にわたって逆方向に反復します。現在の数値が指定された Φ のべき乗より大きい場合は、その数値を Φ のべき乗で割り、その数値をこの値で割ったことを記録します。このプロセスでは、一度に最大の 2 の累乗を減算することで、基本的に n の 1 ビットを一度に復元します。したがって、作業が完了すると、n が見つかります。
このアルゴリズムの実行時間は O(lg n) です。これは、 2乗を繰り返すことで Φ 2 iを生成でき、O(lg n) 項しか生成しないためです。これらの値をすべて格納するため、メモリ使用量は O(lg n) です。
O(1) 時間と O(1) 空間で任意の Fib(n) の n を見つけることができます。
固定小数点 CORDIC アルゴリズムを使用して、整数データ型のシフトと加算のみを使用して ln() を計算できます。
x = Fib(n) の場合、n は次のように決定できます。
n = int(2.0801 * ln(x) + 2.1408)
CORDIC ランタイムは、必要な精度レベルによって決まります。2 つの浮動小数点値は、固定小数点値としてエンコードされます。
この提案の唯一の問題は、フィボナッチ数列にない数値の値を返すことですが、元の問題では、関数への入力が Fib(n) になることが具体的に述べられていました。これは、有効なフィボナッチ数のみが使用済み。
フィボナッチ数の式の閉じた形式は次のとおりです。
Fn = Round(φ^n / Sqrt(5))
ここで、φ は黄金比です。
丸め係数を無視すると、これは逆になり、逆関数は次のようになります。
F(-1)n= log(n*Sqrt(5))/logφ
丸め係数を無視したため、計算できる数式にエラーがあります。ただし、間隔 [n*φ - 1/n, n*φ + 1/n] に自然数が含まれる場合、数値 n がフィボナッチ数であると考えると、次のようになります。
数値は、間隔 [n*φ - 1/n, n*φ + 1/n] に自然数が含まれ、フィボナッチ数列におけるその数値のインデックスが log(n*Sqrt(5) を丸めることによって与えられる場合、フィボナッチ数です。 )/logφ
これは、対数や平方根などの計算に使用されるアルゴリズムに応じて、（疑似）一定時間で実行できるはずです。
編集: φ = (1+Sqrt(5))/2
編集：気にしないでください。質問者はコメントで、べき乗は絶対に一定時間ではないことを述べています。
累乗は、定数時間で許可される数学演算の 1 つですか? もしそうなら、閉じた形式の式を介して定数時間で F(n) を計算できます。次に、いくつかの F が与えられると、次のことができます。
F = F(n) の場合、最初の部分は k = O(log(n)) ステップかかります。2 番目の部分は、サイズ O(2^k) の範囲にわたるバイナリ検索であるため、k = O(log(n)) もかかります。したがって、合計すると、O(1) 時間でべき乗がある場合(そしてそれは大きい場合) 、O(1) 空間で O(log(n)) 時間になります。