Subject: Re: Computing Fibonacci sequence
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

(Nib(n)+1) = (Nib(n-1)+1) + (Nib(n-2)+1).

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

|Reply| |Up| |Exchange index| |Contents| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 61149997

Search by google: