How To Find The Nearest Fibonacci Series Number?

November 10, 2024 Post a Comment

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

Solution 1:

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

deffibs():
    a,b = 0,1yield a
    yield b
    whileTrue:
        a,b = b,a+b
        yield b

defnearest_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:
            returnTrue, n
        elif fib < n:
            prev = fib
        else:
            # Is n closest to prev or to fib?if n - prev < fib - n:
                returnFalse, prev
            else:
                returnFalse, fib

# Testfor i inrange(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

deffast_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 & 1else (2 * a + b) * b
    cache[n] = fib
    return fib

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

defnearest_fib(n):
    if n == 0:
        return0# 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 inrange(35):
    print(i, nearest_fib(i))

output

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__[0]
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

deffibs():
    a, b = 0, 1whileTrue:
        yield a
        a, b = b, a + b

defnearest_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 if2 * n < next_fib else fib

defnearest_fib_Doug(n):
    a = 5 * n * n
    if sqrt(a + 4)%1 == 0or sqrt(a - 4)%1 == 0:
        return n
    c = 1whileTrue:
        m = n + c
        a = 5 * m * m
        if sqrt(a + 4)%1 == 0or sqrt(a - 4)%1 == 0:
            return m
        m = n - c
        a = 5 * m * m
        if sqrt(a + 4)%1 == 0or sqrt(a - 4)%1 == 0:
            return m
        c += 1

cache={0: 0, 1: 1}
deffast_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 & 1else (2 * a + b) * b
    cache[n] = fib
    return fib

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

defnearest_fib_PM2R(n):
    if n == 0:
        return0# 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 resultdefverify(lo, hi):
    for n inrange(lo, hi):
        a = [f(n) for f in funcs]
        head, tail = a[0], a[1:]
        ifnotall(head == u for u in tail):
            print('Error:', n, a)
            returnFalseelse:
        print('Ok')
        returnTruedeftime_test(lo, hi):
    print('lo =', lo, 'hi =', hi)
    for f in funcs:
        start = time()
        for n inrange(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

Oklo=0hi=1000nearest_fib_PM2R  :0.005465507507324219nearest_fib_Rocky :0.02432560920715332nearest_fib_Doug  :0.45461463928222656lo=1000 hi=50000nearest_fib_PM2R  :0.26880311965942383nearest_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.011492252349853516nearest_fib_Rocky :7.556792497634888

Solution 2:

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!")
        breakif 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.

Solution 3:

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:"))

ifsqrt(5*n**2+4)%1==0orsqrt(5*n**2-4)%1==0:
    print("Your number is a Fibonacci number!")
else:
    print("Your number is not a Fibonacci number.")
    c = 0while1:
        c += 1ifsqrt(5*(n+c)**2+4)%1==0orsqrt(5*(n+c)**2-4)%1==0:
            print("%s is the closest Fibonacci number to your entry." % str(n+c))
            breakifsqrt(5*(n-c)**2+4)%1==0orsqrt(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: 9999999999Yournumber is not a Fibonaccinumber.
9999816735 is the closest Fibonaccinumber to your entry.


Enter a number: 9999816735Yournumber is a Fibonaccinumber!

Solution 4:

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!")
        breakif 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.

Python Developer