Pages

Fibonacci Generator

Write a function that generates Fibonacci numbers up to a given value.
Use it to get the highest Fibonacci number less than 1000, and to check if there is in that range a Fibonacci number that is multiple of 12.

You can solve this problem in a myriad of ways. However, the original idea was to push towards writing a Python generator. I extracted this example from Dive into Python 3, paragraph 6.6.1.

Here is a possible implementation:
def fibonacci(top):
    a, b = 0, 1
    while a < top:
        yield a
        a, b = b, a + b
Having a 'yield' statement in its body, we see that this fibonacci function is a generator. That is, a sort of function that behaves like an iterator. Each time we call it, it should yield a value. If not, as in this case when a is not less than top, the generator is consumed, and the iteration stops.

Let's see it in action:
def test_list_1000(self):
    fib1000 = list(fibonacci(1000))  # 1
    self.assertEqual(17, len(fib1000))
    self.assertEqual(987, fib1000[-1])

def test_multiple_12(self):
    for candidate in fibonacci(1000):  # 2
        if candidate and candidate % 12 == 0:  # 3
            break
    else:
        self.fail('No fibonacci multiple of 12 found!')
    self.assertEqual(144, candidate)
1. Here fibonacci(1000) is used to populate a list of seventeen elements, when the generated value is not less than 1000, the generation of elements ends.
2. Each time we call fibonacci(1000) a new Fibonacci number is generated, starting from 0 on.
3. Since 144 is both a Fibonacci number and a multiple of 12, we won't consume completely the generator.

Full code pushed to GitHub.

No comments:

Post a Comment