One could think of multiplication and division as repeated addition and subtraction respectively.
But when it comes to algorithms like long multiplication/division , how do we check their correctness ?
Are we assuming the correctness of such multiplication/division algorithm based on their correctness with smaller values ?
For eg: 12*10=120 , We could add 10, 12 times and verify it.
Consider numbers like this 489759 * 985681 = 482746140879 , Lets say someone came up with some other algorithm and produce some other result. How can one prove long multiplication method produced the correct result ,rather than adding 489759 , 985681 times.
Is there any formal way proof that assert the correctness ?
Best Answer
Our confidence in long multiplication comes from the fact that multiplication distributes with addition. In other words if $a = b + c$ then $ad = bd + cd$. The process of long multiplication works on this principal. I'll give an example of this to help show how it works.
Say we have $$\begin{equation}\begin{split} 11 \times 22 & = (10 + 1)(20 + 2) &\textrm{ Expand the numbers into addition } \\ & = 20(10 + 1) + 2(10 + 1) & \textrm{ Distribute the multiplication across the addition} \\ & = (20 \times 10) + (20 \times 1) + (2 \times 10) + (2 \times 1) & \textrm{ Distribute the multiplication across the inner addition } \\ & = 200 + 20 + 20 + 2 & \textrm{ Do the multiplications} \\ & = 242 & \textrm{ Do the additions} \end{split}\end{equation}$$
The algorithm you learn for long multiplication is a convenient way to keep track of you doing this. It also takes the further step of expanding a number like $ 489759 = (4 \times 100000) + (8 \times 10000) + (9 \times 1000) \dots$ this way you can reduce the mulitiplication into multiplications between single digits and between powers of ten.