C++

Forum

 
Adding large numbers

Gulopey (44)
I have to make a function that can add two numbers of any size. So far I have:


#include <iostream>
#include <string>

struct number {
string data;
number(string num = NULL);
number * flip();
};

number :: number(string num) {
data = num;
}

.
.
.


number * number :: flip() {
number * flipped = new number(data);
for (int i=0; i<data.length(); i++) {
flipped->data[i] = data[(data.length()-1)-i];
}
return flipped;
}
number * add(number * a, number * b) {
number * aflip = a->flip();
aflip->data += '0';
number * bflip = b->flip();
bflip->data += '0';
number * sum;
if (aflip->data.length() > bflip->data.length()) {
int diff = aflip->data.length() - bflip->data.length();
for (int i=0; i < diff; i++) {
bflip->data += '0';
}
} else if (aflip->data.length() < bflip->data.length()) {
int diff = bflip->data.length() - aflip->data.length();
for (int i=0; i < diff; i++) {
aflip->data += '0';
}
}
int digit1;
int digit2;
int carry = 0;
for (int i=0; i<(aflip->data.length()-1); i++) {
digit1 = (int)(aflip->data[i]) - 48;
digit2 = (int)(bflip->data[i]) - 48;
if (digit1 + digit2 + carry < 10) {
sum += (char)(digit1 + digit2 + carry + 48);
carry = 0;
} else {
sum += (char)(digit1 + digit2 + carry - 10 + 48);
carry = 1;
}
}
sum -> flip();
return * sum;

}

Can anyone tell me why I'm getting a segmentation fault? It's really dense because of all the conversions I had to do. Thanks.
Catfish3 (666)
Please use code tags when posting code.
http://cplusplus.com/articles/jEywvCM9/

Can anyone tell me why I'm getting a segmentation fault?


number * sum;

Why is sum declared as a pointer? You overuse pointers. Also I can see a possible memory leak (in C++, every new operation must have a corresponding delete operation.)
Gulopey (44)
Ok I'm trying to add a destructor in order to avoid the memory leakage. I get the error message :

lab4.cpp:46: error: `struct std::basic_string<char, std::char_traits<char>, std::allocator<char> >' used where a `int' was expected
lab4.cpp:47: error: `struct std::basic_string<char, std::char_traits<char>, std::allocator<char> >' used where a `int' was expected

after using the destructor:

1
2
3
4
5
6
7
8
 
struct number {
        string * data;
        number(string num = NULL);
        number * flip();
        ~number() {
                delete data;
        }
};
Gulopey (44)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
int digit1;
        int digit2;
        int carry = 0;
        for (int i=0; i<(aflip->data->length()-1); i++) {
                digit1 = (int)(aflip->data[i]) - 48;
                digit2 = (int)(bflip->data[i]) - 48;
                if (digit1 + digit2 + carry < 10) {
                        sum->data += (char)(digit1 + digit2 + carry + 48);
                        carry = 0;
                } else {
                        sum->data += (char)(digit1 + digit2 + carry - 10 + 48);
                        carry = 1;
                }
        }
        sum = sum->flip();
        return sum;


line 5-6 is what the error is referring to.
Last edited on
Catfish3 (666)
1
2
3
4
5
6
7
8
9
 
number * number :: flip() {
    number * flipped = new number(data);

    for (int i=0; i<data.length(); i++) {
        flipped->data[i] = data[(data.length()-1)-i];
    }

    return flipped;
}


And how about deleting flipped, where will that happen?

Look, I won't sugarcoat this. Your code is currently a pointer mess.

The first thing that you should do now is to correct your code, and use "plain" variables instead of pointers.

lab4.cpp:46: error: `struct std::basic_string<char, std::char_traits<char>, std::allocator<char> >' used where a `int' was expected
lab4.cpp:47: error: `struct std::basic_string<char, std::char_traits<char>, std::allocator<char> >' used where a `int' was expected
number(string num = NULL);

NULL is for pointers, and num isn't.
Gulopey (44)
My assignment requires that I use a destructor for my struct. Is there a way to use one without making data a pointer?
Gulopey (44)
So basically what I'm asking is, why won't C++ convert: 

1
2
 
              digit1 = (int)(aflip->data[i]) - 48;
              digit2 = (int)(bflip->data[i]) - 48;


to an int.
Catfish3 (666)
My assignment requires that I use a destructor for my struct.

That's as silly as requiring to put mustard on pizza. One should put mustard where it's needed!

Anyway. In this case, you can do this: make your data a pointer, allocate and de-allocate memory.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
struct number
{
    string *data;

    number(): data(new string)
    {
    }

    ~number()
    {
        delete data;
    }
};


But if you can get away with it, I suggest you simply use an empty destructor which does nothing.

1
2
3
4
5
6
7
8
9
10
 
struct number
{
    string data;

    // ...

    ~number()
    {
    }
};


Personally I'd like to see exactly what your assignment asks, then I could give you more appropriate advice.
Gulopey (44)
My assignment is to create a struct capable of holding an object that is a number of any size with functions capable of adding, multiplying, subtracting and factorialing that object. I also have to have a constructor, a destructor and a print method. My current print method is:

1
2
3
4
5
6
 
void number :: print() {
        for (int i=0; i<data->length(); i++) {
                cout << data[i];
        }
        cout <<"\n";
}


When I try to replace 

1
2
 
              digit1 = (int)(aflip->data[i]) - 48;
              digit2 = (int)(bflip->data[i]) - 48;


with 

1
2
3
4
 
                digit1 = 5;
                aflip->print();
                digit2 = 3;
                bflip->print();


to see what is wrong it gives me a segmentation fault. I do believe you are correct in that I probably have memory leakage going on. My destructor is not helping in this regard.

E: Actually it seems like the problem stems from:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
struct number {
        string * data;
        number(string num);
        number * flip();
        void print();
        ~number() {
                delete data;
        }
};

number :: number(string num) {
        data = num;
}


I think I am running into problems for assigning num to a pointer to a string rather than a string. I don't know how to assign it to the string, though as it seems everything I try will result in an error message.
Last edited on
Pranay Venkatesh (9)
All You need to do is add long ints. Then use the basic stream of C++ coding to finish off.
Catfish3 (666)
@Pranay: not if he was tasked with coding an arbitrary precision arithmetic library.

Honestly Gulopey, I'm too dumb to help you.

I know one thing though, if I were you I'd say "screw the requirements" and go the path of least resistance, by using an std::vector<unsigned char>, no destructor, and only accepting hexadecimal formatted input (that is, strings of numbers in base 16). That would simplify the tasks of addition and subtraction a bit, but this is still hard stuff.

Many languages have built-in libraries doing what you try to code. C++ has 3rd party libraries, Boost and GMP.
JLBorges (13770)
> My assignment requires that I use a destructor for my struct.
> Is there a way to use one without making data a pointer?

Yes. Just define a trivial destructor.


> I think I am running into problems for assigning num to a pointer to a string rather than a string.

Why do you need to use pointers at all. Using the same logic as in your original code (flip the number, add digit by digit with carry etc.):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <iostream>
#include <vector>
#include <cctype>
#include <stdexcept>
#include <algorithm>

struct number
{
    ~number() {} // destructor (as required)

    number( const char* cstr ) : number( std::string(cstr) ) {}

    number( const std::string& s = "" ) : digits( s.begin(), s.end() )
    {
        for( int& c : digits )
        {
            if( std::isdigit(c) ) c -= '0' ;
            else throw std::out_of_range( "not a decimal digit" ) ;
        }
    }

    std::vector<int> digits ;
};

std::ostream& operator<< ( std::ostream& stm, const number& n )
{
    for( int d : n.digits ) stm << d ;
    return stm ;
}

number flip( const number& n )
{
    auto f = n ;
    std::reverse( f.digits.begin(), f.digits.end() ) ;
    return f ;
}

number operator+( number a, number b )
{
    a = flip(a) ;
    b = flip(b) ;
    auto& aa = a.digits ;
    auto& bb = b.digits ;

    auto n = std::max( aa.size(), bb.size() ) + 1 ;
    aa.resize( n, 0 ) ;
    bb.resize( n, 0 ) ;

    number c ;
    auto& cc = c.digits ;
    cc.resize(n) ;

    int carry = 0 ;
    for( std::size_t i = 0 ; i < n ; ++i )
    {
        cc[i] = aa[i] + bb[i] + carry ;
        carry = cc[i] / 10 ;
        cc[i] %= 10 ;
    }

    while( cc.back() == 0 && cc.size() > 1 ) cc.pop_back() ;
    c = flip(c) ;
    return c ;
}

int main()
{
    number a = "12345678909876543210987654321" ;
    number b = "99999999999999999999999999999999999999999" ;
    std::cout << a+b << '\n' ;
}


http://liveworkspace.org/code/1FgQvR$0
closed account (D80DSL3A)
I'd go with the non-pointer based methods being recommended, but I think I see a reason for the crashes with your pointer based method.

The member data is a pointer to a string, so data[i] would refer to the ith string in an array of strings pointed to by data, not to the ith character in the single string pointed to by data. There are many places in your code which would crash the program.
Try (*data)[i] instead?

EDIT: Is dynamic allocation an actual requirement? If so then maybe it's intended that you work with a dynamically allocated array of characters or integers, not a std::string.
Last edited on
Gulopey (44)
Thanks a lot for the help guys. I went and spoke to my professor and he cleared up why a lot of those unnecessary things were part of the program requirements. I'm going to completely redo it using an array of ints that take the place of the strings I was using before. To any newbie that reads this: I highly recommend that you don't try to figure out how to make things work when your professor gives you strange requirements like this. Go talk to him and see what he had in mind when he assigned it.
Gulopey (44)
Ok after redoing it using your suggestions combined with what the teacher wante, I was able to get it this far:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
number * add(number * a, number * b) {
        number * reverse1 = a->flip();;
        reverse1->print();
        reverse1->size += 1;
        reverse1->digits[reverse1->size] = 0;
        number * reverse2 = b->flip();
        reverse2->print();
        reverse2->size += 1;
        reverse2->digits[reverse2->size] = 0;
        if (reverse1->size > reverse2->size) {
                int fixed[reverse1->size];
                for (int i=0; i<reverse1->size; i++) {
                        fixed[i] = reverse2->digits[i];
                }
                for (int i=reverse2->size-1; i<reverse1->size; i++) {
                        fixed[i] = 0;
                }
                reverse2->digits = fixed;
                //delete [] fixed;
        } else if (reverse2->size > reverse1->size) {
                int fixed[reverse2->size];
                for (int i=0; i<reverse2->size; i++) {
                        fixed[i] = reverse1->digits[i];
                }
                for (int i=reverse1->size-1; i<reverse2->size; i++) {
                        fixed[i] = 0;
                }
                reverse1->digits = fixed;
                //delete [] fixed;
        }
        number * sum = new number("0");
        sum->size = (a->size + 1);
        sum->digits = new int [sum->size];
        int carry = 0;
        reverse1->print();
        reverse2->print();
        for(int i=0; i<reverse1->size; i++) {
                if (reverse1->digits[i] + reverse2->digits[i] <10) {
                        sum->digits[i] = carry + reverse1->digits[i] + reverse2->digits[i];
                        carry = 0;
                } else {
                        sum->digits[i] = carry + reverse1->digits[i] + reverse2->digits[i] - 10;
                        carry = 1;
                }
        }
        return sum;
}


I get bus error (core dumped) when I try this. digits is the place I store an array of ints and size is the int size of the array.
Catfish3 (666)
http://www.oit.uci.edu/help/manuals/uci.unix.guide/common_mistakes_and_pitfalls/segmentation.html

1
2
3
4
5
6
7
 
        number * sum = new number("0");
        sum->size = (a->size + 1);
        sum->digits = new int [sum->size];

        // ...

        return sum;


I hope you remembered to delete[] sum->digits; and then delete sum; ... somewhere.
Gulopey (44)
Thank you very much Catfish. Your comment showed me that I didn't initialize another number, which is what caused this mess.
Topic archived. No new replies allowed.