Software - Math - Fast Division

# 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
PLA
BCC .1
INC R1
BNE .1
INC R2
BNE .1
INC R3
INC R3
BNE .1
.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
LDA R5