Fibonacci: returning a selection of the series

[Baba]

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

 

[Alain Ketterlin]

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] [...]
my questios:
- would you agree that recursive is not ideal for generating a list?
(in this particular case and in general)

I would not, in the general case. Well-known problems like fact or fib
have been scrutinized in so much detail that I find it hard to conclude
anything by looking at them. And problems producing lists are usually
"easy" to transform from one version to the other.

However in the general case, to me, the recursive version is usually
much easier to understand, and the iterative version is just an
optimization to save space. There are recursive algorithms that I would
have trouble to write in an iterative way (unless I use an explicit
stack, but that doesn't really count).

We'll stay with the iterative version here, because you've started with
that and you're not far from the solution. But when you're done, try to
think about a recursive version. When the goal is to produce a list, the
recursion scheme is almost immediate: produce one element per call, one
after the other.

- can my code below be optimised?

Sure. What's this 12 there? Why traversing the list three times (index()
needs to traverse at least some part of it)? And...

- how to deal with 'start' and 'end' values that are not in the list
e.g. 4,76 ?

In general, if you have a program that produces something just to
remove/ignore it five lines later, you have a problem. In your case:

1) are you sure you need to append to list(*) at every iteration? When
do you *really* need to? And...

2) your loop runs up to n (the index of the fib number), but you want to
stop on some fib number value (not index).

So, why not pass start and end to i_fib, and use them where appropriate?

-- Alain.

(*) Don't use "list" as a name, because it's a (useful) built-in
function. Use more expressive names: fn instead of b, fn_1 instead of a,
fibnumbers instead of list, etc.

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'

 

[News123]

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?

Of course, This is probably the whole point of this exercise.

Just because something can be defined recursively doesn't mean, that it
should be
calculated recursively

- 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

lateron you should probably use a generator function for i_fib(n)
Then you will only calculate what is needed.

minor suggestion for above code.
Instead of:
list = list + [b,]
it is common practice to write
list.append(b)

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)

you know, that the list returned by i_fib() is sorted.
Knowing this you can look at the python module bisect.
It allows you to identify the index of the closest entry in a list.

Just read it up in the net:
http://docs.python.org/library/bisect.html



You could do this of course also do manually
(perhaps better for learning python than just using exsitng funtions)

Search for the first Fibonacci number which is bigger than your start number
Then search for the first Fibonacci number, which is bigger than your
end number

Display all numbers between these two indices

 

[geremy condra]

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

 

[Arnaud Delobelle]

my questios:
- would you agree that recursive is not ideal for generating a list?
(in this particular case and in general)

In Python that is probably correct in the vast majority of cases for two
reasons:

* lists in Python are implemented as arrays;
* there is no tail call optimisation in Python.

But not necessarily in other languages. In Lisp for example, recursion
is *the* natural way of generating lists.

 

[Steven D'Aprano]

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]

Start with something to lazily generate Fibonacci numbers. It doesn't
matter whether this is iterative or recursive, but it must be *lazy* --
only generating each number when you ask for the next one. Generators are
ideal for this:

# Untested.
def fib():
"""Generate the Fibonacci numbers."""
a, b = 1, 1
yield a
while 1:
yield b
a, b = b, a+b


Then pass it into a filter than skips numbers less than start,
accumulates numbers until you exceed end, and stop. Then return the
numbers that you collected.

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.

In this specific case, you can get recursion to be much, much more
efficient than the naive f(n) = f(n-1) + f(n-2) case, but iteration in
Python is often more efficient.

my questios:
- would you agree that recursive is not ideal for generating a list? (in
this particular case and in general)

In this particular case, an iterative approach to Fibonacci will probably
be more effective.

In general, no, recursion is fine for generating lists.

 

[Baba]

In general, if you have a program that produces something just to
remove/ignore it five lines later, you have a problem. In your case:

1) are you sure you need to append to list(*) at every iteration? When
do you *really* need to? And...

2) your loop runs up to n (the index of the fib number), but you want to
stop on some fib number value (not index).

So, why not pass start and end to i_fib, and use them where appropriate?

Hi Alain

Thank you for your (pragmatic) suggestions! Based on your input i was
able to considerably optimise my approach:


def fib_range(start, end):
fib_1 = 0
fib_2 = 1
range = []
while fib_2 < end:
fib_1, fib_2 = fib_2, fib_1 + fib_2
if fib_2 >= start and fib_2 <= end:
range.append(fib_2)
return range

print fib_range(4,76)

Thanks
Baba