Fibonacci Sequence and Long numbers.

[Hans Kristian Ruud]

Huaiyu Zhu wrote:

> On Thu, 05 Oct 2000 15:35:43 -0700, Neil Macneale <macneale at cats.ucsc.edu>
> wrote:
> >
> >>>> cache = []
> >>>> cache.insert(0, 0L)
> >>>> cache.insert(1, 1L)
> >>>> def fib(i):
> >...    if len(cache) > i:
> >...       return cache[i]
> >...    cache.insert(i, fib(i-1) + fib(i-2))
> >...    return cache[i]
> >...
> >
> >All seems good and well to this point.  But when I try:
> >
> >>>> fib(1000)
> >
> >I get a whole bunch of recursive erros which tell me there is an Integer
> >addition error.
>
> Are you seeing RuntimeError: Maximum recursion depth exceeded?
>
> If so, this is because fib is calling fib recursively.  When you call fib(n)
> there are n-len(cache) open function calls before they are fulfilled one by
> one.  On my Linux, fib(len(cache)+997) works, but fib(len(cache)+998) fails.
>

An alternative solution would be to use the following properties of Fibonacchi
numbers:

with F(1) = 1, F(2) = 1, F(3) = 2, ...
we have:

F(2n+1) = F(n)*F(n) + F(n+1)*F(n+1)
F(2n) = F(n-1)*F(n) + F(n)*F(n+1)

This will reduce the recursion depth from N to O( log_2(N) )

>>> cache = {}
>>> cache[0] = 0L
>>> cache[1] = 1L
>>> cache[2] = 1L
>>> def fib(i):
 if cache.has_key(i):
  return cache[i]
 else:
  if i%2:
   f1 = fib( (i-1)/2 )
   f2 = fib( (i+1)/2 )
   return f1*f1+f2*f2
  else:
   f0 = fib(i/2-1)
   f1 = fib(i/2)
   f2 = fib(i/2+1)
   return f0*f1+f1*f2

>>> fib(5)
5L
>>> fib(12)
144L
>>> fib(24)
46368L
>>> fib(10000)
33644764876431783266621612005107543310302148460680063906564769974680081442166662

36815559551363373402558206533268083615937373479048386526826304089246305643188735

45443695598274916066020998841839338646527313000888302692356736131351175792974378

54413752130520504347701602264758318906527890855154366159582987279682987510631200

57542878345321551510387081829896979161312785626503319548714021428753269818796204

69360978799003509623022910263681314931952756302278376284415403605844025721143349

61180023091208287046088923962328835461505776583271252546093591128203925285393434

62090424524892940390170623388899108584106518317336043747073790855263176432573399

37128719375877468974799263058370657428301616374089691784263786242128352581128205

16370298089332099905707920064367426202389783111470054074998459250360633560933883

83192338678305613643535189213327973290813373264265263398976392272340788292817795

35805709936910491754708089318410561463223382174656373212482263830921032977016480

54726243842374862411453093812206564914032751086643394517512161526545361333111314

04243685480510676584349352383695965342807176877532834823434555736671973139274627

36291082106792807847180353291311767789246590899386354593278945237776744061922403

37638674004021330343297496902028328145933418826817683893072003634795623117103101

29195316979460763273758925353077255237594378843450406771555577905645044301664011

94625809722167297586150269684431469520346149322911059706762432685159928347098912

84706740862008587135016260312071903172086094081298321581077282076353186624611278

24553720853236530577595643007251774431505153960090516860322034916322264088524885

24331580515348496224348482993809050704834824493274537326245677558790891871908036

62058009594743150052402532709746995318770724376825907419939632265984147498193609

28522394503970716544315642132815768890805878318340491743455627052022356484649519

61124602683139709750693826487066132645076650746115126775227486215986425307112984

41182622661057163515069260029861704945425047491378115154139941550671256271197133

252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875L

>>>

;-)

> Huaiyu

--
Hans Kristian