How to save a long number?

[obeeey]

Hi :)
I've got a task to save numbers of any size and then do some stuff with them.
The thing is, the MAX amount of those numbers to be loaded is 100 000, so I cannot use some static arrays, because they would use too much space.

Another problem is, I CANNOT use the <string> library, so there is no option to save this number as string.

Example:
11111111111111233424444444444555555555555
45444444444444444444444444444
5555555555555555444444444444444444444444444444444

My problem now: how to save those numbers? I was thinking about some dynamic char[] array, but I don't know if it's the best approach.

This is how I wanted to do this before I acknowledged the fact I cant use string:

#define N 100000

class numberData {
    public:
    int index = 0;
    std::string thisNumber;
    numberData* nextNumber = NULL;
};

numberData* createNext(std::string sentNumber)
{
    numberData* newData = new numberData();
    newData->thisNumber = sentNumber;
    newData->nextNumber = NULL;
    return newData;
}

void addNumber(numberData** myData, std::string thisNumber)
{   
    static int index = 0;

    numberData* newData = createNext(thisNumber);
    newData->thisNumber = thisNumber;
    newData->nextNumber = *myData;
    newData->index += index++;
    *myData = newData;
}

void readFromFile(numberData** myData)
{
    std::ifstream myFile("text.txt");
    std::string number;
    int count = 0;
    if(myFile.is_open())
    {
        while (count++ < N && myFile >> number)
            addNumber(myData, number);
    }
    else std::cout << "Problem with opening file..." << std::endl;
    myFile.close();
}

As you can see, in readFromFile() function I save those numbers into strings, and there I should think of something else...
Any help really appreciated. Thanks

[lastchance]

obeeey wrote:

do some stuff with them

Maybe you should tell us what "stuff" you intend to do with them.

After all, simply adding up their digits or doing "stuff" like that wouldn't require you to store them at all.

[jonnin]

the bigger the number, the less efficient it is to store as text at an increasing rate.
just store them in binary. Simply jacking the bytes into 2 64 bit ints is about 40 digits of text stored as only 16 chars.
its also best to process them as 64 bit integer blocks, or whatever the max on your machine is (some machines now have 128 bit registers if you want to go there). Like to add 2 128 bit values add the low order 64 bit values, get your carry, add the high order 64 bit values + the carry ... just 2 operations instead of the many when doing it char by char or text or other inefficient approaches.

[dhayden]

lastchance wrote:

Maybe you should tell us what "stuff" you intend to do with them.

+1

From what you've said so far, there's these are just strings of characters - nothing numeric about them. If you can't use string, can you use vector<char>?

Your numberData has a string for the digits and a nextNumber pointer. What does nextNumber point to?

[obeeey]

Thank you all for answers.
The "stuff" is to find the max and min number in the given list of numbers, and operations like + and - on them (given index i, assign sum of values from index j and k to i).

@lastchance, could you suggest any idea how I could do those things without storing them? I have no idea how that is achievable.

@jonnin, but what to do first? Firsly, I'm reading those numbers from .txt file, and with what should I start to save them binary? I haven't really saved numbers in binary.

Also, I forgot to add, I cannot use any vectors or STL, it has to be written in the most basic way.

[lastchance]

You still aren't giving enough information. I suggest that you state, verbatim, your original assignment or whatever it is - not your interpretation of it.

To find the maximum of a sequence of digits ... just read those digits one at a time, updating the variable you use to hold the maximum. To sum a subsequence of them, again, just read one digit at a time and accumulate between the digits that you want.

But is that what you want? - no idea, you simply aren't giving your whole problem. I can't even work out whether you are talking about single digits or larger entities.

[jonnin]

@jonnin, but what to do first? Firsly, I'm reading those numbers from .txt file, and with what should I start to save them binary? I haven't really saved numbers in binary.

unfortunately you will have to build them up by hand. If you are a beginner, you may want to process as strings instead.
I think i have a tiny example I did a while back. looking for it.

[jonnin]

Found it. Its messy, as it was just a quick example to multiply large integers and I never wrapped it up into a real object or anything clean. It may not be 100% bug free etc either, but its kinda the gist of the idea.

  const int base = 1000; //100000000 fits in 64 bit squared and seems like the best value
  const int logbase = 3; //the log base 10 of above. 
  
  string a = "1234567"; //couple of numbers to test with
  string b = "234567";
  uint64_t abi[5] = {0}; //big integers. this needs a class wrapper for operators etc later
  uint64_t bbi[5] = {0};
  uint64_t cbi[5] = {0}; 
  
  int i,j; //loop vars
      
  //convert text to big integer storage.
  for(i = 0; i < (a.length()/logbase); i++)
  {
	 abi[i] = stoi(a.substr(a.length()-logbase*(i+1),logbase)); 	 
  }  
  if(a.length()%logbase)
  {
	 int tmp = a.length()%logbase;
	 abi[i] = stoi(a.substr(0,tmp));
  }
      
  for(i = 0; i < (b.length()/logbase); i++)
  {
	 bbi[i] = stoi(b.substr(b.length()-logbase*(i+1),logbase));	 
  }
  if(b.length()%logbase)
  {
	 int tmp = b.length()%logbase;
	 bbi[i] = stoi(b.substr(0,tmp));
  }   
   
  //multiply   
  uint64_t cry = 0; //carry
  uint64_t tmp = 0; //intermediate
  for(i = 0; i < 3; i++) //need to figure out how many times to loop. 
  {
	  for(j = 0; j < 3; j++)//need to figure out how many times to loop. 
	  {
		 tmp  = bbi[i]*abi[j]; 		
		 cbi[i+j] += (tmp+ cry);
		 cry = cbi[i+j]/base;
		 cbi[i+j] %= base;			
	  }
	   cbi[i+j] += cry;
	   cry = 0;
  }	  

  //print result.  note we are storing backwards.   
  cout << cbi[3]<<cbi[2]<<cbi[1]<<cbi[0]; 
  //28958703552 output for 123456*234567 from calc.exe
  //289588677489 for 1234567 * 234567
    
}

once you have stuffed it into one of the uint64_t arrays you can just save that to a binary file with .write(); see a tutorial on that if you are new to it. I would just write some normal ints and floats to binary and read them back in a quick practice program before you try to do a big-int cold. The magic numbers are an issue in the example, you can optimize logbase and the rest for your code and should do so, its not right for everything but was just hard-coded for the one quick example.

I will see if I can get a min to redo it for yours later today.

[jonnin]

For yours, just raw storage ...

 const uint64_t base = 1000000000000000000ull; 
  const int logbase = 18; //the log base 10 of above. 
 
string a = "11111111111111233424444444444555555555555";
//string b = "45444444444444444444444444444";
//string c = "5555555555555555444444444444444444444444444444444";
  
  uint64_t abi[5] = {0}; //big integers. this needs a class wrapper for operators etc later
      
  //convert text to big integer storage. 
  for(i = 0; i < (a.length()/logbase); i++)
  {   
	 abi[i] = stoll(a.substr(a.length()-logbase*(i+1),logbase)); 	       
  }  
  
  if(a.length()%logbase)
  {
	 int tmp = a.length()%logbase;
	 abi[i] = stoll(a.substr(0,tmp));   
  }
  cout << abi[2]<<abi[1]<<abi[0] << endl; 
  cout <<hex<< abi[2]<<abi[1]<<abi[0];  //this is what the binary file would look like in a hex editor. 
// Its twice as long as the actual storage as each byte takes up 2 letters when printed. 
  

working in base 10 is a little lazy and wastes a little space, but its much simpler to understand. you can do it in base 64 or base 16 and get optimal space use if you want, but you will need to be on your game when you write multiply or the like if you need such things.
file.write((char*)(abi), size) to store and load from a file, the number a fits in 8*3 = 24 bytes instead of 41 (as text). you can increase[5] or vector up the 64 bit int arrays as needed, etc.

[obeeey]

@jonnin, thank you so much for your response. It's not so easy for me to understand it fully, but I'm going through it. Thanks so much for your help, it'll certainly help!

[dhayden]

The "stuff" is to find the max and min number in the given list of numbers, and operations like + and - on them

Please post the exact assignment as lastchance requested. Often there are important details whose importance you don't recognize.

For example, if you only need to do addition and subtraction and not multiplication and division then storing the digits in a linked list is probably okay.

Here is a start:

#include <iostream>

using std::cin;
using std::cout;
using std::istream;
using std::ostream;


// A node in a linked list of digits.
struct digit {
    digit(unsigned val) : d(val), next(nullptr) {}
    unsigned char d;
    digit *next;
};

class number {
public:
    number(unsigned val=0);
    ~number() { clear(); }
    number(const number & rhs);
    number &operator = (const number &rhs);

    // Assign from an unsigned
    number& operator = (unsigned val);

    // Read and write from/to a stream
    istream &read(istream &is);
    ostream &write(ostream &os);

    void clear();               // clear it to zero

private:
    // head of the digits list. First one is least significant digit
    digit *digits;
};

Some of these methods can be easily implemented using others:

number::number(unsigned val)
{
    // initialize digits and then use assignment operator
    digits = nullptr;
    *this = val;
}
// Copy constructor
number::number(const number & rhs)
{
    // initialize digits and then use assignment operator
    digits = nullptr;
    *this = rhs;
}

write() is hard for two reasons:
- The digits are stored starting with the least significant, but obviously you have to print starting with the most significant.
- Zero is a special case.

So I'll give you this one:

static void recursivePrint(ostream &os, digit *d)
{
    if (d == nullptr) {
        return;
    } else {
        recursivePrint(os, d->next);
        os.put(d->d + '0');
    }
}

ostream &number::write(ostream &os)
{
    // special case for zero
    if (digits == nullptr) {
        os << '0';
    } else {
        // this is a little harder since digits are stored with LSB first.
        // we'll call a recursive routine to print them in the right order
        recursivePrint(os, digits);
    }
    return os;
}

See if you can implement enough for this simple main program to work. It reads a number and then prints it out:

int main()
{
    number n;
    n.read(cin);
    n.write(cout);
}

[jonnin]

@jonnin, thank you so much for your response. It's not so easy for me to understand it fully, but I'm going through it. Thanks so much for your help, it'll certainly help!

There isn't that much to it, you are letting my Cish style intimidate you rather than looking at what it does, most likely.

all it does is cut a chunk off the text string that will fit into an integer using the specified number of digits, which happen to be what will fit clean in a 64 bit int. It then uses the built in tool to turn that chunk into the 64 bit int. It repeats this until it gets all the data converted. log10+1 gives you how many digits a number has, and its a fast way to get that value. A log is just an exponent, here, its a powers of 10, and again, all that is just digit counting really.

if you did the same thing for a smaller string into bytes instead of 64 bit ints, then,
12345 would just take 2 digits (all you can safely fit in a byte)
turn 12 into a byte-int value, repeat and turn 34 into a byte int value, and remainder out 5 into another byte-int value. cout prints them all jammed up so you still see 12345 and the second cout just turns them into hex (which again is 2 characters per byte on screen).

it looks cooler and more complex than it is, because logs get ooos and ahhhs from younglings.