Introduction
There is a fast division technique which makes use of the fact that, for example:
1 / (2^31 - 1) = 2^-31 + 2^-62 + 2^-93 + 2^-124 + …
(This fact can be proven by multiplying both sides by 2^31, then subtracting 1 from each side.) In this example, let's assume that we have a number R, that is less than (2^31 - 1) * 2^N, where N is the number of bit of the result (e.g. 8 or 16). As it happens, for an 8-bit result (i.e. R is a 39-bit number), it is only necessary to sum the first two terms. Suppose the 39-bits are:
0abcdefg hijklmno pqrstuvw xyzABCDE FGHIJKLM
Then the quotient is the upper 8 bits of:
However, the addition must be performed with the carry set, rather than clear.
8-bit implementation
- Enter with a number in R4 (highest byte) to R0 (lowest byte)
- The result is in the accumulator
- Note that R is overwritten!
ASL R3
LDA R4
ROL
SEC
PHA
ADC R0
PLA
BCC .1
INC R1
BNE .1
INC R2
BNE .1
INC R3
INC R3
BNE .1
ADC #0
.1
16-bit implementation
Likewise, for the 16-bit implementation, it is only necessary to sum the first two terms. In this case, R is a 47-bit number, so if the 47 bits are:
0abcdefg hijklmno pqrstuvw xyzABCDE FGHIJKLM NOPQRSTU
Then the quotient is the upper 16 bits of:
Again, the addition must be performed with the carry set, rather than clear.
- Enter with a number in R5 (highest byte) to R0 (lowest byte)
- The result is in R5 (high byte) and R4 (low byte)
- Note that R is overwritten!
ASL R3
ROL R4
ROL R5
SEC
LDA R4
ADC R0
LDA R5
ADC R1
BCC .1
INC R2
BNE .1
INC R3
INC R3
BNE .1
INC R4
BNE .1
INC R5
.1
