2

Oddly enough, my code is giving me the 4781st number, when I know it is the 4782nd Fibonacci Number (I was comparing with a friend). I don't want to submit until my code can do it though.

Here's my code:

import sys
FibNums = []
a=1
b=2
c=3
FibNums.append(a)
FibNums.append(b)
FibNums.append(c)
for i in range(1, sys.maxsize):
    a = b
    b = c
    c = a + b
    FibNums.append(c)
    if len(str(c)) == 1000:
         break
 print (len(FibNums))

Can anyone help me find the error? I checked and my list doesn't skip anything (it does actually contain 1 as the 1st index). Thanks!

  • 1
    That `for` loop should just be a `while True`. – user2357112 Aug 09 '13 at 00:14
  • 1
    You start with 1, 2, 3? Normally the sequence starts with 0, 1, 1, or 1, 1, 2. – Waleed Khan Aug 09 '13 at 00:14
  • also sequence starts: 1,1,2 ... – Mitch Wheat Aug 09 '13 at 00:14
  • Wow, I'm an idiot for not catching that mistake. Thanks. –  Aug 09 '13 at 00:16
  • You might try a more concise `a, b = b, a + b` and avoid `c` altogether. – Waleed Khan Aug 09 '13 at 00:17
  • @user2357112 For vs. while is a matter of preference here. See http://stackoverflow.com/questions/920645/when-to-use-while-or-the-for-in-python. Although `xrange()` might be used to try to marginally improve performance. – agconti Aug 09 '13 at 00:21
  • 2
    @agconti: No, this is supposed to keep going until a `break`, and it doesn't use the value of the loop variable. `while True` is the standard form, clearer than a `for` loop, and it doesn't break if the loop needs to run for longer than `sys.maxsize` iterations. – user2357112 Aug 09 '13 at 00:24
  • @agconti In cases like this `xrange` is more than just a marginal performance improvement. OP must be using python 3 (in which case `range` is like python 2's `xrange`) or, less likely, have an insane amount of RAM: `range(1, sys.maxsize)` allocates an array of 2^63 pointers, which takes up 2^66 bytes = 64 exabytes. – Danica Aug 09 '13 at 00:34
  • @Dougal Thanks I learned a lot from your post. I wasn't sure how much of a performance boost it would be so I wanted to be conservative in my suggestion. – agconti Aug 09 '13 at 01:19
  • @user2357112 Thanks for your comment; I'm not familiar with the standard form for solving this problem. For this case, why would it need to run longer than `sys.maxsize`? – agconti Aug 09 '13 at 01:21
  • @agconti: It wouldn't. However, if you get in the habit of using a `for` loop, you'll get crashes when you write something that does end up running longer than `sys.maxsize`, and you'll waste a bit of performance needlessly. It's better to build good habits early. – user2357112 Aug 09 '13 at 01:31
  • 1
    In this case, you could actually use `while len(str(c)) < 1000` and skip the `if len(str(c)) == 1000: break`, or take a base-10 logarithm of `c` to avoid the overhead of building a string. – user2357112 Aug 09 '13 at 01:36
  • @user2357112 Or just check `c < 10**999`, which will probably be faster still. – Danica Aug 09 '13 at 14:27

1 Answers1

9

The first two Fibonacci numbers are 1 and 1, not 1 and 2.

Tavian Barnes
  • 12,477
  • 4
  • 45
  • 118