Fibonacci: returning a selection of the series

[geremy condra]

On Sun, Aug 29, 2010 at 10:36 AM, Baba <raoulbia at gmail.com> wrote:
> level: beginner
>
> i would like to return a selection of the Fibonacci series.
> example:
> start = 5 ; end  = 55
> the function should then return [5, 8, 13, 21, 34, 55]
>
> it seems that this is best resolved using an iterative approach to
> generate the series. In another post (http://groups.google.ie/group/
> comp.lang.python/browse_thread/thread/aa85ac893fd89c4a/
> d3803a93baf1bdd0#d3803a93baf1bdd0) i looked at the recursive approach
> which seems best to compute the nth number but it seems to me that the
> recursive code is not suited for generating the actual list.
>
> my questios:
> - would you agree that recursive is not ideal for generating a list?
> (in this particular case and in general)
> - can my code below be optimised?
> - how to deal with 'start' and 'end' values that are not in the list
> e.g. 4,76 ?
>
> def i_fib(n):
>    a = 0
>    b = 1
>    list = []
>    counter = 0
>    while counter < n:
>        a, b = b, a+b
>        counter += 1
>        list = list + [b,]
>    return list
>
> def fib_range(start,end):
>    list = i_fib(12)
>    if start in list and end in list:
>        start = list.index(start)
>        end = list.index(end)
>        print list[start:end+1]
>    else: print 'not in list'
>
> fib_range(5,55)
>
> thanks
> Baba

Get the index of the start, use that to generate the second, and
iterate until you hit the end.

from math import sqrt, log, floor

phi = (1 + sqrt(5))/2

def fibonacci_index(n):
    return floor(log(n * sqrt(5))/log(phi) + .5)

def ith_fibonacci(i):
    return floor(phi**i/sqrt(5) + .5)

def next_fibonacci(a, b):
   return a + b

def fibonacci_between(start, stop):
    # find the index of the first
    i = fibonacci_index(start)
    # find the second value given the first
    second_fib = ith_fibonacci(i+1)
    # build the list from there
    fibs = [start, second_fib]
    while fibs[-1] != stop:
        fibs.append(next_fibonacci(fibs[-1], fibs[-2]))
    # and we're done
    return fibs


Now try to understand *why* the above works, rather than just copy-pasting it.

Geremy Condra