Rate this:
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:

// 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 28-Mar-11 14:36pm
Edited 28-Mar-11 14:46pm
Henry Minute223.5K
v2

Rate this:

## Solution 1

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

Which would have been quicker than asking here!
dukenukem18 at 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.
SAKryukov at 29-Mar-11 10:40am

Good advice, Henry, my 5. Probably mine is even more radical... :-)
--SA
SAKryukov at 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
Rate this:

## Solution 2

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
v4
Аslam Iqbal at 29-Mar-11 3:39am

SAKryukov at 29-Mar-11 10:39am

Thank you, Aslam.
A good way to get 1 from a lazy homeworkers...
--SA
dukenukem18 at 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(!) !
SAKryukov at 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)

 0 OriginalGriff 205 1 Sergey Alexandrovich Kryukov 200 2 Rob Philpott 100 3 Prakriti Goyal 97 4 jlopez788 94
 0 OriginalGriff 6,837 1 Sergey Alexandrovich Kryukov 5,589 2 Maciej Los 3,479 3 Peter Leow 3,323 4 DamithSL 2,505

Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 28 Mar 2011