Not Yet Answered # Compute to find Fib- 43

ddanbe 2,467 David W 119 Schol-R-LEA 1,003 ddanbe 2,467 rubberman 1,109 Schol-R-LEA 1,003 Discussion Starter DS9596 Schol-R-LEA 1,003 Discussion Starter DS9596 Discussion Starter DS9596 Schol-R-LEA 1,003 Hi I'm having a problem implementing a mini shopping cart drop down in the header to show the user all the products they have in their shopping cart. It seems the only solution for this is Ajax, and I've looked all over and can't find anything that I could possibly ...

3

What have you done, besides posting your homework assignment?Show your code to us and pinpoint the errors you have.We will be more than happy to help.

0

Can you start the non-recusive function ... show what you can do ... so we can see what you are missing ... hopefully ... not everything :)

0

I will also warn you that while the conventional tree-recursive algorithm is much simpler than the iterative algorithm, it is extremely inefficient, being of order *O(Fib(n))* in time and *O(n)* in space. This is because (for example) for fib(5), you have to compute fib(4) and fib(3), which in turn have to compute fib(3) + fib(2), which in turn have to compute fib(2) + fib(1) and fib(1) + fib(0), **and then** compute fib(2) and fib(1), and so on. The total number of calls to fib() is equal to the fibonacci number of n.

It would take quite a while to compute fib(43) that way, even in C++ - unless you use a trick.

The trick is called *memoization*, and basically means keeping a record of the computed values so that when you come to a value you have already calculated before, you can just look it up in a table rather than re-computed again. I won't go into the details of it, just that it is easiest to use a `vector<int>`

to do it so that you don't have to worry about the size of the table. You don't need to worry about it, but it is something to at least be aware of.

There is an even faster way to compute fibonacci numbers using matrices, but I'll just tantalize you with that fact for now and leave it to you to learn it on your own (hint: Wikipedia covers it quite nicely).

0

@Schol-R-LEA

I even have another way, it is a snippet here in C# but is easily translated in C++. :)

*Edited 1 Year Ago by ddanbe*: ommission

0

Fib(43) is a VERY big number, and will overflow even double precision numbers. Not sure about 64bit integers, but definitely 32bit ones.

As for the recursive vs. non-recursive algorithms, show your work!

FWIW, I was using recursive fib algorithms back in the mid-1980's to balance S&P indexed funds for the Mellon Bank.

1

**rubberman**: I thought so too, but then I checked using Python (which has bigints), and it turns out that's not the case. Fibonacci numbers do grow quite rapidly, but not quite *that* rapidly; fib(43) is around 400 million, which will fit a 32-bit signed value.

```
memo = dict()
memo[0] = 0
memo[1] = 1
def fib(n):
global memo
if n in memo.keys():
return memo[n]
else:
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
fib(43)
print(memo)
```

I think we were both thinking of factorials, which *do* grow that quickly - fact(43) is around 6 x 10^52.

```
def fact(n):
if n <= 1:
return 1
else:
return n * fact(n - 1)
print(fact(43))
```

(And yes, I know I've given the game away, but the OP would need to be able to re-write the Python code into C++, and if they could do that they wouldn't be posting such a basic question in the first place.)

*Edited 1 Year Ago by Schol-R-LEA*

0

Not right, but something like this?

```
long Fib(int n)
{ int f1=1, f2=2, fn;
for (i=43; i<=n; ++i)
{ fn=f1+f2;
f2=fn;
f1=f2;
}
return fn;
}
```

0

Well, it's a start I guess, but in this case, the 43 should be what you are passing to the function as `n`

, not hard-coded into the function; it should look like this in your call:

```
value = fib(43);
```

The initial value of `i`

should probably be 0, since you are counting *up* to the value of `n`

.

```
long Fib(int n)
{
long f1=1, f2=1, fn;
for (i=0; i<=n; ++i)
{
fn=f1+f2;
f2=fn;
f1=f2;
}
return fn;
}
```

(I won't offer advice on whether the algorithm is correct overall, just this one piece of the puzzle.)

0

Instead of that would something like this work?

I found some stuff from the book that it might be like this not sure:

```
#include <iostream>
using namespace std;
int fib(int);
int main()
{
for(int i=0; i<43; ++i)
cout << fib(i) << " ";
cout << endl;
system("pause");
return 0;
}
int fib(int n)
{ if (n<=0)
return 0;
else if (n==1)
return 1;
else
return fib(nul)+fib(n-2); //recursive case
}
```

0

```
#include <iostream>
using namespace std;
int fib(int);
int main()
{
for(int i=0; i<43; ++i)
cout << fib(i) << " ";
cout << endl;
system("pause");
return 0;
}
int fib(int n)
{ if (n<=0)
return 0; // base case
else if (n==1)
return 1; //base case
else
return fib(n-1)+fib(n-2); //recursive case
}
```

0

That should be correct for the recursive version, yes, though you'll want some patience when it runs: you are producing the whole series of `fib(0)`

to `fib(43)`

, one at a time, which means that you'll be recomputing the series, uhm... pardon me if I'm not quite awake enough right now to work it all out but it will be a lot of recomputing. If all you need is `fib(43)`

, this particular code is overkill, but if you mean to print the whole series in that range, you are good to go.

Oops, I just noticed something: you need to test in the loop to be `i <= 43`

in order to get 43 inclusive.

You may want to fiddle about with memoizing the results, though, just to see about how much of a speedup you'll get from it. A `std::vector<int>`

variable should be useful for this purpose.

BTW, are you using Bloodshed Dev-C++ as your IDE by any chance? I noticed the `system("pause");`

line which is why I ask, that particular problem is specific to the old version of Dev-C++ and some early versions of Visual Studio. If you are, you should be aware that this version of Dev-C++ hasn't been updated in ten years, and has been superceded by the Orwell Dev-C++ fork, which is in current development, has an up-to-date version of GCC bundled with it, and AFAICT doesn't have that specific problem. Alternately, you can try Code::Blocks which is a similar IDE to Dev-C++ and also avoids that problem.

*Edited 1 Year Ago by Schol-R-LEA*

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hello All ...

Iam Getting An Error With try to excecute the stored procedure .

I have Have Sql database , the stored procedure like so :

```
USE [MPRS]
GO
/****** Object: StoredProcedure [dbo].[Search_Licenses_By_Number] Script Date: 26-Nov-16 8:06:52 AM ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
ALTER PROCEDURE ...
```

Help! I want to create a java program that finds the highest even integer among the values entered by the user. Stop asking values when a value less than 1 have been entered. If no even integer is entered, display "No Even Integer"

Here is the sample output that I ...