"E_net4" said: Huh, calculate in string? It'd be great, but still, how? For the slow and memory intensive (but easy to explain) version, textbook multiplication.
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[0] = 6, a[1] = 7, a[2] = 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):
for (i=0;j<m){ for (j=0;j<n){ result = a[j]*b[i] c[m][m+n] += result % 10 c[m][m+n+1] += result / 10 } }
for (i=0;i<m+n+1){ result = 0 for(j=0;j<m){ 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.
|