Calculating previous number in Fibonacci Sequence

Question

Given a Fibonacci number, n, how can I calculate the previous number in the Fibonacci Sequence?

Answer 1

Divide by phi ((1 + sqrt(5)) / 2) and round to nearest integer.

This works because the Nth Fibonacci number is

Fn = (Phi ^ n - Psi ^ n) / (Phi - Psi)

where Psi = -1 / Phi. By rearranging the formula and massaging it a bit, you will get that the difference between F_n+1 / Phi and F_n is less than Psi ^ n, and since | Psi | < 1, rounding to the nearest integer will yield the correct result.

Answer 2

Given a Fibonacci number , find the next Fibonacci number

Every 3 consecutive Fibonacci numbers a, b, c satisfies a+b = c and a*c = b² ± 1 where the sign alternates between + and -.

Substituting the first equation into the second gives a*(a+b) = b² ± 1.

Solving for a gives a = (-b ± √(5b² ± 4)) / 2.

Since we know that a is positive, this must become a = (-b + √(5b² ± 4)) / 2.

It then remains to check which of 5b² ± 4 is a perfect square.

Pseudocode:

prevFibonacci(n):
  m = 5*n*n - 4
  x = round(sqrt(m))

  if m != x*x:
    m = 5*n*n + 4
    x = round(sqrt(m))

  return (x - n) / 2

Answer 3

Fibinacci number can be found using matrix exponentiation:

    n
1 1     =   F_n+1   F_n
1 0         F_n     F_n-1

By applying binary search on to find n, you can find the index of the desired fibonacci number n, and from the matrix extract F_n-1

Note that this method is stable with regards to floating points precision (it only uses integers), and the run time is O(logn), where n is the index of the given fibonacci number.

Answer 4

This is a simple to understand, yet potentially inefficient approach to solving the problem. Basically, you can calculate every fibonacci number up to your number, store them in an array, and once you hit n or in this case fibNum, just return the number at index before n.

  var prevFibonacci = function(fibNum) {
    var fibNums = [0,1]; // array to hold fibonacci numbers
    var i = 1;

    while (fibNums[i] !== fibNum) {
      var nextFib = fibNums[i] + fibNums[i-1];
      fibNums.push(nextFib);
      i++;
    }

    return fibNums[i-1];
  };