Home | Wiki | Forum | Featured Image | @GPWiki  
GPWiki.org
GPWiki.org
It is currently Thu Jun 20, 2013 2:09 am

View unanswered posts | View active topics


Board index » Game Programming Discussion » Other Languages

All times are UTC




Post new topic Reply to topic  Page 1 of 1
  [ 7 posts ] 
  Print view Previous topic | Next topic 
Author Message
Gadfly
PostPosted: Tue Aug 11, 2009 7:02 pm 
Level 1 Cleric

Joined: Tue Jul 07, 2009 8:17 pm
Posts: 12
So I just finished writing a program to print the Fibonacci numbers and then find Phi by dividing the last term by the second to last term.

The problem is the Fibonacci numbers increase to huge sizes pretty quickly. I'm using LongInt for my data types, but it just isn't even remotely close to as big as I want. It only prints about 15 Fibonacci numbers before 'resetting' to that big negative number and starting over.

Is there a larger variable data type than a LongInt I could use for huge numbers? If computers can check prime numbers with millions of digits, surely I can squeeze a few more digits out of a data type bigger than LongInt. Thanks.
Top
 Profile  
 
Jasmine
 Post subject:
PostPosted: Tue Aug 11, 2009 7:55 pm 
Corpse Bride
User avatar

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2217
Location: England
If I wanted unlimited integer sizes, I would represent numbers with an array of small integers.

If you imagine each element in the array is to hold one digit of a huge number. That array could be 1 million elements wide, which is representing a number 1 million digits long.

You can then write small algorithms to add numbers like this together. You'd have to consider place value, and carry over.

Three arrays would suffice to build up your fibonacci sequence.

Arrays A and B would both represent 1 initially.

Then add A and B, write to C.
Then add B and C, write to A.
Then add C and A, write to B.

Then add A and B, write to C.
Then add B and C, write to A.
Then add C and A, write to B.
and so on.

_________________
I ain't pushing no moon buttons.
Top
 Profile  
 
Gadfly
 Post subject:
PostPosted: Tue Aug 11, 2009 8:14 pm 
Level 1 Cleric

Joined: Tue Jul 07, 2009 8:17 pm
Posts: 12
Jasmine wrote:
If I wanted unlimited integer sizes, I would represent numbers with an array of small integers.

If you imagine each element in the array is to hold one digit of a huge number. That array could be 1 million elements wide, which is representing a number 1 million digits long.

You can then write small algorithms to add numbers like this together. You'd have to consider place value, and carry over.

Three arrays would suffice to build up your fibonacci sequence.

Arrays A and B would both represent 1 initially.

Then add A and B, write to C.
Then add B and C, write to A.
Then add C and A, write to B.

Then add A and B, write to C.
Then add B and C, write to A.
Then add C and A, write to B.
and so on.

I only took a semester of programming in Pascal for my senior year I high school, and we didn't learn anything about arrays. I'll have to read about it or something, but from what it sounds like you can define this 'array' thing to hold an arbitrary amount of digits. Are arrays what computers use to deal with insanely large numbers?

The last part of your post is exactly how I wrote the code to find the Fibonacci numbers, except A and B are long integers, not these array thing-a-ma-jigs (except I just printed the first two terms for some reason).

Code:
program Fibonacci_Term_Generator;

{$APPTYPE CONSOLE}

{Daniel Young
 08/10/2009
 Fibonacci number generator
}

uses
  SysUtils;

var
i, n: integer;
Phi : real;
Term1, Term2, Term3 : longint;

begin
  writeln('How many Fibonacci terms would you like to print?':65);
  readln(n);
  writeln;
  writeln;
  writeln;

  Term1 := 1;
  Term2 := 1;
  Term3 := 0;
  i := 1;
  write(Term1, ',', ' ', Term2, ',', ' ');
  while (i <> (n + 1)) do
    begin
      Term3 := Term2 + Term1;
      write(Term3, ',', ' ');
      Term1 := Term3 + Term2;
      write(Term1, ',', ' ');
      Term2 := Term1 + Term3;
      write(Term2, ',', ' ');
      i := i + 1;
    end;

  Phi := Term2/Term1;
  writeln;
  writeln;
  writeln('Phi is approximately: ', Phi:0:20);
readln;
end.
Top
 Profile  
 
Jasmine
 Post subject:
PostPosted: Tue Aug 11, 2009 8:23 pm 
Corpse Bride
User avatar

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2217
Location: England
Quote:
I only took a semester of programming in Pascal for my senior year I high school, and we didn't learn anything about arrays. I'll have to read about it or something, but from what it sounds like you can define this 'array' thing to hold an arbitrary amount of digits. Are arrays what computers use to deal with insanely large numbers?

The last part of your post is exactly how I wrote the code to find the Fibonacci numbers, except A and B are long integers, not these array thing-a-ma-jigs (except I just printed the first two terms for some reason).


Arrays are like a collection of similar variables. They can be strings or integers or any data type. These variables all have the same name, but are indexed by numbers, so you'd have A[4] which is the 4th variable of A.

The main use of arrays is when you want to store a list or sequence of data. In our case, we want to store a sequence of digits.



Something like this I think. But I haven't done much Pascal either :)

Code:
var
  A: array[0..255] of Byte;
  B: array[0..255] of Byte;
  C: array[0..255] of Byte;
 
  i, j, carry: Byte;

begin
  A[0] :=1;
  B[0] :=1;

for j := 1 to 10 do
  begin
     carry:=0;
     for i := 0 to 255 do
        begin
          C[i] := A[i] + B[i] + carry;
          carry := int(C[i]/10);
          C[i] := C[i] - carry*10;
        end;

     carry:=0;
     for i := 0 to 255 do
        begin
          A[i] := B[i] + C[i] + carry;
          carry := int(A[i]/10);
          A[i] := A[i] - carry*10;
        end;

     carry:=0;
     for i := 0 to 255 do
        begin
          B[i] := C[i] + A[i] + carry;
          carry := int(B[i]/10);
          B[i] := B[i] - carry*10;
        end;
   end;
end.

_________________
I ain't pushing no moon buttons.
Top
 Profile  
 
Gadfly
 Post subject:
PostPosted: Tue Aug 11, 2009 9:30 pm 
Level 1 Cleric

Joined: Tue Jul 07, 2009 8:17 pm
Posts: 12
Jasmine wrote:
Quote:
I only took a semester of programming in Pascal for my senior year I high school, and we didn't learn anything about arrays. I'll have to read about it or something, but from what it sounds like you can define this 'array' thing to hold an arbitrary amount of digits. Are arrays what computers use to deal with insanely large numbers?

The last part of your post is exactly how I wrote the code to find the Fibonacci numbers, except A and B are long integers, not these array thing-a-ma-jigs (except I just printed the first two terms for some reason).


Arrays are like a collection of similar variables. They can be strings or integers or any data type. These variables all have the same name, but are indexed by numbers, so you'd have A[4] which is the 4th variable of A.

The main use of arrays is when you want to store a list or sequence of data. In our case, we want to store a sequence of digits.



Something like this I think. But I haven't done much Pascal either :)

Code:
var
  A: array[0..255] of Byte;
  B: array[0..255] of Byte;
  C: array[0..255] of Byte;
 
  i, j, carry: Byte;

begin
  A[0] :=1;
  B[0] :=1;

for j := 1 to 10 do
  begin
     carry:=0;
     for i := 0 to 255 do
        begin
          C[i] := A[i] + B[i] + carry;
          carry := int(C[i]/10);
          C[i] := C[i] - carry*10;
        end;

     carry:=0;
     for i := 0 to 255 do
        begin
          A[i] := B[i] + C[i] + carry;
          carry := int(A[i]/10);
          A[i] := A[i] - carry*10;
        end;

     carry:=0;
     for i := 0 to 255 do
        begin
          B[i] := C[i] + A[i] + carry;
          carry := int(B[i]/10);
          B[i] := B[i] - carry*10;
        end;
   end;
end.


Great! Thanks! I'll definitely look into arrays -- they sound handy.
Top
 Profile  
 
Spodi
 Post subject:
PostPosted: Wed Aug 12, 2009 3:49 am 
Dexterous Droid

Joined: Fri Aug 19, 2005 10:34 am
Posts: 3650
A quick Google search brought me to this:

http://sourceforge.net/projects/bigint/

There are quite a lot of libraries, source code, and theory out there for performing math with more bits than can fit into a single variable. With many of them, the only limitation is the amount of memory you can allocate to them.

_________________
NetGore - Open source online RPG engine
Top
 Profile  
 
Gadfly
 Post subject:
PostPosted: Thu Aug 13, 2009 12:29 am 
Level 1 Cleric

Joined: Tue Jul 07, 2009 8:17 pm
Posts: 12
Spodi wrote:
A quick Google search brought me to this:

http://sourceforge.net/projects/bigint/

There are quite a lot of libraries, source code, and theory out there for performing math with more bits than can fit into a single variable. With many of them, the only limitation is the amount of memory you can allocate to them.


That is awesome! I have no friggin' clue how to use that new number type, being a newbie programmer, and all. That would certainly solve my problem. 2 million digits is perfect!
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 7 posts ] 

Board index » Game Programming Discussion » Other Languages

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group