|
%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
|
