unbounded integer class

what math operators does it need to support?

If you''re using linux, trying looking at the man pages for BigInt (I believe it''s called).

If you wanted to make your own, just think of how you could use, say, a character array to do the job:

"100", "758", etc, ended by a null symbol. You could increase data use by using, say, unsigned ints, and a number system based on base 2^32-1, using 0xFFFFFFFF for the terminator.

(If you''re working with smaller numbers, a char based terminating thing would be more efficient).

You mau also want to store them in a reversed format to make math operators easier to preform:

given: var = "768" + "426"

"7680" -> 0,8,6,7,END
"426" -> 6,2,4,END
var -> ???

To add:

   +1 +1
0 8 6 7 END
6 2 4 END
------------
6 0 1 8 END

which would read:
8106 (which is the result of 7680 and 426). I''ll cook up an example real quick for addition...

Any math operators would be nice, but they arent really the point of the class. They could easily be written in. What im mainly looking for is a general idea of how to store the int in a class.

This example uses base 10 to easily transform into strings and back.

#include <iostream>
#include <string>
#include <list>
using namespace std;

class BigInt;
void Add ( BigInt &op1 , BigInt &op2 , BigInt &result );

class BigInt
{
private:
  friend void Add ( BigInt &op1 , BigInt &op2 , BigInt &result );
  list< unsigned char > data; //Storing data NOT in reverse, using list properties to determine end of data.

public:
  string GetString( void )
  {
    string temp;
    list< unsigned char >::iterator c = data.begin();
    while ( c != data.end() )
    {
      temp += ((*c)+'0'); //Adding ascii 0 to convert to ascii.

      ++c;
    }
	 return temp;
  }
  void Set( string to )
  {
    data.clear(); //<-- pretty sure this is wrong!!! What is right stl for this again?

    char *c = (char *)to.c_str();
    while (*c)
    {
      data.push_back( (*c) - '0' ); //subtract ascii 0...

      ++c;
    }
  }
  void Set( unsigned int to )
  {
    //lazy example:

    data.clear(); //<-- again, wrong???

    //This should be much better optimized I think:

    while ( to )
    {
      data.push_back( to % 10 );
      to /= 10;
    }
  }
};

//Note: using references 'cause I'm too lazy to set it up with copy constructors

void Add ( BigInt &op1 , BigInt &op2 , BigInt &result )
{
  result.data.clear(); //<-- Wrong???

  //Setup:

  list< unsigned char >::reverse_iterator op1ri = op1.data.rbegin();
  list< unsigned char >::reverse_iterator op2ri = op2.data.rbegin();
  bool op1reading = true;
  bool op2reading = true;
  bool carrybit = false;

  while ( op1reading || op2reading || carrybit )
  {
    unsigned int current_col = 0;
    //Add up current collumn:

    //Are we carrying?

    if (carrybit) current_col++;
    //Are we reading from 'operator one'?

    if (op1reading)
    {
      //If so, add from the current column of operator one...

      current_col += (*op1ri);
      //Increment the current column...

      ++op1ri;
      //And disable reading from it if we've reached the end.

      if (op1ri == op1.data.rend()) op1reading = false;
    }
    if (op2reading)
    {
      //As per operator one (only with operator two).

      current_col += (*op2ri);
      ++op2ri;
      if (op2ri == op2.data.rend()) op2reading = false;
    }
    //Do we need to carry?

    if (current_col >= 10)
    {
      //Then set our carry bit...

      carrybit = true;
      //And bring us down to a single column.

      current_col -= 10;
    }
    else
    {
      //We don't need to carry...make sure this is cleared.

      carrybit = false;
    }
    //Now we add "this column" to our result:

    result.data.push_front( (unsigned char)current_col );
    //Note: pushing front because we're using reverse iterators.

    //That is, we're starting from the back and working our way

    //to the front. (back/front being in terms of reading).

  }
}

int main( int argc , char **argv )
{
  BigInt pilike, fnord, result;
  pilike.Set("314159265359");
  fnord.Set("12345678909876543211234567890987654321");
  cout << "Pilike: " << pilike.GetString() << endl;
  cout << "Fnord:  " << fnord.GetString() << endl;
  Add( pilike , fnord , result );
  cout << "Result: " << result.GetString() << endl;
  return 0;
}

Appologizes for bugs. I'll go try and compile this and debug it and then edit the post to get it to work.

And no, I'm not going to overload operators for you . (I have work soon :/).

[edited by - MaulingMonkey on July 18, 2003 7:06:56 PM]

EDIT: Code now works/compiles/seems to run okay

[edited by - MaulingMonkey on July 18, 2003 7:15:40 PM]

If you're just concerned with storage, here's a few ways that I might do it:

Method one:
Store base100 numbers in unsigned chars.

This allows quick coversion to/from ascii (2 characters per number).

Method two:
Store base256 (or other 2^(8*n) number...).
This allows more space to be used with less overhead.

I'd be inclined to use vectors or the like instead of lists. I just used lists because that's what I'm familliar with.

If you use a stl container, you don't need to worry about an 'ending' character, which is nice. You'll probably want to use vectors instead of lists, for less overhead.

Plus, if using containers (or an equivilant by hand), it's easy to find the 'end' of the data array, making the order of storage a moot point (except for ease of remembering).

For addition, you'd iterate through it starting at the one's column, then the 100's/256's/whatever's column, increasing in power, and keeping track of carrying.

My example didn't use the sign bit at all...
For Addition/Subtraction, simply swap it around so you're working with the same sign...aka:

given (+x) - (-y) convert to: (+x) + (+y) //simple
given (+x) - (+y):
if (x >= y): simple
if (y > x): convert to: -((+y)-(+x))
given (+x) + (-y) convert to: (+x) - (+y) //and complete as above
given (+x) + (+y): //leave as is...simple!

Multiplication/Division is harder, but the sign bit is a moot point... as it's so simple (if one and only one of the two numbers is negative, then so is the result. Otherwise, the result is positive).

Just think back to good ole' first grade or so .

*** EDIT *** I got the above code example working. It seems to be working correctly, too .

[edited by - MaulingMonkey on July 18, 2003 7:22:47 PM]

This is often called "arbitrary precision arithmetic". Using that term in your favorite search engine might turn up some useful info.

Edit:
Had this link lying around to the Numerical Recipes in C chapter dealing with arbitrary precision math. The sample code is all in C, but the concepts ought to be what you're looking for.

[edited by - GrinningGator on July 18, 2003 8:05:32 PM]

Thanks a bunch for all the help, and if anyone has anything else to say, I''d appreciate that too.

I would think something like the below would suit well:

struct unboundedInt {
    long length;
    __int8 *data;     // The actual digits. Probably malloc'd.

                      // Choose either big or small endian.

}

This would obviously be bounded by the length of "long", but this would allow any number that fits in the address space.

If you need longer (Eg, if this is theoretical), try nesting unboundedInt like:

struct unboundedInt {
    long length;
    unboundInt *bigLength;
    char lengthType;       // Whether length or bigLength is valid.

    __int8 *data;
}

But I can see no practical reason why you'd need to nest it.

[edited by - Krylloan on July 19, 2003 5:46:37 AM]

Try Here. I'm not sure if it works outside of linux since I've never had the chance to play with it.

[edited by - Cocalus on July 19, 2003 6:39:42 AM]

Krylloan:
A 'long' _LENGTH VARIABLE_ will support the aforementioned class having it's _DATA VARIABLE_ point to an area of allocation up to the size of 4GB. Considering you can not allocate that much memory, and on many/most systems you are limited to 4GB files, there should be no need to nest the 'unboundedInt'. If you need a bigger number, you will have a ton more problems to deal with which will require a different setup than simply nesting unboundedInt. (aka you will need to be referencing multiple files). Unless you are on a 64-bit system (and hence more virtual memory and such), then you could simply use a 64 bit integer as 'length'.

Also, for easier custom memory management setup, using an STL container (aka vector) would probably be more eloquant.

A system managing large numbers fast would probably have some sort of hybrid system - smaller numbers stored using a vector, larger numbers with a list of pre-determined size arrays. This makes resizing the data much easier (think about it: given a 1GB number, and you want to add a digit, using a simple malloced area and realloc ing it could potentially force the entire 1GB section of data to be relocated. And that won't even be an option at 2GB...meaning it won't be safe to grow it larger than 2GB).

However, a list or vector of pointers to 256byte chunks could grow much closer to 4GB.

Also, the best implementation will depend on how you're going to use the 'unbounded-int'. For a general math library, we've given some good layouts. For a space game, howver, a more compact and faster solution might be to use another hybrid system - 'unbounded-int's as points of reference for game objects, which would then have a relative bounded relative position in relation to the 'reference point'. If it needs to move outside this bound, then a new reference point would need to be created (or another one found in the same locality).

[edited by - MaulingMonkey on July 20, 2003 11:51:43 PM]

MaulingMonkey:
The range of an unsigned long int is 0-4,294,967,295. A variable of type unsigned long cannot actually contain a value that is 4gb of memory. The maximum storage alloted for unsigned long is 4 bytes.

After doing some studying, I've decided to implement the APA integer class using a doubly-linked list of binary ints each representing a part of the overall integer. It will be binary for efficiency and speed purposes.

[edited by - truiken on July 20, 2003 2:16:06 AM]

quote:

---

Original post by Truiken
MaulingMonkey:
The range of an unsigned long int is 0-4,294,967,295. A variable of type unsigned long cannot actually contain a value that is 4gb of memory. The maximum storage alloted for unsigned long is 4 bytes.

After doing some studying, I've decided to implement the APA integer class using a doubly-linked list of binary ints each representing a part of the overall integer. It will be binary for efficiency and speed purposes.

[edited by - truiken on July 20, 2003 2:16:06 AM]

---

quote:

---

Original post by MaulingMonkey a 'long' length will support a number that takes 4GB of space.

---

My appologies I did not state what I meant clearly. I repeat with clarity the above statement:

A 'long' _LENGTH VARIABLE_ will support the aforementioned class having it's _DATA VARIABLE_ point to an area of allocation up to the size of 4GB.

the _LENGTH VARIABLE_, indeed, only holds 4 bytes of data. However, it describes the _SIZE OF_ the _ALLOCATED AREA_ pointed to by the _DATA VARIABLE_.

I still think you should consider a hybrid allocation scheme... only 1/3rd of each list item (edit: of your proposal) would be actual data. More clarification:

Given: list< unsigned int >
each unsigned int of the list is stored as:

list_item *previous; //4 bytes overhead
unsigned int data; //4 bytes data
list_item *next; //4 bytes overhead

for each byte of data, there are two bytes of extra overhead.

whereas say: list< unsigned int [16] >
each item is stored as:
list_item *previous; //4 bytes overhead
unsigned int data[16]; //64 bytes data
list_item *next; //4 bytes overhead

for each byte of data, there is one _BIT_ of overhead.

Plus, looping through an array is faster than through a list. Lists are good for this task, but by allocating larger chunks you will speed calculation (edit: AND decrease memory useage).

I suggest a hybrid scheme because given the need to store "1" it wouldn't be fun to use --- (edit: ~64) bytes of data for such a simple number.

edit: by hybrid I mean something like (as an example):

class BigInt
{
private:
bool large;
union
{
std::list< unsigned int [16] > largedata; //if large == true
std::vector< unsigned int > smalldata; //if large == false
};
public:
//all your operators and such...
};

edit: I'm being obsessive in editing because I'm dismayed for being misunderstood as being such a dummy (edit of edit: even after providing a good, working example, which would imply I wasn't that stupid)... sorry, It's my ADD, although that's no good excuse...I think this is my last edit :/

edit: last edit? I think i've clarified...

edit: last edit.

[edited by - MaulingMonkey on July 20, 2003 11:56:54 PM]

hehe thanks MaulingMonkey for the tips...I''ll take them all into consideration. And now, on to the coding!