Date: Wed, 15 Oct 1997 08:51:12 -0400
From: Alex Bogomolny
Dear Ben:
Let's think. Consider this implementation (C?)
int Fib(int n)
{
switch (n)
{
case 0:
return 1;
case 1:
return 1;
default:
return Fib(n-1) + Fib(n-2);
}
return -1; // error
}
Denote as Nib(n) the number of times Fib is to be called to compute Fib(n). To me it seems that Nib(n) = Nib(n-1) + Nib(n-2) + 1 with two initial conditions Nib(0) = 1 and Nib(1) = 1. This means that
Therefore, Nab(n) = Nib(n)+1 is a Fibonacci sequence with initial conditions Nab(0) = Nab(1) = 2. From here, Nab(n) = 2Fib(n). Finally, Nib(n) = 2Fib(n) - 1.
What do you think? Computing a number takes almost twice its magnitude. But, probably, it's worth it.
Best regards,
Alexander Bogomolny
73227843