5 Typo corrected

The cost of multiplying two $n$-digit numbers is of order $n^2$ (because each digit of the first number has to be multiplied with each digit of the second number).

A lot of information is found on http://en.wikipedia.org/wiki/Multiplication_algorithm .

The first faster (and easily understandable) algorithm was http://en.wikipedia.org/wiki/Karatsuba_algorithm with complexity $n^{log_2 3} \sim n^{1.585}$.

Basic idea: To multiply $x_1x_2$ and $y_1y_2$ where all letters refer to $n/2$-digit parts of $n$-digit numbers, calculate $x_1 \cdot y_1$, $x_2\cdot y_2$ and $(x_1+y_1)\cdot(x_2+y_2)$ (x_1+x_2)\cdot(y_1+y_2)$and note that this is sufficient to calculate the result with three such products instead of four. 4 added 2 characters in body The cost of multiplying two$n$-digit numbers is of order$n^2$(because each digit of the first number has to be multiplied with each digit of the second number). A lot of information is found on http://en.wikipedia.org/wiki/Multiplication_algorithm . The first faster (and easily understandable) algorithm was http://en.wikipedia.org/wiki/Karatsuba_algorithm with complexity$n^{log_2 3} \sim n^{1.585}$. Basic idea: To multiply$x_1x_2$and$y_1y_2$where all letters refer to$n/2$-digit parts of$n$-digit numbers, calculate$x_1 \cdot y_1$,$x_2\cdot y_2$and$(x_1+y_1)\cdot(x_2+y_2)$and note that this is sufficient to calculate the result with three such products instead of four. 3 added 447 characters in body The cost of multiplying two$n$-digit numbers is of order$n^2$(because each digit of the first number has to be multiplied with each digit of the second number). For Darij Grinberg: More A lot of information is found on http://en.wikipedia.org/wiki/Multiplication_algorithm . The first faster (and easily understandable) algorithm was http://en.wikipedia.org/wiki/Karatsuba_algorithm with complexity$n^{log_2 3} \sim n^{1.585}$. Basic idea: To multiply$x_1x_2$and$y_1y_2$where all letters refer to$n/2$-digit parts of$n$-digit numbers, calculate$x_1 \cdot y_1$,$x_2\cdot y_2$and$(x_1+y_1)\cdot(x_2+y_2)\$ and note that this is sufficient to calculate the result with three such products instead of four.

2 added 106 characters in body; deleted 4 characters in body