Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 861

# 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
0
tough_man
2 Solutions

Author Commented:
i'll be so glad for the person who will solve the question and if he/she can send it to my e-mail i'll be so thank for him/her

khaldoon................
0

Commented:
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.
0

Commented:
I forgot, if you want to use the x3 > 0 thing you have to initialize x3 to some positive number.
0

Commented:
and x1 not x2 will be the largest. Sorry!!! =)
0

Commented:
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;
}
0

Commented:
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.
0

Commented:
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) );
}

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.
0

Commented:
There are several ways to do it.

However, the 'largest value that can be represented on your system' is somewhat vague.

on my system:

an int is 32 bit and can store values up to pow(2,31)-1.

I also have 64 bit int and can store values up to pow(2,63)-1.

I can also make bignums, if I used my whole ram for one single number it would be 768 MB - well, some of it would go away for system tasks etc so let's assume that only 512 MB is available to my memory. So storing the value in ram would be pow(2,29) bytes or pow(2,29+3) == pow(2,32) bits so I can store an unsigned value as big as:
pow(2,pow(2,32))-1.

That's a pretty big number, but if I use virtual memory - which is usually the case - I am not limited by my RAM but by the size of my swap space and that swap space is right now 1152MB, let's assume that I can manage to squeeze in 1 GB of memory, but I actually have lots of free space on my hard disk, I can make the swap space bigger and get 4 GB available. Now the process memory can't be 4 GB so let's assume that only 2GB is available to my number, it is still pow(2,31) bytes == pow(2,34) bits and so the biggest number is pow(2,pow(2,34)) - 1.

Is this the 'largest number representable on my system' you are talking about? I am sure you will find a fibonacci number in that upper region close to that number...

Anyway, assuming it is regular plain 'int' values you're talking about it can easily be found as follows:

f(n+2) == f(n+1) + f(n)

now, if you guess that f(n) == A * pow(r1,n) + B*pow(r2,n)

it is actually a fairly good guess. The two constants A and B are independent of each other and can be any value you want so for this to work you must have that the equation f(n+2) == f(n+1) + f(n) must hold for each of the r1 and r2 in the simple equation:

pow(r,n+2) == pow(r,n+1) + pow(r,n);

Dividing both sides by pow(r,n) and you get:

r*r == r + 1

and this gives a quadratic equation and the two solutions are the r1 and r2.

r*r - 2 * 0.5 * r + 0.25 == 1.25
(r - 0.5)*(r-0.5) == 1.25

r == 0.5 +/- sqrt(1.25) == (1 +/- sqrt(5))/2

so r1 == (1 + sqrt(5))/2 and r2 == (1 - sqrt(5))/2

r2 is here close to -0.6 and will go towards 0 as n goes towards infinity, so for large n only r1 is significant.

You also need to find the value of the two constants A and B above, that is found by a simply using the values for small values of n, for example f(0) and f(1).

f(1) == A * r1 + B * r2
f(0) == A + B

This give you two equations for finding A and B and you have the formula complete.

For large n the r2 is not significant and you can just use r1 and so finding an exponent value n such that A * pow(r1,N) == M where M is some big number should give you a value for N. The value N is then found as:

N = floor(log(M/A)/log(r1)).

Using this N in the original formula for f(N) should then give you the highest fibonacci number representative on your computer.

Alf
0

Commented:
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