Multiplication by the method of Russian peasants
Sometimes this method is called “peasant multiplication”, sometimes “ancient Egyptian”, sometimes “Ethiopian”, sometimes “multiplication through doubling and dividing in half”. It is well known to some, incomprehensible to some, but at the same time it is quite useful and can be used not only for multiplication, but also for raising to a power and calculating matrices.
Let's write two multiplied numbers side by side - they will become the headings of two columns. The third column will contain an increasing amount.
If the number in the left column is odd, we add the number from the right column to the increasing amount. Initially, it will be zero.
')
Then in the left column below we write the number from the header, divided in half (with a drop of the remainder). 13/2 = 6. And in the second column we write a number equal to doubling the column header, 19 * 2 = 38.
Since the number in the left column is even, we do not increase the increasing amount.
Then we repeat the process of dividing by two and doubling. The left column will be 3, this number is odd, so we add to 19 76 and get 95.
Repeating the procedure, we get as a result of 247.
Check:
The average between 13 and 19 will be 16
16 ^ 2 = 256
16 - 13 = 3
3 ^ 2 = 9
256 - 9 = 247
If you do not finish the algorithm, there will be solid zeros in the left column, and since 0 is an even number, you will not need to add anything to the increasing amount. Therefore, as soon as we get one in the left column, the answer appears in the third column.
Why does this work? We can say that this is the usual binary long multiplication. But we will give a longer explanation, which will be at the same time more general.
Denote the number in the left column of A, in the second - B, the increasing amount - R, and the answer - P. Therefore
(A * B) + R = P
Then, if A is even, that is, k, for which A = 2k. Rewrite the equation:
(2k * B) + R = P
Or, which is the same:
(k * 2B) + R = P
If we replace A with half its value, and B with double value, and call them A 'and B', then:
(A '* B') + R = P
That is, if A is even, we will half the first number and double the second, and our equation is correct. And if the odd? Then A = 2k + 1
A * B + R = P
(2k + 1) * B + R = P
2k * B + B + R = P
2k * B + (B + R) = P
K * 2B + (B + R) = P
A '* B' + (B + R) = P
And again we denoted half A through A 'and doubled B through B'.
Our equation is correct if we:
It can be seen that our equation remains balanced when performing the steps of our algorithm.
When we reach zero, we have:
0 * B + R = P
Or R = P. Our increasing amount is equal to the desired result.
Let's try to calculate 2 13 . When raising to a power, we multiply the numbers, rather than add, so we will refine our algorithm:
replace addition by multiplication
replace doubling by squaring
The growing product starts from 1. 13 is an odd one, so we multiply the second column by the growing product, getting 2. Now we will half the number 13 and put 2 in the square.
6 - even, do not multiply the incremental product. We halved 6 and squared 4, we get 16.
3 - odd, multiply 16 by our increasing product, we get 32. We halve the first column and square the second one.
Last step: 1 - odd, multiply 256 by 32, we get 8192, which is the answer.
The proof of this algorithm is the same as that of the past, now our equation just looks like this:
B A * R = E
But this algorithm can be used not only to raise numbers to a power, it also works for matrices. Our growing work begins with the identity matrix, and the matrix is written to the second column, whose degree we need to get. And it works.
Next comes a function written in Python. It works for any non-negative degree, and "base" of any type that supports associative multiplication. In other words, it works for any collection with multiplication that is a monoid .
This does not even need to be understood, it is enough to know that it works for matrices.
Links
Algorithm
13 x 19 -> 0 6 38 19 3 76 -> 1 152 -> 95 0 304 247 ^^^ Let's write two multiplied numbers side by side - they will become the headings of two columns. The third column will contain an increasing amount.
If the number in the left column is odd, we add the number from the right column to the increasing amount. Initially, it will be zero.
')
Then in the left column below we write the number from the header, divided in half (with a drop of the remainder). 13/2 = 6. And in the second column we write a number equal to doubling the column header, 19 * 2 = 38.
Since the number in the left column is even, we do not increase the increasing amount.
Then we repeat the process of dividing by two and doubling. The left column will be 3, this number is odd, so we add to 19 76 and get 95.
Repeating the procedure, we get as a result of 247.
Check:
The average between 13 and 19 will be 16
16 ^ 2 = 256
16 - 13 = 3
3 ^ 2 = 9
256 - 9 = 247
If you do not finish the algorithm, there will be solid zeros in the left column, and since 0 is an even number, you will not need to add anything to the increasing amount. Therefore, as soon as we get one in the left column, the answer appears in the third column.
Evidence
Why does this work? We can say that this is the usual binary long multiplication. But we will give a longer explanation, which will be at the same time more general.
Denote the number in the left column of A, in the second - B, the increasing amount - R, and the answer - P. Therefore
(A * B) + R = P
Then, if A is even, that is, k, for which A = 2k. Rewrite the equation:
(2k * B) + R = P
Or, which is the same:
(k * 2B) + R = P
If we replace A with half its value, and B with double value, and call them A 'and B', then:
(A '* B') + R = P
That is, if A is even, we will half the first number and double the second, and our equation is correct. And if the odd? Then A = 2k + 1
A * B + R = P
(2k + 1) * B + R = P
2k * B + B + R = P
2k * B + (B + R) = P
K * 2B + (B + R) = P
A '* B' + (B + R) = P
And again we denoted half A through A 'and doubled B through B'.
Our equation is correct if we:
- added a number from the second column to the increasing amount
- halved the first column
- doubled second
It can be seen that our equation remains balanced when performing the steps of our algorithm.
When we reach zero, we have:
0 * B + R = P
Or R = P. Our increasing amount is equal to the desired result.
Generalization 1: exponentiation
Let's try to calculate 2 13 . When raising to a power, we multiply the numbers, rather than add, so we will refine our algorithm:
replace addition by multiplication
replace doubling by squaring
====== ==== 13 2 -> 1 6 4 2 3 16 -> 1 256 -> 32 0 65546 8192 ^^^^ The growing product starts from 1. 13 is an odd one, so we multiply the second column by the growing product, getting 2. Now we will half the number 13 and put 2 in the square.
6 - even, do not multiply the incremental product. We halved 6 and squared 4, we get 16.
3 - odd, multiply 16 by our increasing product, we get 32. We halve the first column and square the second one.
Last step: 1 - odd, multiply 256 by 32, we get 8192, which is the answer.
The proof of this algorithm is the same as that of the past, now our equation just looks like this:
B A * R = E
Generalization 2: matrices
But this algorithm can be used not only to raise numbers to a power, it also works for matrices. Our growing work begins with the identity matrix, and the matrix is written to the second column, whose degree we need to get. And it works.
Next comes a function written in Python. It works for any non-negative degree, and "base" of any type that supports associative multiplication. In other words, it works for any collection with multiplication that is a monoid .
def fast_exp(b,e,I=1): # b^e, e – . # I, # , result = I while e > 0: if is_odd(e): result *= b b *= b e = e / 2 return result This does not even need to be understood, it is enough to know that it works for matrices.
Links
Source: https://habr.com/ru/post/273525/
All Articles