A Verilog Implementation of Combinational Multiplier based on Ancient Egyptian Algorithm

This algorithm is a combinational implementation of peasant algorithm. The peasant algorithm is based on an ancient Egyptian technique written in the seventh century B.C. by the scribe Ahmes1. Despite the inexistence of the base two’s concept, the algorithm is essentially the same as modern computers use to make fast multiplications. Sometimes, this algorithm is called Egyptian, sometimes is called Russian peasant algorithm.

Besides the pedagogic effectiveness of concrete constructions, and equally correct, as a friend of me did in this blog post, I dislike them. It’s just cosmetics, but I didn’t found in the internet no algebraic deduction of the algorithm, maybe because the correct conclusion is trivial.

Despite of being an easy proof. In this article I gonna show the process step by step and entirely based on pure algebra. First I would demonstrate the correctness of the algorithm itself. Later I gonna show an implementation using verilog.

The ancient algorithm and its proof

The ancient algorithm is known as duplation mediation algorithm, that is, one of the terms of multiplication is divided successively and the other therm is multiplied successively by a base $ b $ Making this base equals 2 we have the following table:

$ p $ $ q $ $ q \operatorname{mod} 2 $
$ p\cdot 2 $ $ \lfloor q/2 \rfloor $ $ \lfloor q/2 \rfloor \operatorname{mod} 2 $
$ (p\cdot 2) \cdot 2 $ $ \lfloor \lfloor q/2 \rfloor / 2 \rfloor $ $ \lfloor \lfloor q/2 \rfloor / 2 \rfloor \operatorname{mod} 2 $
$ \vdots $ $ \vdots $ $ \vdots $
$ p\cdot 2^n $ $ \lfloor q/2^n \rfloor $ $ \lfloor q/2^n \rfloor \operatorname{mod} 2 $

The method states that

$$ p \cdot q = \sum_{i=0}^{n} p \cdot ( \lfloor q/2^i \rfloor \operatorname{mod} 2)\cdot 2^i \label{eq:1} $$

where $ n \leq \operatorname{ceil}(\log_2(q)) $

Let’s see the method in action. We have the product $ 33\cdot 12 $ The corresponding table is:

i $ p\cdot 2^i $ $ \lfloor q/2^i \rfloor $ $ \lfloor q/2^i \rfloor \operatorname{mod} 2 $ $ p \cdot (\lfloor q/2^i \rfloor \operatorname{mod} 2) $
0 33 12 0 0
1 66 6 0 0
2 132 3 1 132
3 264 1 1 264
4 528 0 0 0
$ p\cdot q $ 396
$ \sum_{i=0}^{n} p \cdot 2^i \cdot ( \lfloor q/2^i \rfloor \operatorname{mod} 2) $ 396

Now we have a strong clue of the method correctness. But we shall support the correctness in a strong algebraic proof. Using the first equation as a base to our theorem we should deduce the equality between right and left side expressions for all naturals. In this direction, we should state that there is some valid algebraic manipulation that could bring one side of equality to the other.

We know that any $ q \in \mathbb{N} $ can be represented as the following series 2 3

$$ q = \sum_{i=0}^{n=\lceil \log_b(q) \rceil }q_i\cdot b^i $$

$$ q_i= \lfloor q/b^i \rfloor \operatorname{mod} b $$

$$ q = \sum_{i=0}^{n=\lceil \log_b(q) \rceil }\lfloor q/b^i \rfloor \operatorname{mod} b\cdot b^i \label{eq:2} $$

if we multiply both sides of the above equation by $ p $ we have

$$ p \cdot q = \sum_{i=0}^{n=\lceil \log_b(q) \rceil } p \cdot \lfloor q/b^i \rfloor \operatorname{mod} b\cdot b^i \label{eq:3} $$

making $ b=2 $ and rearranging the equation above we have

$$ p \cdot q = \sum_{i=0}^{n=\lceil \log_b(q) \rceil } p \cdot ( \lfloor q/2^i \rfloor \operatorname{mod} )\cdot 2^i $$

the same result as the first equation.

The verilog implementation

Found a solid algebraic foundation to the peasant algorithm we now know that it is correct for all naturals. Based on this, we now can build a Verilog module that implements this algorithm.

module mult
#( parameter SIZE=8 )
(
    input reg [SIZE-1:0] a,
    input reg [SIZE-1:0] b,
    output [SIZE-1:0] y,
    output v
);

genvar i;

reg [2*SIZE-1:0] a_ = 0;
reg [2*SIZE-1:0] b_ = 0;
reg [2*SIZE-1:0] y_;

always@( a or b )
begin

    y_ = 0;
    a_[SIZE-1:0] = a;
    b_[SIZE-1:0] = b;
    v = 0;

    for (i=0;i < SIZE; i = i + 1) begin
        y_ = y_ + ((a_[i])?(b_ << i):0);
    end

    for (i=0; i < SIZE; i = i + 1) begin
        v = v | y_[SIZE+i];
    end

    if (v)
        y = 0;
    else
        y[SIZE-1:0] = y_[SIZE-1:0];

end

endmodule
comments powered by Disqus