C++

Forum

 
C++ Summing large numbers using string

Mastaron (4)
Hi guys,
for a competition I needed to store large numbers (>20 length) and to add them with other large numbers. So i made this code:

//add.cpp
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
 
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int m=0;

char sum(int a, int b, int c)
{
	if(c==1) m=(a+b)/10;
	else m+=(a+b)/10;
	return (a+b)%10+'0';
}

string add(string a, string b)
{
	if(b.length()>a.length()||(b.length()==a.length()&&b[0]-'0'>a[0]-'0')) swap(a,b);
	string c="";
	int i=a.length()-1,j=b.length()-1;
	while(i>=0)
	{
		if(j<0)
		{
			c+=sum(a[i]-'0',m,1);
			i--;
		}
		else
		{
			int m2=m;
			c+=sum(sum(a[i]-'0',b[j]-'0',1)-'0',m2,0);
			i--; j--;
		}
	}
	if(m!=0) c+=sum(m,0,1);
	for(int i=0;i<=(c.length()-1)/2;i++)swap(c[i],c[c.length()-1-i]);
	return c;
}

int main()
{
	ifstream f ("input.txt");
	ofstream g ("sum.txt");
	string s,s2;
	f>>s>>s2;
	g<<add(s,s2);
	f.close(); g.close();
	return 0;
}


//input.txt
1
2
3
 
32485689234981709712094710984091842358764876328746187648716462938589273589723895789237587238947189748917894718973891728937189478913277893257891749817984719287439812789473289475328975981723894718927489127894712894

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999


//sum.txt
32485689234981709712094710984091842358764876328746187648716462938589273599723895789237587238947189748917894718973891728937189478913277893257891749817984719287439812789473289475328975981723894718927489127894712893

I checked the answer at https://defuse.ca/big-number-calculator.htm, and it was the same.
The program ran for 0,016s.

Can you tell me a faster way to add them? At this competition the most important thing is the time, so I would apreciate your comment.

Thank you,
Mastaron
Last edited on
dhayden (5798)
Don't do division (or remainder) in the sum() function. Division is very time consuming. Here is a version without it. I've also cleaned up the way sum() works a little bit.
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
 
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

// Add a, b, and carry.  Return the least significant digit
// and update carry.
int
sum(int a, int b, int &carry)
{
    int result = a+b+carry;
    if (result >= 10) {
        result -= 10;
        carry = 1;
    } else {
        carry = 0;
    }
    return result;
}

string
add(string a, string b)
{
    int s {0}, carry {0};

    if (b.length() > a.length() ||
        (b.length() == a.length() && b[0] - '0' > a[0] - '0')) {
        swap(a, b);
    }
    string c = "";
    int i = a.length() - 1, j = b.length() - 1;
    while (i >= 0) {
        if (j < 0) {
            s = sum(a[i] - '0', 0, carry);
            // c += sum(a[i] - '0', m, 1);
            i--;
        } else {
            s = sum(a[i] - '0', b[j] - '0', carry);
            i--;
            j--;
        }
        c += s+'0';
    }
    if (carry)
        c += '1';
    for (int i = 0; i <= (c.length() - 1) / 2; i++)
        swap(c[i], c[c.length() - 1 - i]);
    return c;
}

int
main()
{
    ifstream f("input.txt");
    ofstream g("sum.txt");
    string s, s2;
    f >> s >> s2;
    g << add(s, s2);
    f.close();
    g.close();
    return 0;
}


Mastaron (4)
Thank you for your code and advice :)
Topic archived. No new replies allowed.