# How to find the nearest Fibonacci Series number?

Posted on

### Question :

How to find the nearest Fibonacci Series number?

My next step is if the input is not in the Fibonacci Series, the program has to give an output with a number which is in the series that is nearest to the input. I do not know how to proceed, can anyone help me?

``````def fibs():
a,b = 0,1
yield a
yield b
while True:
a,b = b,a+b
yield b

n = int(input("please, enter a number: "))
for fib in fibs():
if n == fib:
print("Yes! Your number is a Fibonacci number!")
break
if fib > n:
print("No! Your number is not a Fibonacci number!")
break
``````

## Why this method works well:

This is a way that does not require previous computation, so is fantastic for performance and such when checking very large numbers.

## The Program:

``````from math import *

n = int(input("Enter a number:"))

if sqrt(5*n**2+4)%1==0 or sqrt(5*n**2-4)%1==0:
print("Your number is a Fibonacci number!")
else:
print("Your number is not a Fibonacci number.")
c = 0
while 1:
c += 1
if sqrt(5*(n+c)**2+4)%1==0 or sqrt(5*(n+c)**2-4)%1==0:
print("%s is the closest Fibonacci number to your entry." % str(n+c))
break
if sqrt(5*(n-c)**2+4)%1==0 or sqrt(5*(n-c)**2-4)%1==0:
print("%s is the closest Fibonacci number to your entry." % str(n-c))
break
``````

## The Explanation:

If (5*n^2 + 4) or (5*n^2 – 4) is a perfect square, then n is a Fibonacci number.

## Program Input/Output

``````Enter a number: 9999999999
Your number is not a Fibonacci number.
9999816735 is the closest Fibonacci number to your entry.

Enter a number: 9999816735
Your number is a Fibonacci number!
``````

Here’s a simple way using your generator that’s ok for testing small numbers.

``````def fibs():
a,b = 0,1
yield a
yield b
while True:
a,b = b,a+b
yield b

def nearest_fib(n):
''' If n is a Fibonacci number return True and n
Otherwise, return False and the nearest Fibonacci number
'''
for fib in fibs():
if fib == n:
return True, n
elif fib < n:
prev = fib
else:
# Is n closest to prev or to fib?
if n - prev < fib - n:
return False, prev
else:
return False, fib

# Test
for i in range(35):
print(i, nearest_fib(i))
``````

output

``````0 (True, 0)
1 (True, 1)
2 (True, 2)
3 (True, 3)
4 (False, 5)
5 (True, 5)
6 (False, 5)
7 (False, 8)
8 (True, 8)
9 (False, 8)
10 (False, 8)
11 (False, 13)
12 (False, 13)
13 (True, 13)
14 (False, 13)
15 (False, 13)
16 (False, 13)
17 (False, 21)
18 (False, 21)
19 (False, 21)
20 (False, 21)
21 (True, 21)
22 (False, 21)
23 (False, 21)
24 (False, 21)
25 (False, 21)
26 (False, 21)
27 (False, 21)
28 (False, 34)
29 (False, 34)
30 (False, 34)
31 (False, 34)
32 (False, 34)
33 (False, 34)
34 (True, 34)
``````

## Update

Here’s a more efficient method which uses Binet’s formula to first approximate y: F(y) = n. It then uses a pair of identities related to the matrix form (which can compute F(n) in O(log(n)) time) to recursively find the nearest Fibonacci numbers to n. The recursion is quite fast because it uses a cache to hold values that have already been computed. Without the cache this algorithm is roughly the same speed as Rockybilly’s.

``````from math import log, sqrt

def fast_fib(n, cache={0: 0, 1: 1}):
if n in cache:
return cache[n]
m = (n + 1) // 2
a, b = fast_fib(m - 1), fast_fib(m)
fib = a * a + b * b if n & 1 else (2 * a + b) * b
cache[n] = fib
return fib

logroot5 = log(5) / 2
logphi = log((1 + 5 ** 0.5) / 2)

def nearest_fib(n):
if n == 0:
return 0
# Approximate by inverting the large term of Binet's formula
y = int((log(n) + logroot5) / logphi)
lo = fast_fib(y)
hi = fast_fib(y + 1)
return lo if n - lo < hi - n else hi

for i in range(35):
print(i, nearest_fib(i))
``````

output

``````0 0
1 1
2 2
3 3
4 5
5 5
6 5
7 8
8 8
9 8
10 8
11 13
12 13
13 13
14 13
15 13
16 13
17 21
18 21
19 21
20 21
21 21
22 21
23 21
24 21
25 21
26 21
27 21
28 34
29 34
30 34
31 34
32 34
33 34
34 34
``````

Note that `fast_fib` uses a default mutable argument for the cache, but that’s ok here because we want the cache to remember its previous contents.

In my speed tests a default mutable argument cache is faster than any other form of cache but it has the downside that it’s impossible to clear the cache from outside of the function, and if you add logic to the function for cache clearing it impacts the performance for the majority of the calls when you don’t want to clear the cache.

Update

It is actually possible to clear a default mutable argument cache from outside the function. We can access a function’s default arguments via its `.__default__` attribute (or `.func_defaults` in old versions of Python 2; `.__default__` works in Python 2.6, but not in 2.5).

Eg,

``````d = fast_fib.__defaults__
d.clear()
d.update({0: 0, 1: 1})
``````

Here is some code (which runs on Python 2 and Python 3) that performs timing tests on some of the algorithms submitted for this question. Rockybilly’s is very similar to my first version except it avoids having to save the previous value. I’ve also made the OP’s `fibs` generator a little more compact.

Douglas’s code is ok for small numbers, or when the argument is, in fact, a Fibonacci number, but it gets very slow for large non-Fibonacci numbers due to the slow one-by-one search. I’ve been able to optimize it a little by avoiding recalculation of various quantities, but that doesn’t make a huge difference to the running speed.

In this version, my `fast_fib()` function uses a global cache so that it can be cleared between tests to make the timings fairer.

``````#!/usr/bin/env python3

""" Find the nearest Fibonacci number to a given integer

Test speeds of various algorithms

See https://stackoverflow.com/questions/40682947/fibonacci-in-python

Written by PM 2Ring 2016.11.19
Incorporating code by Rockybilly and Douglas
"""

from __future__ import print_function, division
from math import log, sqrt
from time import time

def fibs():
a, b = 0, 1
while True:
yield a
a, b = b, a + b

def nearest_fib_Rocky(n):
''' Find the nearest Fibonacci number to n '''
fibgen = fibs()
for fib in fibgen:
if fib == n:
return n
elif fib > n:
next_fib = next(fibgen)
return next_fib - fib if 2 * n < next_fib else fib

def nearest_fib_Doug(n):
a = 5 * n * n
if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0:
return n
c = 1
while True:
m = n + c
a = 5 * m * m
if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0:
return m
m = n - c
a = 5 * m * m
if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0:
return m
c += 1

cache={0: 0, 1: 1}
def fast_fib(n):
if n in cache:
return cache[n]
m = (n + 1) // 2
a, b = fast_fib(m - 1), fast_fib(m)
fib = a * a + b * b if n & 1 else (2 * a + b) * b
cache[n] = fib
return fib

logroot5 = log(5) / 2
logphi = log((1 + 5 ** 0.5) / 2)

def nearest_fib_PM2R(n):
if n == 0:
return 0
# Approximate by inverting the large term of Binet's formula
y = int((log(n) + logroot5) / logphi)
lo = fast_fib(y)
hi = fast_fib(y + 1)
return lo if n - lo < hi - n else hi

funcs = (
nearest_fib_PM2R,
nearest_fib_Rocky,
nearest_fib_Doug,
)

# Verify that all the functions return the same result
def verify(lo, hi):
for n in range(lo, hi):
a = [f(n) for f in funcs]
if not all(head == u for u in tail):
print('Error:', n, a)
return False
else:
print('Ok')
return True

def time_test(lo, hi):
print('lo =', lo, 'hi =', hi)
for f in funcs:
start = time()
for n in range(lo, hi):
f(n)
t = time() - start
print('{0:18}: {1}'.format(f.__name__, t))
print()

verify(0, 1000)
cache={0: 0, 1: 1}
time_test(0, 1000)

funcs = funcs[:-1]
cache={0: 0, 1: 1}
time_test(1000, 50000)
``````

typical output

``````Ok
lo = 0 hi = 1000
nearest_fib_PM2R  : 0.005465507507324219
nearest_fib_Rocky : 0.02432560920715332
nearest_fib_Doug  : 0.45461463928222656

lo = 1000 hi = 50000
nearest_fib_PM2R  : 0.26880311965942383
nearest_fib_Rocky : 1.266334056854248
``````

These times are on an old 2GHz 32 bit machine running Python 3.6 on Linux. Python 2.6 gives similar timings.

FWIW, both Rockybilly’s and my code can easily handle very large numbers. Here’s the timing output of `time_test(10**1000, 10**1000 + 1000)`:

``````nearest_fib_PM2R  : 0.011492252349853516
nearest_fib_Rocky : 7.556792497634888
``````

Keeping the previous fibonacci is not necessary if you don’t mind making an extra generator call.

First store the generator inside a variable.

``````gen = fibs()

n = int(input("please, enter a number: "))
for fib in gen:
if n == fib:
print("Yes! Your number is a Fibonacci number!")
break
if fib > n:
print("No! Your number is not a Fibonacci number!")

next_fib = next(gen)
prev = next_fib - fib
closest = prev if n - prev < fib - n else fib # Search for Python ternary operator
# If you are a stranger to this line of code.
print("The closest fibonacci number to your entry is %s" % closest)

break
``````

Edit: I first used `gen.next()` to get the next value of the yield, however I forgot that in Python 3, it is renamed as usage to `gen.__next__()`. Please take care using it. `next(gen)` is the expected usage for both Python versions.

You could zip `fibs` with itself:

``````n = int(input("please, enter a number: "))
for fib, next_fib in itertools.izip(fibs(), itertools.islice(fibs(), 1, None)):
if n == fib:
print("Yes! Your number is a Fibonacci number!")
break
if next_fib > n:
closest = fib if n - fib < next_fib - n else next_fib
print("The closest Fibonacci number is {}".format(closest))
break
``````

You could use `itertools.tee` to optimize it a bit.