How a multiplier circuit could be implemented in JavaScript

TBH I have a hard time understanding the logic gate diagrams because I haven't yet fully understood the low-level electronics equipment and how that all works.

I have had a little bit of experience learning about basic logic gates and after watching a few videos and thinking about it a lot I can understand it for a few minutes before it slips away.

But then I saw some examples of "logic gates" "implemented" in software and it made much more sense what's going on. For example, here.

Then I even was able to go further and understand how a full adder works, as in here:

function fullAdder(a,b,c){
  return {
    c:or(and(xor(a,b),c), and(a,b)), // C is the carry
    s:xor(xor(a,b),c) // S is the sum
  };
}

That's pretty basic compared to the logic diagrams.

Now I would like to understand how multiplication and division are implemented in logic gates, such as like x86's MUL operator.

function MUL(a,b){
  return {
    ...
  };
}

I don't know really where to begin though other than dedicating some serious time to understanding a multiplier circuit and trying to translate that into perhaps a NAND gate implementation using the examples above. Wondering if one who knows this already can demonstrate the implementation in JavaScript.

Solution

Multiplication relies of the way numbers are encoded in binary. If A is unsigned and coded by bits a_n-1,a_n-2,...,a_1,a_0, its value is
A=a_n-1*2^n-1+a_n-2*2^n-2+...+a_1*2^1+a_0

So to multiply A×B, you have to do
A×B=A×(b_n-1*2^n-1+b_n-2*2^n-2+...+b_1*2^1+b_0)
= A×b_n-1*2^n-1+A×b_n-2*2^n-2+...+A×b_1*2^1+A×b_0
and multiplication is just a big addition where every term A×b_i*2^i is either A×2^i if b_i==1 or 0 if b_i==0

Here is an implementation in C


int mult(unsigned short A, unsigned short B){
  int res=0;
  int mask=0x1;
  for(int i=0; i<16;i++,mask<<=1){
    if(B&mask)
      res += (A << i);
  }
  return res;
}

The test on b_i can be replaced by an 'and' gate.

int mult(unsigned short A, unsigned short B){
  int res=0;
  int mask=0x1;
  for(int i=0; i<16;i++,mask<<=1){
     res += (A&~(((B&mask)>>i) -1))<<i;
  }
  return res;
}

This fancy expression extracts ith bit of B (B&mask), puts it at LSB (>>i), substracts 1, so that we have a 1-1=0 it bit is 1 and a -1=0xffffffff otherwise. We just have to complement and to do the "and" with A to get either A or 0 depending on ith bit. Fortunately, things are easier in hardware. It is sufficient to duplicate bit b_i of B and to do an "and" with every bit of A.

To simplify hardware, the variable shift of A<<i can be replaced by a 1 bit left shift of A at every step (A=A<<1). And a similar modification can be done for b_i extraction in such a way that we always consider the LSB of B.

int mult(unsigned short A, unsigned short B){
  int res=0;
  int mask=0x1;
  for(int i=0; i<16;i++){
     res += A&~((B&mask) -1);
     A <<= 1;
     B >>= 1;
  }
  return res;
}

This is more or less how a simple multiplier looks in hardware, once the loop is unrolled. You can implement it in js and replace the + by an adder done with gates and use simulated "and" gates.

Actually, hardware multipliers are a bit more complex.

they use a special adder without carry propagation to reduce addition time (carry save addition). This requires an extra addition at the end of the computation
they frequently use base 4 to reduce the number of adding steps (modified Booth algorithm).
they are pipelined to improve throughput

BTW, you may be interested by this online simulator of the different computer arithmetic algorithms.