Developers Club geek daily blog

2 years, 9 months ago
Sometimes this method call "country multiplication", sometimes "Ancient Egyptian", sometimes "Ethiopian", sometimes "multiplication through doubling and halving". Some it is well-known, some – is unclear, but at the same time it is rather useful and can be used not only for multiplication, but also for exponentiation and calculations of matrixes.

Algorithm


  13  x  19 ->     0
   6     38       19
   3     76 ->
   1    152 ->    95
   0    304      247
                 ^^^

Let's write two multiplied numbers nearby – they will become headings of two columns. The third column will contain the increasing sum.

If number in the left column odd, we add number from the right column to the increasing sum. Initially it will be equal to zero.

Then in the left column below we write number from heading, divided in half (with discarding of a remaining balance). 13 / 2 = 6. And in the second column we write the number equal to doubling of column heading, 19*2 = 38.

As number in the left column even, we do not increase the increasing sum.

Then we repeat fission process on two and doubling. In the left column will be 3, this odd number therefore we add to 19 76 and we receive 95.

Repeating procedure, we receive as a result 247.

Check:

The average between 13 and 19 will be 16
16 ^ 2 = 256
16 – 3 = 3
3 ^ 2 = 9
256 – 9 = 247

If not to finish work of algorithm, then in the left column there will be continuous zero and as 0 – an even number, it will be necessary to add nothing to the increasing sum. Therefore as soon as we receive unit in the left column, in the third column the answer appears.

Proof


Why it works? It is possible to tell that this normal binary long multiplication. But we will give longer explanation which will be at one also more general.

Let's designate number in the left column A, in the second – B, the increasing sum – R, and the answer – P. Therefore

(A*B) + R = P

Then, if A even, that is k, for which A=2k. Let's rewrite the equation:

(2k*B) + R = P

Or that the same:

(k*2B) + R = P

If we replace with A half of its value, and B – the doubled value, and we will call them A' and B', then:

(A' * B') + R = P

That is, if A even, we half the first and we will double the second, and our equation truly. And if 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 designated a half of A through A' and the doubled B through B'.

Our equation is right if we:
  • added number from the second column to the increasing sum
  • halfed the first column
  • doubled the second

It is visible that our equation remains balanced at execution of steps of our algorithm.

When we reach zero, we have:

0 * B + R = P

Or R=P. Our increasing sum is equal to the necessary result.

Generalization 1: exponentiation

Let's try to count 213. At exponentiation we multiply numbers, but we do not put therefore we will improve our algorithm:

let's replace addition with multiplication
let's replace doubling with squaring

степень   база
======   ====
  13      2 ->     1
   6      4        2
   3     16 ->
   1    256 ->    32
   0  65546     8192
                ^^^^

The accruing work begins with 1. 13 – odd therefore we multiply the second column by the accruing work, receiving 2. Now we will half 13 and we will square 2.

6 – even, we do not multiply the accruing work. Let's half 6 and we will square 4, we will receive 16.

3 – odd, we multiply 16 by our accruing work, we will receive 32. Let's half the first column and we will square the second.

Last step: 1 – odd, we multiply 256 on 32, we receive 8192, as is the answer.

The proof of this algorithm same, as well as at the past, just our equation looks now so:

BA*R=E

Generalization 2: matrixes

But this algorithm can be used not only for construction of numbers in degree – it works also for matrixes. Our accruing work begins with identity matrix, and the matrix whose degree we should receive is written to the second column. And everything works.

Further there is a function written in the Python language. It works for any non-negative degree, and "base" of any type supporting associative multiplication. In other words, it works for any collection with multiplication which is monoidy.

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

Even it is not necessary to understand it, it is enough know that it works for matrixes.

Links

This article is a translation of the original post at habrahabr.ru/post/273525/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus