After dealing with a rather less useful variety of division routines in "Attitude #7", we now discuss bitwise division, which is possibly the most practical method of performing this operation on a C-64.
BY KRILL/PLUSH
Alright, before looking at an actual bitwise division routine, let's first make a few preliminary considerations.
CONSIDERING IT
In a division, there is a dividend which is divided by a divisor to obtain the quotient. This quotient tells how often the divisor is contained in the dividend. Assume an 8-bit unsigned integer dividend and a divisor with the same properties. The quotient can at most be as big as the dividend, or it is smaller. As already mentioned, the quotient tells how often the divisor is contained in the dividend. It follows that every bit in the quotient tells how many times the divisor is contained in the dividend, which is as many as the bit's value is. For example, if bit 4 is set, the divisor is contained 2^4=16 times, or if bit 7 is set, 2^7=128 times. If both are set, it's 128+16=144 times.
MODE OF OPERATION OF A BITWISE DIVISION ROUTINE
A routine would go through each bit of the result and check if the divisor is contained as many times in the dividend as the bit's value. It starts with the most significant bit (why will be explained later), i.e. bit 7 in this case. The bit will be set if the divisor is contained at least 128 times in the dividend. If so, this 128-fold divisor is subtracted from the dividend, as it is already considered by setting bit 7 in the result. Then the next bit (#6 here) is processed, which is checking if the divisor is contained at least 64 times in the updated dividend and setting the result bit accordingly. Continue until having an arbitrarily accurate result. This can mean more than those bits on the left side of the comma, so as many decimal bits as required can be calculated. Some operations will yield infinitely many decimal bits (think 1 divided by 3), which means that an arbitrarily accurate routine will always have an error with these operations.
Now you can see why we start at the most significant bit: this way, the loop can be passed with increasing result accuracy, until enough bits, and possibly decimal bits, are obtained.
THE ROUTINE
As an illustration there is an actual small routine, which is of course pretty much unoptimized.
; store arguments:
STX dividend
STY divisorhi
; divisor*128 is 16 bits:
LDA #$00
STA divisorlo
STA result
; 8 bit result size:
LDX #$08
; halve the divisor:
loop LSR divisorhi
ROR divisorlo
SEC
; 16-bit subtraction:
LDA dividend
SBC divisorlo
TAY
LDA #$00
SBC divisorhi
; don't store new dividend
; if the old one is smaller
; than the divisor:
BCC zero
; store new dividend:
STY dividend
; store bits in the result:
zero ROL result
DEX
BNE loop
LDA result
This looks similar to a bitwise multiplication routine. The arguments are passed in the X and Y registers, and the result is returned in the accu. Please note that to obtain the 128-fold divisor prior to the actual division loop, the original divisor is not shifted seven bits to the left, but simply shifted one bit to the right and then, by redefining lo- and hibyte, multiplied by 256. But there is still much more room for improvement.
A FEW TIPS FOR OPTIMIZATION
Looking a bit closer at the routine, one can see that as long as the hibyte of the divisor is not 0, the corresponding bit in the accu will never be set. So one could put a smaller loop before the actual division loop, which halves the divisor until its hibyte becomes 0. The main loop would be shorter by as many passes this new preloop runs, and would also work without shifting right the divisor hibyte and subtracting the hibytes, since the hibytes are all 0 when entering the main loop. Note that when enhancing the routine to bigger argument or result size, these optimizations would be slighty less efficient.
WHAT TO KEEP IN MIND
The things to pay attention to are similar to those with bitwise multiplication. When working with signed numbers, first calculate with their absolute values and then set the result's sign according to the dividend's and divisor's signs. The result can have arbitrarily many decimal bits, and if the arguments have decimal bits, the result can be bigger than the dividend if the divisor is smaller than 1. When calculating with fractions, the result has as many integer bits as the routine allows - the result can be bigger than the arguments. Of course, a division by zero does not give a valid result - it will be a number with all bits set.
That's it for bitwise division. I omitted to detail the possibility of using tables to "calculate" the result, as this would work exactly like with multiplication or any other mathematical function.
The next part will discuss one of the fastest methods to divide on the C-64. See you there!
KRILL/PLUSH |