Server Help Forum Index Server Help
Community forums for Subgame, ASSS, and bots
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   StatisticsStatistics   RegisterRegister 
 ProfileProfile   Login to check your private messagesLogin to check your private messages   LoginLogin (SSL) 

Server Help | ASSS Wiki (0) | Shanky.com
Fibonacci Series into a Really Large Number?

 
Post new topic   Reply to topic Printable version
 View previous topic  Mathmatical Number Game Problem Post :: Post C coding challenge  View next topic  
Author Message
Quan Chi2
Member of "Sexy Teenagers that Code" Group
Member of


Age:27
Gender:Gender:Male
Joined: Mar 25 2005
Posts: 860
Location: NYC
Offline

PostPosted: Tue Feb 10, 2009 1:55 pm    Post subject: Fibonacci Series into a Really Large Number? Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List Send email Visit posters website AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Age:31
Gender:Gender:Male
Joined: May 08 2003
Posts: 1252
Location: Montreal, Canada
Offline

PostPosted: Tue Feb 10, 2009 2:56 pm    Post subject: Reply to topic Reply with quote

negative results? ... use unsigned types maybe tongue.gif

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

_________________
DCME co-developer
17th Parallel Head Sysop
Subspace: The Future
Back to top
View users profile Send private message Add User to Ignore List
Doc Flabby
Server Help Squatter


Joined: Feb 26 2006
Posts: 636
Offline

PostPosted: Tue Feb 10, 2009 4:28 pm    Post subject: Reply to topic Reply with quote

Alternativly write it in haskell tongue.gif
_________________
Rediscover online gaming. Get Subspace | STF The future...prehaps
Back to top
View users profile Send private message Add User to Ignore List
Bak
?ls -s
0 in


Age:18
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Tue Feb 10, 2009 5:32 pm    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List AIM Address
Samapico
No, these DO NOT look like penises, ok?


Age:31
Gender:Gender:Male
Joined: May 08 2003
Posts: 1252
Location: Montreal, Canada
Offline

PostPosted: Wed Feb 11, 2009 12:10 pm    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Bak
?ls -s
0 in


Age:18
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Fri Feb 13, 2009 1:33 pm    Post subject: Reply to topic Reply with quote

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.
Back to top
View users profile Send private message Add User to Ignore List AIM Address
Doc Flabby
Server Help Squatter


Joined: Feb 26 2006
Posts: 636
Offline

PostPosted: Sat Feb 14, 2009 8:03 am    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Cheese
Wow Cheese is so helpful!


Joined: Mar 18 2007
Posts: 1011
Offline

PostPosted: Sat Feb 14, 2009 3:39 pm    Post subject: Reply to topic Reply with quote

sometimes, those who do not know the wheel exists attempt to reinvent the wheel...
_________________
SSC Distension Owner
SSCU Trench Wars Developer
Back to top
View users profile Send private message Add User to Ignore List Visit posters website AIM Address
Bak
?ls -s
0 in


Age:18
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Sat Feb 14, 2009 5:00 pm    Post subject: Reply to topic Reply with quote

not everyone uses C99
Back to top
View users profile Send private message Add User to Ignore List AIM Address
YonatanNaamad
Newbie


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

PostPosted: Mon Mar 23, 2009 5:44 pm    Post subject: Reply to topic Reply with quote

Samapico wrote:

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


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);
}
Back to top
View users profile Send private message Add User to Ignore List
SamHughes
Server Help Squatter


Joined: Jun 30 2004
Posts: 248
Location: Greenwich
Offline

PostPosted: Mon Mar 23, 2009 10:27 pm    Post subject: Reply to topic Reply with quote

Doc Flabby wrote:
Alternativly write it in haskell tongue.gif


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 icon_rolleyes.gif
Back to top
View users profile Send private message Add User to Ignore List
Bak
?ls -s
0 in


Age:18
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Tue Mar 24, 2009 1:58 am    Post subject: Reply to topic Reply with quote

hey sam what have you been up to these days?
Back to top
View users profile Send private message Add User to Ignore List AIM Address
SamHughes
Server Help Squatter


Joined: Jun 30 2004
Posts: 248
Location: Greenwich
Offline

PostPosted: Tue Mar 24, 2009 9:08 pm    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
YonatanNaamad
Newbie


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

PostPosted: Tue Mar 24, 2009 9:43 pm    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Samapico
No, these DO NOT look like penises, ok?


Age:31
Gender:Gender:Male
Joined: May 08 2003
Posts: 1252
Location: Montreal, Canada
Offline

PostPosted: Tue Mar 24, 2009 11:15 pm    Post subject: Reply to topic Reply with quote

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 tongue.gif
Back to top
View users profile Send private message Add User to Ignore List
Bak
?ls -s
0 in


Age:18
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Wed Mar 25, 2009 6:07 am    Post subject: Reply to topic Reply with quote

SamHughes wrote:
You?
Grad school.
Back to top
View users profile Send private message Add User to Ignore List AIM Address
SamHughes
Server Help Squatter


Joined: Jun 30 2004
Posts: 248
Location: Greenwich
Offline

PostPosted: Wed Mar 25, 2009 11:52 pm    Post subject: Reply to topic Reply with quote

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. icon_smile.gif

Bak wrote:
[..]

Grad school.


If you meet anybody named Will Mansky, tell him I said hi.
Back to top
View users profile Send private message Add User to Ignore List
Display posts from previous:   
Post new topic   Reply to topic    Server Help Forum Index -> Non-Subspace Related Coding All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum
View online users | View Statistics | View Ignored List


Software by php BB © php BB Group
Server Load: 53 page(s) served in previous 5 minutes.

phpBB Created this page in 0.083927 seconds : 42 queries executed (39.3%): GZIP compression disabled