Server Help

[Quan Chi2]

I understand that there is Binet's formula for calculating the n^th fibonacci number.

Here's the deal:

So I'm using recursion for the fibonacci program I'm writing. The problem I have is that when the program reaches the 45..46 number, it stops functioning correctly and the number generated is negative. I understand that it's because normal datatypes (standard types) are not able to handle such calculations with high numbers.

I've tried using long long and double long while declaring my fibonacci function. It didn't work.

How do I go about working around this problem? [/b]

[Samapico]

negative results? ... use unsigned types maybe

I happen to have a code example for that using recursive functions as well in a class presentation:

Code: Show/Hide unsigned int FibonacciRec(unsigned int N) { if (N==0)    return 0; else if (N==1)    return 1; else    return FibonacciRec(N - 1) + FibonacciRec(N - 2); }

But that gives you a crapload of function calls... Maybe it can even overflow your stack and give you weird stuff, if that's what you used.

That's the suggested optimization they give us...

Code: Show/Hide unsigned int FRO(unsigned int N, unsigned int Previous, unsigned int Current) { if (N <= 1) { return Current; } else { return FRO(N ? 1, Current, Current + Previous); } } unsigned int FibonacciRecOptimized(unsigned int N) { return (N == 0) ? (N) : (FRO(N, 0, 1)); } unsigned int FibonacciIter(unsigned int N) { unsigned int R1 = 0, R2 = 1, R = 0, i; for (i = 1; i <= N; i++) { R = R1 + R2; R2 = R1; R1 = R; } return R; }

_________________
(Insert a bunch of dead links here)

[Doc Flabby]

Alternativly write it in haskell
_________________
Rediscover online gaming. Get Subspace | STF The future...prehaps

[Bak]

int will go up to ~2 billion(2^31) before going negative
unsigned int will get to ~4 billion(2^32). If you want arbitrary precision math you have to use a library(for java you can use the BigInteger class).

However, samp is probably right in that you just have a stack overflow because each recursive call causes two more calls (so exponential function calling).
_________________
SubSpace Discretion: A Third Generation SubSpace Client

[Samapico]

Yeah... you get 2 * Fib(N+1) - 2 recursive function calls...


But your problem is surely because you're not using unsigned values...
F47 = 2 971 215 073

Anything over 2147483647 doesn't fit in a 32bit signed int.
Though, even with an unsigned value, you'll get an overflow at 48 or 49 (result will loop back to 0).
So yeah, you'll need to get 64 or 128 bits ints.

[Bak]

try long long int

do

Code: Show/Hide printf("num bytes = %i\n",sizeof(long long int));

to see if it's a 4 byte (32 bit) or 8 byte (64 bit) value.

[Doc Flabby]

Acctually its far easier to use Stdint.h if you want fixed size intergers

It contains definitions for all the different lengths of intergers. I'm surprised so many people still try to do this manually.

http://en.wikipedia.org/wiki/Stdint.h

You could probably find some code/libary that simulates an unlimited size interger.

[Cheese]

sometimes, those who do not know the wheel exists attempt to reinvent the wheel...
_________________
SSC Distension Owner
SSCU Trench Wars Developer

[Bak]

not everyone uses C99

[YonatanNaamad]

[SamHughes]

[Bak]

hey sam what have you been up to these days?

[SamHughes]

[YonatanNaamad]

Relationships you say? May I interest you in the stable marriage problem*? It might not be directly applicable to a search engine, but it's somewhat relevant regardless.

*Although it would not surprise me if you've seen this.

[Samapico]

[Bak]

[SamHughes]