?
Solved

How to write nonrecursive function that calculates the nth fibonacci number and determine  the largest fibonacci

Posted on 2003-03-29
10
Medium Priority
?
819 Views
Last Modified: 2008-03-06
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
Comment
Question by:tough_man
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
10 Comments
 

Author Comment

by:tough_man
ID: 8233176
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8233203
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
 
LVL 4

Accepted Solution

by:
n_fortynine earned 100 total points
ID: 8233218
I forgot, if you want to use the x3 > 0 thing you have to initialize x3 to some positive number.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 4

Expert Comment

by:n_fortynine
ID: 8233220
and x1 not x2 will be the largest. Sorry!!! =)
0
 

Expert Comment

by:alphaeternity
ID: 8233305
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
 

Expert Comment

by:alphaeternity
ID: 8233309
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
 

Expert Comment

by:Eighty
ID: 8233415
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.
0
 
LVL 12

Assisted Solution

by:Salte
Salte earned 100 total points
ID: 8233940
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
 
LVL 9

Expert Comment

by:tinchos
ID: 9551795
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
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses
Course of the Month13 days, 22 hours left to enroll

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question