Server Help :: View topic - Fibonacci Series into a Really Large Number?

Server Help

Non-Subspace Related Coding - Fibonacci Series into a Really Large Number?

Quan Chi2 - Tue Feb 10, 2009 1:55 pm
Post subject: Fibonacci Series into a Really Large Number?

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 - Tue Feb 10, 2009 2:56 pm
Post subject:

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;
}

Doc Flabby - Tue Feb 10, 2009 4:28 pm
Post subject:

Alternativly write it in haskell

Bak - Tue Feb 10, 2009 5:32 pm
Post subject:

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).

Samapico - Wed Feb 11, 2009 12:10 pm
Post subject:

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 - Fri Feb 13, 2009 1:33 pm
Post subject:

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 - Sat Feb 14, 2009 8:03 am
Post subject:

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 - Sat Feb 14, 2009 3:39 pm
Post subject:

sometimes, those who do not know the wheel exists attempt to reinvent the wheel...

Bak - Sat Feb 14, 2009 5:00 pm
Post subject:

not everyone uses C99

YonatanNaamad - Mon Mar 23, 2009 5:44 pm
Post subject:

Samapico wrote:

Code: Show/Hide

Unless I'm missing something, your optimization just uses recursion as a means of doing a for loop. C is an imperative language... why are you using it as though it's declarative?

In any case, here's another efficient, though ugly, "recursive" implementation.

Code: Show/Hide

long long fib(int a, long long *mem)
{
return (a <= 1) ? (mem[a] = a) : ((mem[a] == -1) ? (mem[a] = fib(a-1,mem) + fib(a-2,mem)) : mem[a]);
}
long long getfib(int x)
{
int i;
long long *memo = malloc(sizeof(long long)*x);
for (i = 0; i < x; i++) memo[i] = -1;
return fib(-1+x,memo);
}

SamHughes - Mon Mar 23, 2009 10:27 pm
Post subject:

Doc Flabby wrote:

Alternativly write it in haskell

Don't mind if I do. Here's a solution that, like Binet's formula, takes ~(log(n)) arithmetic operations, only with exact arithmetic.

Code: Show/Hide

prod (a,b,c) (a',b',c') = (a*a'+b*b', a*b'+b*c', b*b'+c*c')

pow acc m 0 = acc
pow acc m n = pow acc' (prod m m) (div n 2)
where acc' | even n = acc
| otherwise = prod m acc

fib n = let (_,x,_) = pow (1,0,1) (1,1,0) n in x

Yay, I can write trivial functions

Bak - Tue Mar 24, 2009 1:58 am
Post subject:

hey sam what have you been up to these days?

SamHughes - Tue Mar 24, 2009 9:08 pm
Post subject:

Bak wrote:

hey sam what have you been up to these days?

Working in Boston, working on a relationship search engine. You?

YonatanNaamad - Tue Mar 24, 2009 9:43 pm
Post subject:

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 - Tue Mar 24, 2009 11:15 pm
Post subject:

SamHughes wrote:

[..]

Working in Boston, working on a relationship search engine. You?

So next time we get 10 popups from matching websites, we'll know who to blame

Bak - Wed Mar 25, 2009 6:07 am
Post subject:

SamHughes wrote:

You?

Grad school.

SamHughes - Wed Mar 25, 2009 11:52 pm
Post subject:

YonatanNaamad wrote:

It might not be directly applicable to a search engine, but it's somewhat relevant regardless.

Nope, I'm talking about tracking relationships, not creating them.

Bak wrote:

[..]

Grad school.

If you meet anybody named Will Mansky, tell him I said hi.