Long multiplication: Difference between revisions
no edit summary
No edit summary |
|||
Line 550:
</lang>
=={{header|Mathematica}}==
We define the long multiplication function:
<lang Mathematica>
LongMultiplication[a_,b_]:=Module[{d1,d2},
d1=IntegerDigits[a]//Reverse;
d2=IntegerDigits[b]//Reverse;
Sum[d1[[i]]d2[[j]]*10^(i+j-2),{i,1,Length[d1]},{j,1,Length[d2]}]
]
</lang>
Example:
<lang Mathematica>
n1 = 2^64;
n2 = 2^64;
LongMultiplication[n1, n2]
</lang>
gives back:
<lang Mathematica>
340282366920938463463374607431768211456
</lang>
To check the speed difference between built-in multiplication (which is already arbitrary precision) we multiply two big numbers (2^8000 has '''2409''' digits!) and divide their timings:
<lang Mathematica>
n1=2^8000;
n2=2^8000;
Timing[LongMultiplication[n1,n2]][[1]]
Timing[n1 n2][[1]]
Floor[%%/%]
</lang>
gives back:
<lang Mathematica>
72.9686
7.*10^-6
10424088
</lang>
So our custom function takes about 73 second, the built-in function a couple of millionths of a second, so the long multiplication is about 10.5 million times slower! Mathematica uses Karatsuba multiplication for large integers, which is several magnitudes faster for really big numbers. Making it able to multiply <math>3^{(10^7)}\times3^{(10^7)}</math> in about a second; the final result has 9542426 digits; result omitted for obvious reasons.
=={{header|Perl}}==
| |||