Fast multiplication for PICs

The allround preferred programmable micro-controller for small custom-electronics is the well known PIC16F84. It has found its successor in the PIC 16F628.

These chips are based on the RISC-technology, which of course requires a lot of programming knowledge if higher functions should be implemented. Sometimes you need to operate multiplying or division. There exist many ways to do these operations. The question only is about speed and memory allocation.

The multiplication that we propose here is a fast and remarkably short solution to the problem.

The algorithm is based on a particularity of binary notation.

Imagine the multiplying of the numbers x10 = 7  and y10 = 5

x2 = 111

y2 = 101, which signifies y10 = 1*22 + 0*21 + 1*20 = 1*1002 + 0*102 + 1*12

the distributive rule gives us:

111 * 101 = 111 * (1*100 + 0*10 + 1*1) = 111*(1*100) + 111*(0*10) + 111*(1*1)

the associative and commutative rules give us:

= (111*100)*1 + (111*10)*0 + (111*1)*1

In binary notation, multiplying by factors of 2 is equivalent to shifting the number:

= 11100*1 + 1110*0 + 111*1

= 11100 + 111 = 100011 = 3510

Thus a simple algorithm may be written for multiplication:

' operate the muliplication  z = x * y

z := 0
while y <> 0 do
is the least significant bit of y 1 ?
 yes: z := z + x no: continue
shift x one digit to the left
shift y one digit to the right

Let's now analyze the function MULV8 which may be accessed from within a program by preparing the temporary variables TEMPX and TEMPY, calling the function and finally retrieving the product from the variable RESULT

For example,

we want our program to compute:

z := x * y

In PIC-assembler this will sound:

 MOVF   x,W          MOVWF  TEMPX          MOVF   y,W          MOVWF  TEMPY          CALL   MULV8          MOVF   RESULT,W          MOVWF  z

Suppose we have z := 27 * 7    (= 189)

expressed in binary notation:  z := b'00011011' * b'00000111'

here is what the computer will do:

to those not too familiar with PIC-assembler, we translate the code :

clrf  means 'clear file' (in PIC-language a file is an 8-bit register)

movlw 'fill accumulator with litteral value'

movwf 'transfer value from accumulator to file'

movf 'transfer value from file to itself (F) or the accumulator (W)'

btfsc means 'skip next instruction if the designed bit is clear')

bcf 'bit clear at file' Status,C = CLEAR THE CARRY-FLAG

rrf 'rotate right file and store it to itself or the accumulator'

rlf 'rotate left file and store...'

btfss 'skip next instruction if designed bit is set' Status,Z = ZERO-FLAG SET?

 LINE TEMPX TEMPY RESULT W ZERO-BIT CARRY-BIT CLRF RESULT 00011011 00000111 0 ? ? ? MOVF TEMPX,W 00011011 00000111 0 00011011 0 ? BTFSC TEMPY,0 00011011 00000111 0 00011011 0 ? ADDWF RESULT 00011011 00000111 00011011 00011011 0 0 BCF  STATUS,C 00011011 00000111 00011011 00011011 0 0 RRF  TEMPY,F 00011011 00000011 00011011 00011011 0 1 BCF STATUS,C 00011011 00000011 00011011 00011011 0 0 RLF  TEMPX,F 00110110 00000011 00011011 00011011 0 0 MOVF TEMPY,F 00110110 00000011 00011011 00011011 0 0 BTFSS STATUS,Z 00110110 00000011 00011011 00011011 0 0 next loop MOVF TEMPX,W 00110110 00000111 00011011 00110110 0 0 BTFSC TEMPY,0 00110110 00000011 00011011 00110110 0 0 ADDWF RESULT 00110110 00000111 01010001 00110110 0 0 BCF  STATUS,C 00110110 00000111 01010001 00110110 0 0 RRF  TEMPY,F 00110110 00000001 01010001 00110110 0 1 BCF STATUS,C 00110110 00000001 01010001 00110110 0 0 RLF  TEMPX,F 01101100 00000001 01010001 00110110 0 0 MOVF TEMPY,F 01101100 00000001 01010001 00110110 0 0 BTFSS STATUS,Z 01101100 00000001 01010001 00110110 0 0 next loop MOVF TEMPX,W 01101100 00000001 01010001 01101100 0 0 BTFSC TEMPY,0 01101100 00000001 01010001 01101100 0 0 ADDWF RESULT 01101100 00000001 10111101 01101100 0 0 BCF STATUS,C 01101100 00000001 10111101 01101100 0 0 RRF TEMPY,F 01101100 00000000 10111101 01101100 0 1 BCF STATUS,C 01101100 00000000 10111101 01101100 0 0 RLF TEMPX,F 11011000 00000000 10111101 01101100 0 0 MOVF TEMPY,F 11011000 00000000 10111101 01101100 1 0 RETURN =189

Here the functions for 8 and 16-bits: (Author: Claude Baumann 2002; updated 2006 thanks to L. Armstrong)

 MULV8                       CLRF RESULT MULU8LOOP                       MOVF TEMPX,W                       BTFSC TEMPY,0                       ADDWF RESULT                       BCF STATUS,C                       RRF TEMPY,F                       BCF STATUS,C                       RLF TEMPX,F                       MOVF TEMPY,F                       BTFSS STATUS,Z                       GOTO MULU8LOOP                       RETURN ADD16                        MOVF TEMPX16,W                        ADDWF RESULT16                        BTFSC STATUS,C                        INCF RESULT16_H                        MOVF TEMPX16_H,W                        ADDWF RESULT16_H                        RETURN MULV16                         CLRF RESULT16                        CLRF RESULT16_H MULU16LOOP                         BTFSC TEMPY16,0                         CALL ADD16                         BCF STATUS,C                         RRF TEMPY16_H,F                         RRF TEMPY16,F                         BCF STATUS,C                         RLF TEMPX16,F                         RLF TEMPX16_H,F                         MOVF TEMPY16,F                         BTFSS STATUS,Z                         GOTO MULU16LOOP                         MOVF TEMPY16_H,F                         BTFSS STATUS,Z                         GOTO MULU16LOOP                         RETURN

Note that these programs work for signed and unsigned variables.