"E_net4" said:For the slow and memory intensive (but easy to explain) version, textbook multiplication.
Huh, calculate in string?
It'd be great, but still, how?
Assume numbers num1 and num2, with 0 <= num1,num2 <= 2 147 483 647. Say num1 = 146576 and num2 = 46578643. Note that num1*num2 does not fit in a long. Split num1 and num2 in decimal representation in two arrays: a = 6, a = 7, a = 5, etc. If you wish to know the lengths of the arrays in advance, the log10 function is your friend. Let's say num1 has n digits and num2 has m digits ( here n=6, m=8 ).
Assign a 2D array c[m][m+n+1], fill it with zeros. The rows will hold the rows of the multiplication, the columns the digits. Also create an array d[m+n+1] to hold the final result, fill with zeros.
Calculation like this (note - pseudocode):
result = a[j]*b[i]
c[m][m+n] += result % 10
c[m][m+n+1] += result / 10
result = 0
result += c[j][i]
//if m could be strictly bigger than 11, you might need division by 100 and three cells here
d[i] += result % 10
d[i+1] += result / 10
Then make a string out of the digits in the array d.
Possible optimizations: don't split with tens but with 10000s (10000^2 should fit in a long). Don't waste space and time on all the zeros. Use binary notation and split on 2^16. Use a better method or a better language that natively supports this.