Multiplication of Long Integers
Faster than Long Multiplication
Here’s the start of the second part of the Algorithms Unplugged book which focuses on Arithemtic and Encryption.
Our First lesson in the second part talks about Multiplication and how to make this mathematical operation operate much faster than doing it with the traditional method of long multiplication.
I know that you probably forget how to multiply two long integers with your brain or with a pencil and paper because it’s something that most of us used to do when he was a kid whenever he starts using a calculator he begins to forget most of the mathematical operations he was doing by his brain and do it easily with a calculator.
But In this article, there are no more calculators we will start by explaining how long multiplication is done.
So let’s say we have 5678 and want to multiply it with 4321 how do you do it?
first, we will take the first digit from the right which is 1 and multiply it by all the digits in the first number we will get the following:
Then we will take 2 which is the second digit from the right and multiply it with all digits at the first number we will get the following:
This time we did extra work firstly we had to add an extra 0 as we are in the second digit and for the third digit we will add two zeros and so on.
total zeros to be added = (n-1) in which n represents the position of a digit
secondly, we had a reminder in the multiplication process which raised above the next digit so when multiplying 2x8 we get 16. we will write 6 and take 1 as a reminder to add it to the total of the next process which is 2x7 and we get 14 and add it to one which is our reminder we will get 15 so we will write 5 and take one as a reminder and so on.
At the last digit, we will have one as the remainder and 2x5 which is equal to 10 so our total will be 11 and it will be written as it is (there is no next digit to have the remainder) and the result will be 113560.
We will sum up all the results we will have from doing the same processes on the rest of the digits to get the total of our multiplication process as follows:
This is how we do the long multiplication no wonder that we prefer to use a calculator.
Anyway, even computers aren’t happy to solve a multiplication process in this way especially when talking about much bigger numbers than this 4-digit number and calculating large numbers is something that is used in many applications of computers such as encryption of communication on the internet.
So why computers aren’t happy well first you have to know that computer scientists don’t measure the effort needed to carry out an algorithm in seconds or minutes because such information will depend on the hardware, the programming language and the details of implementation.
Instead, they count the number of basic operations performed by an algorithm.
A computer can do a basic operation in a single step such as multiplying two numbers with one digit (e.g. 2x4=8).
In Long Multiplication what operations do we do?
First, we have to multiply each digit by all other digits we have so in our example of a 4-digit number we will have 2xn² basic operation which is equal to 2x4² = 32.
How do we get the Multiplication equation?
When multiply 4* 5678 (short multiplication) we will have 4 multiplication basic operations as we will multiply 4 with each number and we will have also 4 addition basic operations. The image below describe why we have 4 addition the right most digit which circled with yellow will not have any operation on it and will be copy directly to the result without any computing. The blue marks show the addition process we have we will add 3+8 then 2+4 then 2+0 and finally 2 + the remain if exist and counting them will result in 4 operations. Therefore, we have n(no. of digits) multiliplication basic opertains and also n addition basic operations so as total we will have n+n = 2n basic operations in every short multiplication process in the long multiplication. we have n multiplications n.2n will result 2n² which is represent all the basic operations for long multiplication.
Second, we have addition in our example we will have (n-1) x (2 x n) basic operations which equal 24 basic operations.
How do we get the addition equation?
n-1 represents the total of additions you will have as you can see we will first add 5678 + 113560 and the total will be added to the next number so we will have 119238 + 1703400 and then we will add the total of them to 2271000 from all of these we notice that we will do 3 long additions and if we have 5-digit number we will do 4 long additions so we get n-1.
2xn represents each addition basic operation which represents the short additions. we notice that in our example we have a 4-digit number but when added we will add an 8-digit number with another 8-digit number at the maximum case and this represent the number of basic operation we will have so we will get 8 basic operation on each addition.
Therefore the computer has to do 32+24 = 56 basic operations to multiply two 4-digit numbers. In such a small digit number you will say that it’s only 56 basic operations not too much to make the computer bothered but as we have mentioned computer used in some apps needs a multiplication of two numbers which has a really large number of digits.
So for example, if we have 100,000 digits we will have:
2x100,000² = 20000000000 for multiplication basic operations.
(100,000–1)x(2x100,000) = 19999800000 for addition basic operations.
Adding them together the total of basic operations will be nearly 40 billion. I think now you have the answer to why the computer has a problem with how long multiplication works.
Is there any substitute that we can use to make long multiplication have a less total number of basic operations?
Yes, there is a way called Kartsuba’s method, named after Russian mathematician Anatolii Alexeevitch Karatsuba who came up with its main idea.
Kartsuba’s method depends on the divide and conquer algorithm in which we depend on breaking down complex problems into small easy problems which can be solved faster and by solving all of them we will find that we solve the big complex problem.
In multiplication, we know that the easiest thing is the multiplication of two numbers consisting of one digit each (n = 1). Multiplying them needs a single basic operation, which immediately gives the result.
So if we have a multiplication of 2-digit numbers we will try to break it down to be the multiplication of one-digit numbers so it can be more easy to solve how we can do it?
Let’s describe it with this example say we have a = 78 and b = 21 and we want to multiply a with b. To make it one digit all we will have to do is split the number into two halves so 78 will be p=7 and q=8 and for 21 we will have r = 2 and s = 1.
Then we have to know the fact that if you have an n-digit number and you split it into two halves as we do above then you can get the original number before splitting from the two halves again by multiplying the first half with 10^n/2 and adding it to the second half. Using our example and this fact we will have two equations:
1- a = (p x 10¹) + q = 70 + 8 = 78
2- b = (r x 10¹) +s = 20 + 1 = 21
Therefore,
a x b = ((p x 10) + q) x ((r x 10) + s) = (p x 10 x r x 10) + (p x 10 x s) + (q x r x 10) + q x s = (p x r) x 100 + (p x s + q x r) x 10 + q x s
substituting p, r, q and s in the equation with the numbers in our example we will get the following equation: (7 · 2) · 100 + (7 · 1 + 8 · 2) · 10 + 8 · 1 which will be equal 1638 and we get the result of multiplying 78 with 21 by this equation.
We have 4 multiplications of one digit followed by additions and this is precisely what long multiplication does. But Kartusuba had an idea that enables us to multiply a 2-digit number a and b with just three multiplications of one-digit numbers. HOW?
By introducing the following 3 equations:
u = p × r,
v = (q − p) × (s − r),
w = q × s.
These three equation will help in multiplying a and b by the help of this formula:
u + w − v = p × r + q × s − (q − p) × (s − r) = p × s + q × r.
we can substitute u, v and u + w − v in the earlier equation we have which is (p x r) x 100 + (p x s + q x r) x 10 + q x s. After substituting, we will get the following equation:
a × b = u × 10² + (u + w − v) × 10 + w
By using three of Kartusuba’s equations in our example (21 x 78) we will have:
u=7×2= 14,
v = (8 − 7) × (1 − 2) = −1,
w =8×1= 8.
After getting the result of the three equations we will substitute it in the following equation:
a × b = u × 10² + (u + w − v) × 10 + w
78 × 21 = 14 × 100 + (14 + 8 − (−1)) × 10 + 8 = 1400 + 230 + 8 = 1638
We have used two subtractions of digits, three multiplications of digits, and
several additions and subtractions of digits to combine the results of the three multiplications.
So we decrease only from 4 to 3 multiplications when comparing with the long multiplication but this small difference only appears in small digits numbers if we go to large digit numbers we will see that there is a big difference in the number of basic operations between the 2 methods.
To prove that we have to know how Karatsuba’s Method works for any numbers of any length.
This is the equation of any digit length:
a = p × 10^n/2 + q
b = r × 10^n/2 + s
a × b = u × 10^n + (u + w − v) × 10^n/2 + w
The n in the above equations represents the number of digits. So in the first 4 digits example when we have 5678 x 4321 the equations will be:
5678 = 56 × 10² + 78
4321 = 43× 10² + 21
u = 56 × 43= 2408,
v = (78 − 56) × (21 − 43) = −484,
w = 78 × 21= 1638.5678 × 4321 = 2408 × 10⁴ + (2408 + 1638 − (−484)) × 10² + 1638 = 24080000 + 453000 + 1638
= 24534638.
In this calculation, we had to compute three auxiliary products of two-digit
numbers. we had already investigated how to do that with Karatsuba’s method, using only three multiplications of digits each time. This way,
we can compute the three auxiliary products using only 3 × 3 = 9 multiplications of digits and several additions and subtractions. The long multiplication would have taken 16 multiplications of digits and several additions.
Now we begin to notice a big change the difference was only 1 in 2-digit numbers but in 4-digit numbers, the difference becomes 7 and as the number of digits grows the difference between the two methods will grow.
NOTE:
Karatsuba’s method works for any number n of digits that is a power of 2 so it will be used with numbers which consist of 2-digit, 4-digit, 8-digit, 16-digit, 32-digit and so on.
If your number for example has only 3-digit then you will make it tends to the nearest one work with Karatsuba’s method which in this case will be the 4-digit number and you will make that by adding a number of zeroes that make it equal to 4-digit in this example so you will add only one zero from left (infront of number).
This leads to the following table which compares how many multiplications of digits are used by Karatsuba’s method, or by long
multiplication, respectively, to multiply numbers with n digits.
From The above table, you can see a big difference appears when increasing the number of digits between the Karatsuba and Long multiplication methods. Which makes Karatsuba’s Method has the advantage over Long multiplication.
That’s it I have explained to you the first lesson in the second part of The Algorithms Unplugged wait for more lessons to be explained next lesson will be The Euclidean Algorithm so stay tuned.
