Exercise 11 (Chapter 5) - Is this the way to go?

[pantera]

/*

Write a program that writes out the first so many values of the
Fibonacci series. Find the largest Fibonacci number that fits in an
int.

*/

// Exercise 11 - Chapter 5

#include "std_lib_facilities.h"
#include <limits.h>

int Fibonacci (int n)
{
if (n==1||n==2) {
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}

int main()
{
int n;
cout << "Enter how many values of the Fibonacci series you wish to
print out: \n";
cin >> n;
cout << "The first " << n << " values of the Fibonacci series is:
\n";
// print the first n values of the Fibonacci series
for (int i=1; i<=n; ++i)
cout << Fibonacci(i) << endl;

// find the largest Fibonacci number that fits in an int
int k = 1;
int count_Fib = 0;
while (Fibonacci(k)<INT_MAX) {
++count_Fib;
++k;
}

cout << "k = " << k << endl;
cout << "count_Fib = " << count_Fib << endl;
cout << Fibonacci(k) << endl;
cout << "The largest Fibonacci number for an int is " << Fibonacci
(count_Fib) << endl;
}

[Edico]

pantera, how do you reached so quickly ex.11 from Chapter 5?
Do you read the Chapter 5?
Where do you handle errors in your solution?

This is my solution:

#include "std_lib_facilities.h"

int main()
try
{
unsigned int v1 = 0;
unsigned int v2 = 1;
unsigned int v3 = 0;
unsigned int i = 0;
unsigned int n = 0;
unsigned int largest = 0;

cout << "This program writes out the first n Fibonacci numbers.
\n";
cout << "Please enter a value for n:\n";
cin >> n;
if (n < 0)
error("n must be a positive number");
cout << "The first " << n << " Fibonacci numbers ";
if (n == 1) cout << "is ";
else cout << "are: ";
for (i = 0; i < n; ++i) {
v3 = v1 + v2;
cout << v1 << ' ';
v1 = v2;
v2 = v3;
}
cout << endl;
v1 = 0;
v2 = 1;
v3 = 0;
cout << "The largest Fibonacci number that fits in an int is ";
largest = pow(2, 31); // the largest unsigned int is 2^32 - 1
while (v3 < narrow_cast<unsigned int>(largest)) {
v3 = v1 + v2;
if (v3 > narrow_cast<unsigned int>(largest) && v3 > 0)
cout << v3 << endl;
v1 = v2;
v2 = v3;
}
cout << endl;
return 0;

}

catch (runtime_error& e) {
cerr << "error: " << e.what() << endl;
return 1;

[Art Werschulz]

Hi.

On Dec 25, 2009, at 5:07 AM, Edico wrote:

> largest = pow(2, 31); // the largest unsigned int is 2^32 - 1

Two problems here: The standard library's pow() function expects its
first argument to be a floating point type
largest = (largest - 1) + largest;

The good news is that you code is correct. Moreover, it avoids the
exponential cost associated with the naive implementation of the
recursive formula for Fibonacci numbers. IOW, whereas the naive
implementation has cost O(phi^n), where phi = (1 + sqrt(5))/2, this
algorithm has cost O(n). (The big-O notation means "order of
magnitude"; the cost of using these two algorithms to compute the n-th
Fibonacci number grows no faster than exponetially or linearly in n.)
The reason for this slowness is that the naive recursive version
involves a great deal of recalculation. For fun, draw a call tree for
Fibonacci(5), and you'll see what I mean.

However, the code is pretty nonintuitive. I would help the reader out
by using better variable names, not to mention some comments.
Moreover, you can still make use of a function to compute Fibonacci
numbers; since they grow exponentially, you won't take too big a
performance hit for using same. The small performance hit is becasue
the computation of successive Fibonacci numbers will still involve
some recalculation, so that computing the first n will take time
O(n^2), whereas your code takes time O(n) for the same task.

BTW, if you want an even faster algorithm for computing the n-th
Fibonacci number, you can use matrix multiplication (see the Wikipedia
article for details), along with the fact that one can calculate the
matrix power A^n in time O(log n) by repeated squaring. For example,
A^8=((A^2)^2)^2. This means that you can compute the n-th Fibonacci
number in time O(log n). You could also use the expicit formula for
the n-th Fibonacci number along with fast powering (e.g.,
x^8=((x^2)^2)^2) for any real number x), but that involves non-integer
arithmetic, which is somewhat unnatural for an integer-based problem
(and can also lead to roundoff errors).

Art Werschulz (8-{)} "Metaphors be with you." -- bumper sticker
GCS/M (GAT): d? -p+ c++ l u+(-) e--- m* s n+ h f g+ w+ t++ r- y?
Internet: agw STRUDEL comcast.net

[Edico]

Agree, with the floating point for pow, a function to compute
fibonacci,
the comments and I agree that my code is pretty nonintuitive.
I just made a copy-paste from the exercise written some time ago.
At that time I was still writing nonintuitive and ugly code.
Maybe you will write the code for your pedantry and share it to us
so that we can learn something.

[pantera]

Thank you, Edico. When I read your codes, I saw "narrow_cast" which
I'd never seen before. By that time, I'd read Ch.5, but perhaps I was
reading the chapter a bit fast and carelessly. I've re-read the
chapter, but it's a lot more clear to me now. It's really difficult to
go fast on subjects like programming/maths and still have something
solid in the memory. The skills are cumulative, and can be acquired
only by lots of practice, and today's skills depend a lot on
yesterday's ones.