Is it possible to multiply using ONLY shift and rotate?

Question

I found this thread on multiplying using shift and add, and I know how to make it work. But is it possible to multiply using only Shift and Rotate.

As long as you're only multiplying by a power of 2, yes. – lurker Apr 14 '16 at 01:14 — lurker, Apr 14 '16 at 01:14

Magoo · Accepted Answer · 2016-04-14T09:07:11.510

Very vague.

If you mean "without add and subtract" then yes.

If you have a register containing only 1s and another containing only zeroes, then (intel) RCR will allow you to set the cary flag to 1 or 0.

So - if you use sth like (BH=FF BL=0); want to add DH to DL

  rcr DL,1     ;DL0 to carry
  jc  DL1      ;it was a 1
  rcr DH,1     ;DH0 to carry
;CY now has result DL0=0 + DH0=0=00; DL0=0 + DH0=1=01
  rcr CL,1     ;CY to CL7
  rcr BL,1     ;0 to CY, BL unchanged
  rcl CL,1     ;CL0=0, CY=0 or 1
  rcl CL,1     ;CL01=00 or 01
  jmp done1    ;finished adding
DL1:
  rcr DH,1     ;DH0 to carry. DL0 was 1, so result=10 if CY set, 01 if not
  jc  DHDL10   ;result is 10
  rcl CL,1     ;CL0=0
  rcr BH,1     ;1 to CY, BH unchanged
  rcl CL,1     ;CL0=01
  jmp done1    ;finished adding
DHDL10:
  rcl CL,1     ;CL0=1
  rcr BL,1     ;0 to CY, BL unchanged
  rcl CL,1     ;CL01=10
done1:

This routine should add the lowest bits of DL and DH, giving the lowest 2 bits of CL.

From there, you could call this to add 2 registers together - it's just a matter of repeating the shift-and-add. (I'm not saying that this would be pleasant, just it could be done if you were sufficiently determined)

Since you can add 2 numbers together, you can add any number of numbers together and multiplying is simply a matter of adding register1 lots of register2.

Therefore, it's possible. Tedious, but possible.

after some thinks...

given again (BH=FF BL=0); want to add DH to DL

  rcr DL,1      ;DL0 to CY
  jc  DL1
DL0:
  rcr DL,1    
  jc  DL01
DL00:
  ...
DL01:
  rcr DL,1    
  jc  DL011
DL010:
 ...
DL01000000:
  rcr DH,1    
  jc  DL01000000H1
DL01000000H0:
  rcr DH,1    
  jc  DL01000000H01
 ...
DL00010000H00100000:   ;8*4=32 - note bit-order reversed dur RCR, RCL = conventional
; all we need here is to use BH/BL and RCR to build result.
 ...

So - here's a long, complicated, tedious way of simply creating a 256*256 list of possible results, mechanically evaluating each possible pair of input values BUT only using two instructions. Probably need a computer to write it for you...

If *all* you had was "shift" and "rotate" i don't think you would succeed. You need at least a full complement of boolean logic, e.g., not + and (or just nand, etc.) You are doing "and" by doing sequential test and jump, and you can get not by "jmp not condition". That's OK, but important to note in terms of success based on the explicit question asked by OP. Given a bunch of 8 bit registers, just RCL (or just RCR) and just JC, I suspect you have enough to be Turing capable. (add, compare, jump conditional is enough to do it). After that it is just arcane code :-} — Ira Baxter, Apr 14 '16 at 03:43
I already upvoted your answer once. Can't do it again, but a tip of the hat for carrying through on silly. I was only willing to write a comment :-} — Ira Baxter, Apr 14 '16 at 09:24

Is it possible to multiply using ONLY shift and rotate?

1 Answers1