Click here to Skip to main content
15,905,563 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
hi,

I need to write a program that computes the nth Fibonacci number using C++. The result (nth Fibonacci number) will be maximum 128bit and I have to use int arrays to solve the problem. I already did the part that computes the nth fibonacci number using arrays. I defined 3 arrays to solve the problem:

C++
// digits of a number are stored in array.
...
unsigned int fib1[100];
unsigned int fib2[100];
unsigned int result[101];
...

result is the summation of fib1 and fib2; for example [2,1] + [3,4] = [5,5] (21+34=55)

But now I need to write another program that computes the nth Fibonacci number recursively. I really don't know how to do that for 128bit numbers. Is there any way to reimplement my code to solve this problem?

Or anyone has another idea?

PS : I am not allowed to use "long double" type or any prepared library like TTmath or GMP.
Posted
Updated 28-Mar-11 14:46pm
v2

If you do an internet search for c++ recursive fibonacci you will find lots of solutions.

Which would have been quicker than asking here!
 
Share this answer
 
Comments
dukenukem18 28-Mar-11 21:09pm    
hi , i already searched for it but most of them use common way (following code block) or "long double" type.

<pre>
int fib(int n)
{
if (n <= 2)
return 1
else
return fib(n-1) + fib(n-2)
}
</pre>

this is not what i'm looking for. i need to reimplement this code for 128bit numbers according to the conditions i already wrote in my question.
Sergey Alexandrovich Kryukov 29-Mar-11 10:40am    
Good advice, Henry, my 5. Probably mine is even more radical... :-)
--SA
Sergey Alexandrovich Kryukov 29-Mar-11 17:03pm    
Henry, please pay attentions for the OP's comment. It was explicitly told the reason of down-vote due to giving NOT CODE. This is more than enough for blacklisting. Such people should be banned.

--SA
It's even faster to write it on your own. Just follow the bare definition and use the loop, no recursion. Oops! You say "recursive". OK then, use recursion.
Any type is fine, it does not really matter for the algorithm.

Instead of wasting time on finding exact implementation, use just first principles: http://en.wikipedia.org/wiki/Fibinochi_numbers[^] (I think you already know that, but take a look).
By the way, take this hint: you don't really need an array, unless you're required to return the array of 0..N Fibonacci numbers, not N-th Fibonacci number as you put it in first place.

If you have the implementation with long double, just change to type the 128-bit integer or any other at your liking: the algorithm should not change.

—SA
 
Share this answer
 
v4
Comments
Аslam Iqbal 29-Mar-11 3:39am    
good link
Sergey Alexandrovich Kryukov 29-Mar-11 10:39am    
Thank you, Aslam.
A good way to get 1 from a lazy homeworkers...
--SA
dukenukem18 29-Mar-11 16:12pm    
lazy homeworker ? i m trying OK ?? i'm not good at programming. i tried some ways to solve that and i already completed most of it. at the end, i just wrote here to take some advice to solve a part of my problem, and i was just looking for an advice NOT code or wikipedia link(!) !
Sergey Alexandrovich Kryukov 29-Mar-11 17:01pm    
Aha, so you admit it was your vote of "1" by saying that?
I meant somebody who voted "1", anonymous person who cannot take any offense by definition, being anonymous.

Now, you're saying it's you. What am I supposed to to? Just to explain you this: You say "I'm not good at programming". It should mean you want to become a good one. There is only one way of becoming a such person: make your hands dirty and do the job. People spend a lot of their free time to give your real help.

You're not happy with NOT code?
It simple means you're not welcome here.

I will blacklist you.
And you're not going to be a developer unless you dramatically change your attitude.

Sorry,
--SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900