Multiplication with PIC Assembly

Jan
25

I was programming a PIC microcontroller in assembly and noticed that it doesn't have a native multiply function. Being the adventurous programmer that I am, I decided to write my own. It is based on what is known as the Peasant multiplication algorithm.

Assuming X, Y, and ANS are defined bytes of memory, with X*Y ≤ 255 and ANS = 0, the following algorithm will multiply X and Y, storing the result in ANS.

MUL:        ; X * Y = ANS
            movlw   1
            subwf   X, w
            btfss   STATUS, C
            goto    END_MUL             ; while x >= 1
            btfss   X, 0                ;    if x is odd
            goto    END_MUL_IF
            movf    Y, w
            addwf   ANS, f              ;       ANS += Y
END_MUL_IF: bcf     STATUS, C           ;    clear carry
            rrf     X, f                ;    X >>= 1
            bcf     STATUS, C           ;    clear carry
            rlf     Y, f                ;    Y <<= 1
            goto    MUL
END_MUL:

How to Convert Floor Division to Ceiling Division

Jan
7

Today I found an elegant way to implement ceiling division.

Using Java, the following code results in an integer result of ceil(5/6):

int div = (int)Math.ceil(5 / (double)6);

A simpler, more elegant solution the doesn't require the Math library would be:

int div = (5 + 6 - 1) / 6;

Here's the solution generally:

int ceiling = (numerator + denominator - 1) / denominator;

However, one must be careful since there is a possibility here for an overflow. One way to prevent an overflow would be to use long instead of int.

On a related note, to convert floor division to rounding division, you can use the following:

int rounded = (numerator + denominator / 2) / denominator;

You may read more about this at its source.