On the Linear Time Algorithm For Finding Fibonacci Numbers

You're viewing a comment by Shlomi Fish and its responses.

July 07, 2009, 12:25

Hi all!

Just a note about the Python code:

def LinearFibonacci(n):
  fn = f1 = f2 = 1
  for x in xrange(2, n):
    fn = f1 + f2
    f2, f1 = f1, fn
  return fn

fn is not needed here, and if one opts to use it anyway, need not be initialised before the loop. Furthermore, the variable names "f1" and "f2" are confusing here, because I expect f2 to be bigger than f1. I would write this code as:

def LinearFibonacci(n):
  curr, next = 1, 1
  for x in xrange(2, n):
    next, curr = ((next+curr),next)
  return next

Tested and works.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.