Author 
Message 
Quan Chi2 Member of "Sexy Teenagers that Code" Group
Age:30 Gender: Joined: Mar 25 2005 Posts: 860 Location: NYC Offline

Posted: 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] 

Back to top 


Samapico No, these DO NOT look like penises, ok?
Age:34 Gender: Joined: May 08 2003 Posts: 1252 Location: Montreal, Canada Offline

Posted: 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:
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...
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;
}

_________________ DCME codeveloper
17th Parallel Head Sysop
Subspace: The Future 

Back to top 


Doc Flabby Server Help Squatter
Joined: Feb 26 2006 Posts: 636 Offline

Posted: Tue Feb 10, 2009 4:28 pm Post subject: 




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

Back to top 


Bak ?ls s 0 in
Age:21 Gender: Joined: Jun 11 2004 Posts: 1826 Location: USA Offline

Posted: 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). _________________ SubSpace Discretion: A Third Generation SubSpace Client 

Back to top 


Samapico No, these DO NOT look like penises, ok?
Age:34 Gender: Joined: May 08 2003 Posts: 1252 Location: Montreal, Canada Offline

Posted: 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. 

Back to top 


Bak ?ls s 0 in
Age:21 Gender: Joined: Jun 11 2004 Posts: 1826 Location: USA Offline


Back to top 


Doc Flabby Server Help Squatter
Joined: Feb 26 2006 Posts: 636 Offline

Posted: 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. 

Back to top 


Cheese Wow Cheese is so helpful!
Joined: Mar 18 2007 Posts: 1017 Offline

Posted: Sat Feb 14, 2009 3:39 pm Post subject: 




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

Back to top 


Bak ?ls s 0 in
Age:21 Gender: Joined: Jun 11 2004 Posts: 1826 Location: USA Offline

Posted: Sat Feb 14, 2009 5:00 pm Post subject: 




not everyone uses C99 

Back to top 


YonatanNaamad Newbie
Joined: Mar 22 2009 Posts: 5 Location: Troy Offline

Posted: Mon Mar 23, 2009 5:44 pm Post subject: 




Samapico wrote: 
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));
}


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.
long long fib(int a, long long *mem)
{
return (a <= 1) ? (mem[a] = a) : ((mem[a] == 1) ? (mem[a] = fib(a1,mem) + fib(a2,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);
}



Back to top 


SamHughes Server Help Squatter
Joined: Jun 30 2004 Posts: 249 Location: Greenwich Offline

Posted: 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.
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 

Back to top 


Bak ?ls s 0 in
Age:21 Gender: Joined: Jun 11 2004 Posts: 1826 Location: USA Offline

Posted: Tue Mar 24, 2009 1:58 am Post subject: 




hey sam what have you been up to these days? 

Back to top 


SamHughes Server Help Squatter
Joined: Jun 30 2004 Posts: 249 Location: Greenwich Offline

Posted: 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? 

Back to top 


YonatanNaamad Newbie
Joined: Mar 22 2009 Posts: 5 Location: Troy Offline

Posted: 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. 

Back to top 


Samapico No, these DO NOT look like penises, ok?
Age:34 Gender: Joined: May 08 2003 Posts: 1252 Location: Montreal, Canada Offline

Posted: 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 

Back to top 


Bak ?ls s 0 in
Age:21 Gender: Joined: Jun 11 2004 Posts: 1826 Location: USA Offline

Posted: Wed Mar 25, 2009 6:07 am Post subject: 




Grad school. 

Back to top 


SamHughes Server Help Squatter
Joined: Jun 30 2004 Posts: 249 Location: Greenwich Offline

Posted: 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. 

Back to top 


