Large number addition method

Question

  It’s a simple and usual question. If you need to add 2 50-digit numbers, what would you do? The first thing a dummy would look into is definitely the limits of the primitive data type. But note that, a 32-bit machine with a separate floating point processor can at max process 64-bit (for double). So, it comes to max 2^64 which is 20 digits. Then how would you solve for more digits?

Say, the question is you need to add some 100’s of 50-digit numbers and you need to find the first 20 digits.

Brain storm

  I started solving the problem. Straight forward I knew that I need to write code for a simple adder system. Addition is very simple considering the operations required for doing it.

1. Take the LSD part (Least significant digit or the last digit in the number)
2.  Add all the LSD digits of the given numbers (50^th digit)
3.  Ex: if there are 100 numbers with digit max which can be 9, it can add up to max 900.
4. We need to maintain a carry which is the digits other than the last digit that we got in the sum
5. Take carry as well in addition of the next set of digits. (49-0^th digit)
6. Finally output the sum

The method I followed to find the last digit is not much optimized. That is, if you divide a number by 10, you get the carry value. If you mod the number by 10, you get the remainder which is nothing but the last digit.

This same question might get twisted for different bases. Say, you need to do the same for base 2. J Then the rules are different and our algorithm won’t work.

Code

int main()

{

    char line[55];

    short dignum[100][50];

    int count=0;

    ifstream myfile ("eulerinput.txt");

    for(int i=0 ; i<100; i++) {

        myfile.getline(line, 51);

        for(int j=0; j < 50; j++) {

            dignum[i][j] = line[j]-48;

            cout<<dignum[i][j];

        }

      cout<<endl;

    }

    int carry=0; // never >999.. since 100 digits addition + carry can never exceed over 999

    //adder

    int dsum;

    for(int i=49; i>=0; i--) {

      dsum = 0;

      for(int j=0; j < 100; j++) {

                  dsum += dignum[j][i];

      }

      dsum += carry;

      carry = dsum/10;

      cout<<dsum%10<<" "; //digits in reverse

    }

    cout<<endl<<dsum;

    return 0;

}