CODEWITHSUNDEEP
algorithmlanguage-agnostic
Aks
Aks

Reputation: 5236

Multiplying two numbers represented as strings

Given two numbers, 123 and 456 as strings, I want to be able to multiply them and print the string output. I can't convert them to numbers because they could potentially be very long. I have working code for this problem as below

string multiply(string num1, string num2) {
    if(num1[0]=='0'||num2[0]=='0') return "0";
    int n1(num1.size()), n2(num2.size()), n(n1+n2);
    vector<int> r(n,0);
    string      s(n,'0');
    for(size_t i=0;i<n1;++i){
        for(size_t j=0;j<n2;++j){
            r[i+j+1]+=(num1[i]-'0')*(num2[j]-'0');
        }
    }
    for(size_t i=n-1;i>0;--i){
        if(r[i]>9)  r[i-1]+=r[i]/10;
        s[i]  += r[i]%10;
    }
    s[0]+=r[0];
    return s[0]=='0'?string(s.begin()+1,s.end()):s;
}

But I cant figure out how this logic was arrived at. Why are we putting the products in i+j+1 and then carrying afterwards? Is this some standard multiplication logic?

Upvotes: 1

Views: 6536

Answers (1)

HugoRune
HugoRune

Reputation: 13819

You are essentially multiplying a series of numbers:
123 * 456 becomes [100 + 20 + 3] * [400 + 50 + 6]

If you multiply 100 (3 digits) and 400 (3 digits) you will get 40000 (5 = 3 + 3 - 1 digits).

Now, your input strings have the 100 and 400 at position num1[0] and num2[0], the third-rightmost position, since they have 3 digits.
40000 has 5 digits, so the resulting 4 should be put at the fifth-rightmost position in the result, which is position r[(r.Length) - (3+3-1)].
Since r.Length=num1.length+num2.length this is equal to r[0 + 0 + 1] or r[i + j + 1]

The main reason this looks so unfamiliar is because humans order the digits from right to left, starting with the lowest digits, while this algorithm starts with the highest digit.

The carry step afterwards is required because the first part of this algorithm will generate digits higher than 9, i.e the two last digits of the input 3 * 6 = 12, but the result will be put into the single rightmost position r[r.Length-1]

Upvotes: 3

Related Questions