Multiplying two numbers represented as strings

Question

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?

Answer 1

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]