login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of function evaluations when recursively calculating Fibonacci(n) with caching.
2

%I #49 Mar 11 2020 01:57:42

%S 1,1,1,3,6,5,9,8,11,10,14,13,16,13,19,15,18,15,22,18,21,18,24,20,23,

%T 20,27,23,26,23,29,22,25,22,32,26,29,26,32,25,28,25,34,28,31,28,34,27,

%U 30,27,37,31,34,31,37,30,33,30,39,33,36,33,39

%N Number of function evaluations when recursively calculating Fibonacci(n) with caching.

%C One way to calculate the Fibonacci numbers recursively is to use:

%C F(0) = 0, F(1) = 1, F(2) = 1,

%C F(n) = F((n + 1)/2)^2 + F((n - 1)/2)^2 for odd n,

%C F(n) = F(n/2) * (F(n/2 - 1) + F(n/2 + 1)) for even n.

%C Proof: It is known that F(i) * F(j) + F(i + 1) * F(j + 1) = F(i + j + 1) (see formula section of A000045).

%C For even n, let i = n/2 and j = n/2 - 1, for odd n, let i = j = (n + 1)/2.

%C This table gives the number of evaluations of F for calculating F(n). It is assumed that values of F which have been previously calculated are available; looking up a previously calculated value counts as a function evaluation.

%C a(0) = 1, a(1) = 1, a(2) = 1,

%C if (a(n)) has not been previously calculated then

%C a(n) = a((n + 1)/2) + a((n - 1)/2) + 1, n odd,

%C a(n) = a(n/2) + a(n/2 - 1) + a(n/2 + 1) + 1, n even,

%C else

%C a(n) = 1.

%C Conjecture: a(n) is O(log n).

%H Thomas König, <a href="/A331164/b331164.txt">Table of n, a(n) for n = 0..10000</a>

%H Thomas König, <a href="/A331164/a331164.f90.txt">Calculation of Fibonacci numbers</a>, Fortran program including operation counts.

%H Thomas König, <a href="/A331164/a331164.png">Graph for calculating F(10) with different ordering of the calls.</a>

%e Calculation of F(15) = 15:

%e Level of recursion is marked with indentation and "level", so calculating F(15) (level 1) calls F(8) (level 2), which calls F(5) (level 3) etc... until a cached value is reached.

%e F(15) level 1

%e F(8) level 2

%e F(5) level 3

%e F(3) level 4

%e F(2) level 5 cached

%e F(1) level 5 cached

%e F(2) level 4 cached

%e F(4) level 3

%e F(3) level 4 cached

%e F(2) level 4 cached

%e F(1) level 4 cached

%e F(3) level 3 cached

%e F(7) level 2

%e F(4) level 3 cached

%e F(3) level 3 cached

%o (Fortran) program main

%o implicit none

%o integer, parameter :: pmax = 100000

%o integer :: r, n

%o logical, dimension(0:pmax) :: cache

%o do n=0, pmax

%o cache (0:2) = .true.

%o cache (3:pmax) = .false.

%o r = a(n)

%o write (*,fmt="(I0,', ')", advance="no") r

%o end do

%o write (*,fmt="()")

%o contains

%o recursive function a (n) result(r)

%o integer, intent(in) :: n

%o integer :: r

%o if (cache(n)) then

%o r = 1

%o return

%o else if (mod(n,2) == 1) then

%o r = a ((n+1)/2) + a ((n-1)/2) + 1

%o else

%o r = a(n/2+1) + a (n/2) + a(n/2-1) + 1

%o end if

%o cache (n) = .true.

%o end function a

%o end program main

%Y Cf. A000045; see A331124 for the number of evaluations without caching.

%K nonn,easy,hear

%O 0,4

%A _Thomas König_, Jan 11 2020