Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
657 views
in Technique[技术] by (71.8m points)

python - 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
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

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]
        head, tail = a[0], a[1:]
        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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...