1

I am working on a program that calculates the Reciprocal Fibonacci Constant (the infinite summation of the Fibonacci numbers.) It calculates every term upto it's error:

I have an program but it only goes to 1474 terms and I need to get to about 10000 terms. It returns an error:

Traceback (most recent call last):
  File "/Users/jaddvirji/Desktop/PapaTechChallenges/Challenge2/Part1/main.py", line 23, in        <module>
curf.write(str(Decimal(fibConstant(x))))
  File "/Users/jaddvirji/Desktop/PapaTechChallenges/Challenge2/Part1/main.py", line 18, in     fibConstant
return (1.0 / fib(n)) + fibConstant(n - 1.0)
File "/Users/jaddvirji/Desktop/PapaTechChallenges/Challenge2/Part1/main.py", line 12, in   fib
return long(((phi**n) - (1-phi)**n) / 5**0.5)

OverflowError: (34, 'Result too large')

And my code is:

#!/usr/bin/env python

print "(C) COPYRIGHT JADD VIRJI 2013. ALL RIGHTS RESERVED."
from decimal import *
import time as t
import sys
sys.setrecursionlimit(10000)

phi = (1+(5**0.5))/2

def fib(n):
   return long(((phi**n) - (1-phi)**n) / 5**0.5)

def fibConstant(n):
  if(n == 1):
      return (1.0 / fib(n))
else:
  return (1.0 / fib(n)) + fibConstant(n - 1.0)

x = 1
while True:
  curf = open(str(x)+" term.txt","w")
  curf.write(str(Decimal(fibConstant(x))))
  curf.close()
  x = x+1
  print Decimal(x)

print "DONE. THANKS FOR USING."

Also, Every result from about 200 terms above is the same (and wrong.)

Does anybody know how to fix these problems?

EDIT: I have a feeling that the problems after ~200 terms are because of floating point errors with the Binet Fibonacci calculation. How do I make these decimals go on forever?

ultimatetechie
  • 328
  • 3
  • 14
  • 1
    In Python you should convert your algorithm from recursive to iterative. – Paulo Scardine Jun 26 '13 at 17:16
  • 3
    see http://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence-in-python for generator-expressions. – Fredrik Pihl Jun 26 '13 at 17:18
  • 1
    Why would you do `while True` when you could do `for x in xrange(1,10001)`? A `while True` loop would go forever - not your only problem, but... – 2rs2ts Jun 26 '13 at 18:14

1 Answers1

1

Try storing the values of fibConstant in a list. Then for each subsequent calculation, you only need to call the last value of the list instead of recalculating. For example:

from math import sqrt

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

def fib(n):
    return (phi**n - (1-phi)**n) / sqrt(5)

fib_constant_list = [1./fib(1)]
def fib_constant(n):
    new_fib_c = (1./fib(n) + fib_constant_list[-1])
    fib_constant_list.append(new_fib_c)
    return new_fib_c

n = 2
N_MAX = 1000
while n < N_MAX:
     print fib_constant(n)
wflynny
  • 17,180
  • 5
  • 41
  • 60