역 피보나치 알고리즘?

역 피보나치 알고리즘?

---

임의의 n에 대해 F (n)을 계산하는 방법에는 수십 가지가 있으며, 그중 많은 방법이 런타임 및 메모리 사용량이 높습니다.

그러나 반대 질문을하고 싶다고 가정 해 보겠습니다.

n> 2에 대해 F (n)이 주어지면 n은 무엇입니까?

(F (1) = F (2) = 1이고 명확한 역이 없기 때문에 n> 2 제한이 있습니다).

이 문제를 해결하는 가장 효율적인 방법은 무엇입니까? 피보나치 수를 열거하고 목표 수에 도달했을 때 멈추는 방식으로 선형 시간으로이 작업을 수행하는 것은 쉽지만 그보다 더 빠르게 수행 할 수있는 방법이 있습니까?

편집 : 현재 여기에 게시 된 최상의 솔루션은 수학적 연산이 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)두 개의 연속적인 피보나치 수를 저장하는 vector를 고려하십시오 . 이 행렬을 곱 (8*1 + 5*1, 8*1 + 5*0) = (13, 8)하면 다음 피보나치 수를 얻을 수 있습니다.
일반화하면 A^n * (1, 0) = (f(n), f(n - 1)).

실제 알고리즘은 두 단계를 거칩니다.

1. 계산 A^2, A^4, A^8, 등 우리가 수를 원하는 패스까지.
2. 의 n계산 된 거듭 제곱을 사용하여 로 이진 검색 을 수행 A합니다.

참고로 양식의 모든 시퀀스 f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t)는 이와 같이 표시 될 수 있습니다.

---

Wikipedia 는 결과를 다음과 같이 제공합니다.

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

여기서 Phi는 황금 비율입니다.

---

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)

시퀀스 대신 시퀀스 A^(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 개 단어 로 양방향 반복기를 만들 수 있습니다 . 나머지는 Zeckendorf 표현을 찾기 위해이 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)이 주어진 피보나치 수와 어떻게 비교되는지에 따라 샘플 공간을 두 개로 분할합니다.

편집 : @rcollyer의 솔루션은 내 것이 O (lg n)이고 그가 찾은 것은 O (1) = 일정한 시간이기 때문에 더 빠릅니다.

---

그래서 저는이 문제에 대해 생각하고 있었고 O (lg n) 메모리 사용으로 O (lg n) 시간에 이것을 할 수 있다고 생각합니다. 이것은

F (N) = (1 / √5) (Φ ^N - φ ^N )

여기서 Φ = (1 + √5) / 2 및 φ = 1-Φ.

첫 번째 관찰은 n> 1에 대해 φ ⁿ <1입니다. 이것은 모든 n> 2에 대해

F (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 + ... + 21 b ₁ + 2 0 b ₀} / √5 ⌋

또는 더 읽기 쉽게

F (n) = ⌊ Φ ^{2 k-1 b _k-1} Φ ^{2 k-2 b _k-2} ... Φ ^{2 1 b ₁} Φ ^{2 0 b ₀} / √5 ⌋

이것은 다음 알고리즘을 제안합니다. 먼저 숫자 F (n)보다 큰 ⌊ Φ ^z / √5 ⌋이 되는 숫자 Φ ^z 를 계산할 때까지 모든 ^k에 대해 Φ ^{2 k} 계산을 시작 합니다. 이제 거기에서 이렇게 생성 한 Φ의 모든 힘을 거꾸로 반복합니다. 현재 숫자가 표시된 Φ의 거듭 제곱보다 크면 Φ의 거듭 제곱으로 나누고이 값으로 나눈 값을 기록합니다. 이 프로세스는 기본적으로 한 번에 가능한 가장 큰 2의 거듭 제곱을 빼서 한 번에 한 비트의 n을 복구합니다. 결과적으로 일단 완료되면 n을 찾을 수 있습니다.

이 알고리즘의 실행 시간은 O (lg n)입니다. 반복 된 제곱으로 Φ ^{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 런타임은 원하는 정밀도 수준에 따라 결정됩니다. 두 부동 소수점 값은 고정 소수점 값으로 인코딩됩니다.

이 제안의 유일한 문제는 피보나치 수열에없는 수에 대한 값을 반환한다는 것입니다. 그러나 원래 문제는 함수에 대한 입력이 Fib (n)이 될 것이라고 구체적으로 명시했습니다. 이는 유효한 피보나치 수만 다음과 같음을 의미합니다. 익숙한.

---

EDIT: Never mind. The asker has stated in comments that exponentiation is definitely not constant time.

---

Is exponentiation one of the mathematical operations that you'll allow in constant time? If so, we can compute F(n) in constant time via the closed-form formula. Then, given some F, we can do the following:

1. Compute F(1), F(2), F(4), F(16), F(256), ... until F(2^k) <= F < F(2^{k+1})
2. Do a binary search for i between 2^k and 2^{k+1} until F(i) <= F < F(i+1)

If F = F(n), then first part takes k = O(log(n)) steps. The second part is a binary search over a range of size O(2^k), so it also takes k = O(log(n)). So, in total, we have O(log(n)) time in O(1) space if (and it's a big if) we have exponentiation in O(1) time.

---

A closed form of the Fibonacci number formula is:

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

---

이것은 user635541의 답변과 유사 할 수 있습니다. 나는 그의 접근 방식을 완전히 이해하지 못합니다.

다른 답변에서 언급 피보나치 수의 행렬 표현을 사용하여, 우리는에서 갈 수있는 방법을 얻을 수 F_n와 F_m로 F_{n+m}와 F_{n-m}(만 플러스, 곱하기, 빼기와 나누기 사용하여, 일정 시간을 ! 실제로하지를 업데이트 참조 ). 우리는 또한 0 (단위 행렬)을 가지고 있으므로 수학적 그룹입니다!

일반적으로 이진 검색을 수행 할 때 평균을 구하기위한 나누기 연산자도 필요합니다. 또는 적어도 2로 나누십시오. 그러나 우리 F_{2n}가 F_n그것 으로 가고 싶다면 제곱근이 필요합니다. 운 좋게도 플러스와 마이너스는 로그 시간 '거의'이진 검색에 필요한 모든 것입니다!

Wikipedia는 아이러니하게도 Fibonacci_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

Here test is some boolean function; a and b are consecutive fibonacci numbers f_k and f_{k-1} such that the difference between out upper bound hi and lower bound lo is always f_k. We need both a and b so we can increase and decrease the implicit variable k efficiently.

Alright, so how do we use this to solve the problem? I found it useful to create a wrapper around our Fibonacci representation, that hides the matrix details. In practice (is there such a thing for a Fibonacci searcher?) you would want to inline everything manually. That would spare you the redundancy in the matrices and make some optimization around the matrix inversion.

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]

However the code does work, so we can test it as follows. Notice how little different the search function is from when our objects were integers and not Fibonaccis.

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

The remaining open question is whether there is an efficient search algorithm for monoids. That is one that doesn't need a minus / additive inverse. My guess is no: that without minus you need the extra memory of Nikita Rybak.

Update

I just realized that we don't need division at all. The determinant of the F_n matrix is just (-1)^n, so we can actually do everything without division. In the below I removed all the matrix code, but I kept the Fib class, just because everything got so extremely messy otherwise.

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

이 모든 것이 매력처럼 작동합니다. 내 유일한 걱정은 비트 복잡성이 계산을 지배한다는 것입니다. 우리가 방금 순차 검색을 수행했을 수도 있습니다. 또는 실제로 자릿수를 보는 것만으로도 당신이보고있는 것을 거의 알 수 있습니다. 그래도 재미가 없습니다.

참고 URL : https://stackoverflow.com/questions/5162780/an-inverse-fibonacci-algorithm