Digit Carry problem with adding Arrays

hellfire1 (13)
Hello there!

To start, this thread may not be quite "General Programming" Material, however I posted it on the beginner forums a while ago, and apparently only 1 person is either willing or able to give advice, and he seems to be offline.

I will give a breif explanation here of my problem, and then point you to the thread that the entire problem is posted in, as it's simpler to open a new tab then to re-paste everything here.

I am having a problem currently trying to add two arrays of integers together. These arrays are up to 100 digits long each, and I'm hitting a wall with carried digits. I clearly have the code at least somewhat correct, as adding little things like 1555 and 1555 work, it outputs 3110 in another array.

However, I get errors when I add things like 500 and 500, it outputs 000, or if I add 999 and 2, I get 231?!

Clearly there are some major errors, but I've been searching for them, and cannot find them for the life of me...

I suspect the problem is both with my output function, and my add function, as I don't think my output function will output my expanded array, but I cannot figure out how to correct this.

The most up to date version of my code is here:
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
 
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

const int MAX_DIGITS = 100;

//prototypes

void inputVLI(int vli[], int& size);

void outputVLI(int vli[], int size);

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3);

int compVLI (int vli1[], int vli2[],
int size1, int size2);

/*
Write a main function that:
Declares three VLI: vli1, vli2 and vli3
Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
Outputs vli1 and vli2 (using outputVLI function)
Calculates vli3 (vli3 = vli1 + vli2, using addVLI function)
Compares vli1 and vli3 (using compVLI function)
*/

//main function

void main()
{
	int vli1[MAX_DIGITS], vli2[MAX_DIGITS], vli3[MAX_DIGITS+1]; //+1 is for a possible carried digit
	int size1, size2, size3;

	cout << "Step 1: INPUT\n"
		 << "------------------------------------------------------------------\n";
	cout << "A very long integer is a number of up to 100 decimal digits. \n"
		 << "Please enter a very long integer: \n";
	inputVLI(vli1, size1);
	cout << endl << "Please enter a second very long integer: \n";
	inputVLI(vli2, size2);
	
	cout << "Step 2: OUTPUT\n"
		 << "------------------------------------------------------------------\n";
	outputVLI(vli1, size1);
	cout << endl;
	outputVLI(vli2, size2);
	cout << endl;

	cout << "Step 3: ADDITION\n"
		 << "-------------------------------------------------------------------\n";
	addVLI(vli1,vli2,vli3,size1,size2,size3);
	outputVLI(vli3,size3);
}

//Function definitions

void inputVLI(int vli[], int& size)
{
	string vli1_string;
	bool no_error = true;

	do //enters the VLI as a string
	{
		cin >> vli1_string;
		cout << endl;
		size = vli1_string.length();  //claculates the size using .length
		for (int number = 0; number < size ; number++)
		{
			if (!isdigit((char)vli1_string[number])) //checks if string is entirely numbers
			{
				cout << "Your input was not all numbers. Input must be only numbers! \n\n"
					 << "Try again...\n";
				no_error = false;
				break;
			}
			else if (size >= MAX_DIGITS) //verifies that string is within max digits
			{
				cout << "Your input is over 100 digits long!\n"
					 << "Please enter a number with less than 100 digits... \n\n";
				no_error = false;
				break;
			}
			else // reassigns each character as an integer value
			{
				//takes each character of the array and converts it to an integer,
				//by subtracting the char '0'.
				no_error = true;
				vli[number] = vli1_string[number] - '0';
			}
		}
	}
	while (no_error == false); //keeps re-running until there is no errors...
}

void outputVLI(int vli[], int size)
{
	//simply takes each value of the array and outputs it with a space behind it.
	for(int number = 0; number < size; number++)
    {
        cout << vli[number] << " ";
    }
    cout << endl;
}

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3)
{
int vli1_int, vli2_int; //uses the integer changed arrays
int carried = 0; //realized I needed a way to figure out the carried numbers

//Determines which of the two numbers is bigger, to make the size of VLI3.
    if(size1 > size2)
    {
        size3 = size1;
    }
    else
    {
        size3 = size2;
    }

//cycles through each index, until it reaches the size of vli3.
    for(int number = 0; number <= size3; number++)
    {
	if (size1 - number >= 0)
		vli1_int = vli1[size1 - number];
	else 
		vli1_int = 0;
	//takes the numbers from right to left, unless there are none, then defaults to zero
	//this is to avoid an error with unknown array values
        
        if (size2 - number >= 0)
		vli2_int = vli2[size2 - number];
	else
		vli1_int = 0;
	//also takes the numbers from right to left, unless none exist, then defaults to zero
	//this is to avoid an error with unknown array values

	//States that if the value for the cell is over 9, it should be split into stored and carried digit.
	if (vli1_int + vli2_int + carried > 9)
	{
		vli3[size3 - number]= (vli1_int + vli2_int + carried)%10;
		carried = (vli1_int + vli2_int + carried)/10;
	}
	else
	{
		vli3[size3 - number]= (vli1_int + vli2_int + carried);
		carried = 0;
	}
		
	//If final number is over 9, it expands the array, and then shifts all values to the right.
	//It then places the carried digit in the new space created.
	if (vli3[0] > 9)
	{
		++size3;
		for (int number = 0; number <= size3; number++)
		vli3[size3 - number] = vli3[size3 - number + 1];
		vli3[0]= 1;
		vli3[1]= vli3[1]%10;
	}
    } 
}

int compVLI (int vli1[], int vli2[],
int size1, int size2)
{
	return 0;
}


Sorry to ask you to open a new tab up, but the thread that explains all of this in much more detail is here:
http://v2.cplusplus.com/forum/beginner/85207/

Please, please, please can someone have a serious look at this and help me with these errors? I've been at a standstill the whole day, and it's very frustrating.

Many thanks,
-Drew
kg1992 (30)
Hello.

It seems size3 needs to be bigger.

I tested it.

1 + 9 gives 0 to me. 99 + 99 gives me 98. The most significant digit is keep missing.

Hope it was helping.

=================================================

Wait, Wait... I'm sorry. I missed something.

[size2 - number] -> This goes out of range.

size of array might be the number of digits.

because number starts from 0, the first thing the program will read is
[size2]

which is one ahead of last element.
Last edited on
kg1992 (30) 
1
2
3
 
int vli1[MAX_DIGITS] = {0},
    vli2[MAX_DIGITS] = {0},
    vli3[MAX_DIGITS+1] = {0}; //+1 is for a possible carried digit



You better initialize them first. Notice that I attached "= {0}" for all arrays. This will initizlie all the elements of the array to 0.
Last edited on
kg1992 (30) 
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

const int MAX_DIGITS = 100;

//prototypes

void inputVLI(int vli[], int& size);

void outputVLI(int vli[], int size);

void addVLI(int vli1[], int vli2[], int vli3[],
            int size1, int size2, int& size3);

int compVLI (int vli1[], int vli2[],
             int size1, int size2);

void pushVLIToRight(int vli[], int size )
{
  for( int i = 0; i < size; ++i )
  {
    vli[MAX_DIGITS-size+i] = vli[i];
    vli[i] = 0;
  }
}

/*
Write a main function that:
Declares three VLI: vli1, vli2 and vli3
Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
Outputs vli1 and vli2 (using outputVLI function)
Calculates vli3 (vli3 = vli1 + vli2, using addVLI function)
Compares vli1 and vli3 (using compVLI function)
*/

//main function

void main()
{
  int vli1[MAX_DIGITS] = {0}, vli2[MAX_DIGITS] = {0}, vli3[MAX_DIGITS+1] = {0}; //+1 is for a possible carried digit
  int size1, size2, size3;

  cout << "Step 1: INPUT\n"
    << "------------------------------------------------------------------\n";
  cout << "A very long integer is a number of up to 100 decimal digits. \n"
    << "Please enter a very long integer: \n";
  inputVLI(vli1, size1);
  cout << endl << "Please enter a second very long integer: \n";
  inputVLI(vli2, size2);

  cout << "Step 2: OUTPUT\n"
    << "------------------------------------------------------------------\n";
  outputVLI(vli1, size1);
  cout << endl;
  outputVLI(vli2, size2);
  cout << endl;

  cout << "Step 3: ADDITION\n"
    << "-------------------------------------------------------------------\n";
  addVLI(vli1,vli2,vli3,size1,size2,size3);
  outputVLI(vli3,size3);
}

//Function definitions

void inputVLI(int vli[], int& size)
{
  string vli1_string;
  bool no_error = true;

  do //enters the VLI as a string
  {
    cin >> vli1_string;
    cout << endl;
    size = vli1_string.length();  //claculates the size using .length
    for (int number = 0; number < size ; number++)
    {
      if (!isdigit((char)vli1_string[number])) //checks if string is entirely numbers
      {
        cout << "Your input was not all numbers. Input must be only numbers! \n\n"
          << "Try again...\n";
        no_error = false;
        break;
      }
      else if (size >= MAX_DIGITS) //verifies that string is within max digits
      {
        cout << "Your input is over 100 digits long!\n"
          << "Please enter a number with less than 100 digits... \n\n";
        no_error = false;
        break;
      }
      else // reassigns each character as an integer value
      {
        //takes each character of the array and converts it to an integer,
        //by subtracting the char '0'.
        no_error = true;
        vli[number] = vli1_string[number] - '0';
      }
    }
  }
  while (no_error == false); //keeps re-running until there is no errors...
}

void outputVLI(int vli[], int size)
{
  //simply takes each value of the array and outputs it with a space behind it.
  for(int number = 0; number < size; number++)
  {
    cout << vli[number] << " ";
  }
  cout << endl;
}

void addVLI(int vli1[], int vli2[], int vli3[],
            int size1, int size2, int& size3)
{
  // Allgn numbers to the right.
  // Ex > 
  // vli1: 9 9 0 0 0 ... 0
  // vli2: 9 9 9 0 0 ... 0
  //          To
  // vli1: 0 0 0 ... 0 9 9
  // vli2: 0 0 0 ... 9 9 9
  pushVLIToRight( vli1, size1 );
  pushVLIToRight( vli2, size2 );

  // Get size of added number.
  size3 = ( size1 > size2 ? size1 : size2 );

  // Add
  // vli1: 0 0 0 ... 0 9 9
  // vli2: 0 0 0 ... 9 9 9
  //          To
  // vli3: 0 0 0 ... 9 18 18
  for( int i = 0; i < size3; ++i )
  {
    vli3[MAX_DIGITS - i] = vli2[MAX_DIGITS -1 -i] + vli1[MAX_DIGITS -1 -i];
  }

  // Pass carry nums
  // vli3: 0 0 0 ... 0 9 18 18
  //          To
  // vli3: 0 0 0 ... 1 0 9  8
  for( int i = 0; i < size3; ++i )
  {

    
    if( i == size3 - 1 // if it is the last iteration
     && vli3[MAX_DIGITS - i] >= 10 ) // and sum of two will have new digit
     size3++;

    // pass carry to next digit.
    vli3[MAX_DIGITS - i - 1] += vli3[MAX_DIGITS - i]/10;
    vli3[MAX_DIGITS - i] %= 10;
  }


  // Push vli3 to the left.
  // vli3: 0 0 0 0 ... 1 0 9 8
  //          To
  // vli3: 1 0 9 8 ... 0 0 0 0
  for( int i = 0; i < size3; ++i )
  {
    vli3[i] = vli3[MAX_DIGITS - size3 +1 + i];
    vli3[MAX_DIGITS - size3 +1 + i] = 0;
  }
}

int compVLI (int vli1[], int vli2[],
             int size1, int size2)
{
  return 0;
}


I know that it is so bad thing to do, but it got really hard to continue on your code, so I just show my own answer to you. Hope it helps you.

Idea is this: you can just add everything at once, and then think about carry. Consider following example:

99 + 999 = 1098

0 9 9
9 9 9+
---------

9 18 18

(Pass carry from third digit to second digit)

9 19 8

(Pass carry from second digit to first digit)

10 9 8

(Pass carry from first digit to new first digit)

1 0 9 8
Last edited on
hellfire1 (13)
Actually, this also has an error.

If you add long numbers, like 15555555555555555555555555555555 by itself for example, the program freaks out.

I'll look and see if I can find why, and where...

See:

Step 1: INPUT
------------------------------------------------------------------
A very long integer is a number of up to 100 decimal digits.
Please enter a very long integer:
14444444444444444444444444444444444444444444444444444444444444444444444444444444
44444444444444444444444444444444444444444444444444444444444444444444444444444444
444444444444444

Your input is over 100 digits long!
Please enter a number with less than 100 digits...

1555555555555555555555555555555555555555555555555555555555555555555555555555555


Please enter a second very long integer:
1555555555555555555555555555555555555555555555555555555555555555555555555555555

Step 2: OUTPUT
------------------------------------------------------------------
1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

Step 3: ADDITION
-------------------------------------------------------------------
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
Press any key to continue . . .


Here's another example of error:

Step 1: INPUT
------------------------------------------------------------------
A very long integer is a number of up to 100 decimal digits.
Please enter a very long integer:
99999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999

Your input is over 100 digits long!
Please enter a number with less than 100 digits...

99999999999999999999999999999999999999999999999999999999999999999999999999999999



Please enter a second very long integer:
99999999999999999999999999999999999999999999999999999999999999999999999999999999


Step 2: OUTPUT
------------------------------------------------------------------
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9


9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9


Step 3: ADDITION
-------------------------------------------------------------------
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8

Press any key to continue . . .


It seems to have issues on very large numbers, even though it now works for smaller ones.
Last edited on
hellfire1 (13)
Ok, I've found that the exact number of digits that start to return errors are when you have a number of OVER 50 digits being added to something.

Then the addition part returns crazy values.... why is it doing this??!

EDIT:

Ok, it seems to be related to MAX_DIGITS...

If MAX_DIGITS = 100, it accepts up to 50 digits correctly. If I alter MAX_DIGITS to 200, it now works with up to 100 digits, which is correct.

However, this is NOT the way this is intended to work, and rather than rig it with duct tape so to speak, I'd really love if someone could help me find the error and solve this so MAX_DIGITS works correctly.

I'm using a variant of the code kg1992 posted, but it works exactly the same as the one he posted, complete with the error I am having.
Last edited on
kg1992 (30)
Sorry my fault.

Push to right is the actual problem. It will not work for big numbers. Using following pushVLIToRight will solve the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void pushVLIToRight(int vli[], int size )
{
  int source[MAX_DIGITS];

  for( int i = 0; i < size; ++i )
  {
    source[i] = vli[i];
    vli[i] = 0;
  }
  for( int i = 0; i < size; ++i )
  {
    vli[MAX_DIGITS-size+i] = source[i];
  }
}
hellfire1 (13)
Ah yes, thanks! :)

Could you clarify what you did there^ ?

I'm a bit unclear as to why the addition of the source[MAX_DIGITS], and what it is doing...

if I understand it correctly, you're copying the VLI to source, and then wiping the original VLI?

And then below, you re-assign the numbers from source back to VLI but from right to left?
Why was this needed, rather than the original function?


Sorry if all these questions are bothersome, but I like to understand what why things work. :)

EDIT: Another question as well, sorry, this is more of me not understanding your code then an error, it's an easy fix if I knew how.

Currently the problem works up to 99 digits, but flops at 100. I'm afraid I don't quite understand what you've done with your code well enough to try to edit it to accept 100 digits, without changing the MAX_DIGITS again to 101...

But I'm sure if I stare at this in the morning I'll see it, it's late and it's a horrible time to be working on programming :P

Thanks so much for the help, if you get to these questions, awesome, but if you miss them for some reason, no big deal, I can work though this. :)
Last edited on
kg1992 (30)
Hello.

It is not bad thing to understand, and I feel a little sorry about giving you terrible explanation about what I did.

What happened with original pushVLIToRIght is somehow similar with this:

1
2
3
4
5
6
 
void Swap( int&a, int&b )
{
  a = b;
  b = a;
// Now a and b is the same value..
}


The function needed some information inside the vli. But because it rewrites some values in the vli before it can read it, problem happened.

So I created new array that will mirror the original vli, and than I changed vli. "source" in the function does similar thing with "temp" in this:

1
2
3
4
5
6
 
void Swap( int&a, int&b )
{
  temp = a;
  a = b;
  b = temp;
}

Last edited on
Registered users can post here. Sign in or register to post.

C++

Forum