# Unsigned Integer Division Routines

In general, multiplication in assembly is easy, and division is a bitch. There are three basic approaches to doing division. The first is to just do a loop in which the divisor is continually subtracted:

lda dividendValue ldx #0 sec.loopDivideBySeven inx sbc #7 bcs .loopDivideBySeven

The advantage to this approach is that it takes very few bytes. On the other hand when the dividend is large lots of loops get taken, and each loop piles on the cycles. The completion time is variable, which for the 2600 usually means you have to figure out a worse case execution time to prevent unwanted scanline bounces.

A second approach is to use look up tables:

ldy dividendValue lda DivideByFiveTable,Y;... code continuesDivideByFiveTable: .byte 0,0,0,0,0 ; 0-4 .byte 1,1,1,1,1 ; 5-9 .byte 2,2,2,2,2 ; 10-14 .byte 3,3,3,3,3 ; 15-19 .byte 4,4,4,4,4 ; 20-24 .byte 5,5,5,5,5 ; 25-29 .byte 6,6,6,6,6 ; 30-34

This approach is the fastest way possible, aside from a trivial divide by "powers of two" case. The disadvantage... you use up gobs and gobs of rom if you want to cover a lot of values. Sometimes if feels like you have no choice when the cycles are tight, but there are usually other places to shave cycles.

These first two basic approaches seem at extremes to each other. In between these are the "hybrid" approaches, where you divide a little, and then follow up with a small look-up table, as demonstrated by Supercat.

The third approach is to use reciprocal multiplication. I became interested in doing these so called "fast" division routines a few years ago. The first thing the reader has to know is that these are not necessarily the "fastest" (tables are always faster), but are generally a good compromise in terms of bytes and cycles to the first two basic approaches. Here are some of the routines I have found. They cover divisors 2 to 32, are all constant cycle routines, and don't use X or Y registers. They are good for any value, 0 to 255.

New! The file below is now updated with some better routines.

- 4

## 12 Comments

## Recommended Comments