tough_man
asked on
How to write nonrecursive function that calculates the nth fibonacci number and determine the largest fibonacci
i need to write a program that calculates the nth fibonacci number and determine the largest fibonacci number that can be printed on your system
You can do (pseudo)
int i; long x1 = 0, x2 = 1, x3;
for(i = 2; i < max; ++i) {
x3 = x1 + x2;
x1 = x2;
x2 = x3;
}
To simply calculate the n Fibonacci you choose max. of course the first and second numbers are 0 and 1 (the initial values of x1 and x2 respectively).
To calculate the largest F number there're a trick that I use, but I don't know if it would be portable. Replace i < max with x3 > 0. Since x3 is a signed number, if it exceeds the maximum integer the system allows it will start to turn negative. You want to catch x3 right when it turns negative, then x2 would be the largest possible F number. There are "BigInt" classes supported by some systems, but I don't know for sure.
int i; long x1 = 0, x2 = 1, x3;
for(i = 2; i < max; ++i) {
x3 = x1 + x2;
x1 = x2;
x2 = x3;
}
To simply calculate the n Fibonacci you choose max. of course the first and second numbers are 0 and 1 (the initial values of x1 and x2 respectively).
To calculate the largest F number there're a trick that I use, but I don't know if it would be portable. Replace i < max with x3 > 0. Since x3 is a signed number, if it exceeds the maximum integer the system allows it will start to turn negative. You want to catch x3 right when it turns negative, then x2 would be the largest possible F number. There are "BigInt" classes supported by some systems, but I don't know for sure.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
and x1 not x2 will be the largest. Sorry!!! =)
for what language?
-Scheme
(define fib
(lambda (n)
(if (<= n 1)
1
(+ (fib (- n 1)) (fib (- n 2))))))
-C++
inf fib(int n)
{
int curr = 1;
int prev = 1;
while (n > 1)
{
curr += prev;
prev = curr - prev;
n--;
}
return curr;
}
-Scheme
(define fib
(lambda (n)
(if (<= n 1)
1
(+ (fib (- n 1)) (fib (- n 2))))))
-C++
inf fib(int n)
{
int curr = 1;
int prev = 1;
while (n > 1)
{
curr += prev;
prev = curr - prev;
n--;
}
return curr;
}
im not sure about your question on printing the largest fib on a system though .. it depends on the computer's bits of available memory and the allocation of integers.
This uses only a mathematical formula. For very big numbers this will be faster than the other approach. You probably want to define PHI and sqrt(5) as constants elsewhere.
int fib(int x) {
const double PHI = 0.5 + sqrt(1.25);
return int( pow(PHI, x) / sqrt(5) );
}
More info:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html
I don't understand your question about largest fib number on a system. __int64 is the biggest integer type (at least in MSVC, I'm not sure if it's a standard), so you could replace int with __int64 in the function, if that's what you mean.
int fib(int x) {
const double PHI = 0.5 + sqrt(1.25);
return int( pow(PHI, x) / sqrt(5) );
}
More info:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html
I don't understand your question about largest fib number on a system. __int64 is the biggest integer type (at least in MSVC, I'm not sure if it's a standard), so you could replace int with __int64 in the function, if that's what you mean.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:
Split points between n_fortynine & Salte
Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
Tinchos
EE Cleanup Volunteer
I will leave a recommendation in the Cleanup topic area that this question is:
Split points between n_fortynine & Salte
Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
Tinchos
EE Cleanup Volunteer
ASKER
khaldoon................