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 x₁₀ = 7  and y₁₀ = 5

x₂ = 111

y₂ = 101, which signifies y₁₀ = 1*2² + 0*2¹ + 1*2⁰ = 1*100₂ + 0*10₂ + 1*1₂

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 = 35₁₀

Thus a simple algorithm may be written for multiplication:

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:

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?

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

Note that these programs work for signed and unsigned variables.

Main Page