BigInt as String

[goldenchicken]

Hey everyone!
So I'm writing my own BigInt class and i came up with the idea to store the numbers as strings. I got stuck when writing the addition function, as it started throwing bad_alloc's and i have no idea where. Anyone who can help me? Thanks

//intString.h
#include <iostream>
#include <string>
#include <algorithm>
class intString
{
public:
	std::string  m_value;
	intString(int value = 0);
	std::string getValue();
	void setValue(std::string s);
	friend intString operator+(intString &s1, intString &s2);
	friend std::ostream& operator<<(std::ostream &out, intString& val);
};


//intString.cpp
#include "intString.h"
intString::intString(int value) : m_value(std::to_string(value)) {  }
void intString::setValue(std::string s) { m_value = s;}
std::string intString::getValue() { return m_value;}


//operators.cpp
#include "intString.h"

const int ZERO_ASCII_CODE = 48;
//utility
int to_int(char numb)
{
	return (int)numb - ZERO_ASCII_CODE;
}

//in and output operators
std::ostream& operator<<(std::ostream &out, intString& val)
{
//crashes here
	out << val.getValue();
	return out;
}

//basic arithmetics
intString operator+(intString &s1, intString &s2)
{

	std::reverse((s1.getValue()).begin(), (s1.getValue()).end());
	std::reverse((s2.getValue()).begin(), (s2.getValue()).end());
	std::string reversed1 = s1.getValue();
	std::string reversed2 = s2.getValue();
	std::string result = "";
	//loop trough largest string
	std::string longest;
	std::string shortest;
	if (reversed1.length() > reversed2.length())
	{
		longest = reversed1;
		shortest = reversed2;
	}
	else
	{
		longest = reversed2;
		shortest = reversed1;
	}
	bool addOneToNext = false;
	for (int i = 0; i < longest.length(); ++i)
	{

		if (i < shortest.length())
		{
			int add = longest[i] + shortest[i];
			if (addOneToNext == true)
			{

				add += 1;
				addOneToNext = false;
			}
			//add last character to the resulting string

			result += std::to_string(add)[std::to_string(add).length()-1];
			if (add > 9)
				addOneToNext = true;

		}
		else result += longest[i];
	}
	if (addOneToNext == true)
		result += "1";
	std::reverse(result.begin(), result.end());
	intString answer(0);
	answer.setValue(result);
}

[Chervil]

This code gives compiler warnings when I tried to compile it.
The first at line 65

    for (int i = 0; i < longest.length(); ++i)

[Warning] comparison between signed and unsigned integer expressions [-Wsign-compare]

That's easily remedied by changing int i to an unsigned type, such as size_t.

    for (size_t i = 0; i < longest.length(); ++i)

Another compiler warning at line 91:

[Warning] no return statement in function returning non-void [-Wreturn-type]

Though it is 'only' a warning, its impact is severe. The function promises to return an intString but doesn't do so.

Inserting the line

    return answer;

just before the closing brace at line 91 should resolve that.

I tested the program as follows:

int main()
{
    intString a = 123;
    intString b = 456;
    
    std::cout << "a = " << a << '\n';
    std::cout << "b = " << b << '\n';
    
    intString c = a + b;
    
    std::cout << "c = " << c << '\n';
}

This was the output:

a = 123
b = 456
c = 1641

The value of c is incorrect, it should be 579, not 1641.

It also gives the somewhat surprising result, 0 + 0 = 16

a = 0
b = 0
c = 16

I've not attempted to debug the problem any further.


It is good practice to use const where appropriate. Also make the member variable m_value private.

class intString
{
    std::string  m_value;

public:
    intString(int value = 0);
    std::string getValue() const;
    void setValue(std::string s);
    friend intString operator+(const intString &s1, const intString &s2);
    friend std::ostream& operator<<(std::ostream &out, const intString& val);
};

[Chervil]

Here are a couple of problems. Lines 46, 47 don't do anything useful.

std::reverse((s1.getValue()).begin(), (s1.getValue()).end());

This is operating on the temporary values returned by function getValue().

Instead, do the reverse later.

    std::string reversed1 = s1.getValue();
    std::string reversed2 = s2.getValue();
    std::reverse(reversed1.begin(), reversed1.end());
    std::reverse(reversed2.begin(), reversed2.end());

Another problem here at line 70:

int add = longest[i] + shortest[i];

Since the values are character codes, not integers, you need to subtract ZERO_ASCII_CODE from each.

[jonnin]

I highly advise you not try to use text. Its going to be very, very slow to multiply or do anything interesting with your numbers like this.

[goldenchicken]

@Chervil: Thanks alot for pointing out these problems!

@jonnin: This was the first idea for a bigInt class that I could come up with.

[jonnin]

Its fine if what you need is to store and print big numbers, and not much else, maybe a little simple math. If you need to do a LOT of math or involved math, the performance of it will get you coming and going. If you haven't gotten into it too deeply, and you want it to perform well for many operations, you might want to go back to the design table.

[goldenchicken]

The only thing i want it to do is basic operations (+, -, *, /)

[lastchance]

@goldenchicken,
I think that using strings for large integers is likely to lead to a lot of hard work, with continual conversion between characters and integers to do numerical operations. You really only need to be choosing a suitable container for the digits: vector<int> might be more suitable.

The only thing i want it to do is basic operations (+, -, *, /)

The first three are fine. However, the fourth ... I did this once and had awful trouble with the divide operation for a large-integer class.

[jonnin]

Well, since we threw performance out the windows anyway, just call your addition function in a loop to multiply and subtract in a loop to divide? :P And if your subtract is really your add with a negative 1 ... you only need 1 function.

I joke, 2 > 64 bits multiplied by adding this way would take hours each, maybe more. The division by multiply by 1/x was serious though, it might be worth trying.

[JLBorges]

#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <iomanip>

struct int_string
{
    void reduce() { for( char& c : digits ) c -= '0' ; } // convert to integers 0-9
    void restore() { for( char& c : digits ) c += '0' ; } // convert to character '0'-'9'

    int_string( unsigned long long value ) : digits( std::to_string(value) ) {}

    int_string( std::string value ) : digits( std::move(value) )
    {
        if( digits.empty() ) digits = "0" ;
        for( char c : digits ) // sanity check
            if( !std::isdigit(c) ) throw std::invalid_argument( "badly formed number" ) ;
    }

    int_string( const char* value ) : int_string( std::string(value) ) {} // delegating constructor

    // implement the compound assignment operator += (a long inline friend)
    // friends defined inside class body are inline and are accessible
    // only via argument-dependant lookup (aka koenig look up)
    // note: a is passed as reference to non-const; the original is modified
    //       b is passed by value; the function receives a copy which it can safely trash
    friend int_string& operator+= ( int_string& a, int_string b )
    {
        // using the same logic as in the original post

        // reverse both strings
        std::reverse( a.digits.begin(), a.digits.end() ) ;
        std::reverse( b.digits.begin(), b.digits.end() ) ;

        // resize both to max size (+1 because there may be a carry at the end)
        const std::size_t max_digits = std::max( a.digits.size(), b.digits.size() ) + 1 ;
        a.digits.resize( max_digits, '0' ) ;
        b.digits.resize( max_digits, '0' ) ;

        // reduce both to hold integer digits 0-9
        a.reduce() ;
        b.reduce() ;

        // normal long hand addition
        int carry = 0 ;
        for( std::size_t i = 0 ; i < max_digits ; ++i )
        {
            a.digits[i] += b.digits[i] + carry  ;
            carry = a.digits[i] / 10 ;
            a.digits[i] %= 10 ;
        }

        // remove leading zero digits
        while( a.digits.size() > 1 && a.digits.back() == 0 ) a.digits.pop_back() ;

        // reverse the result and restore digits back to characters '0'-'9'
        std::reverse( a.digits.begin(), a.digits.end() ) ;
        a.restore() ;

        return a ;
    }

    // canonical: For every binary arithmetic operator there should exist
    // a corresponding compound assignment operator; canonical forms of binary operators
    // are implemented in terms of their compound assignments
    // note: a is passed by value; so we return the result of a+=b
    // passing lhs by value helps optimize chained a+b+c
    // for more information, see: overloading Binary arithmetic operators in
    // http://en.cppreference.com/w/cpp/language/operators
    friend int_string operator + ( int_string a, const int_string& b ){ return a += b ; }

    friend std::ostream& operator << ( std::ostream& stm, const int_string& number )
    { return stm << number.digits ; }

    private: std::string digits ;
};

int main()
{
    const int_string a = 123456789012 ;
    const char* b = "5678901234567890123456789" ;
    const std::string c = "98765432101234567890123456" ;
    const unsigned int d = 2345678 ;

    std::cout << std::setw(30) << a << " +\n"
              << std::setw(30) << b << " +\n"
              << std::setw(30) << c << " +\n"
              << std::setw(30) << d << " ==\n"
              << std::setw(30) << "---------------------------" << '\n'
              << std::setw(30) << a+b+c+d << '\n' ;
}

http://coliru.stacked-crooked.com/a/3da16ae728f9ccf4