(16 bit division), Fast divide by 10

Entry posted by Omegamatrix May 27, 2014

3,276 views

I took a stab at making a 16 bit division routine tonight. I took the approach of dividing the high and low bytes separately, since I have already written a bunch of 8 bit division routines. I then corrected the result with a couple of small look up tables.

This is the 16 bit routine I came up with. At 111 cycles max, and 96 bytes total it's not too bad.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;    UNSIGNED DIVIDE BY 10 (16 BIT)
;    111 cycles (max), 96 bytes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
TensRemaining:
    .byte 0,25,51,76,102,128,153,179,204,230
ModRemaing:
    .byte 0,6,2,8,4,0,6,2,8,4
.overflowFound:
    cmp    #4                    ;2  @74  We have overflowed, but we can apply a shortcut.
    lda    #25                   ;2  @76  Divide by 10 will be at least 25, and the
    bne    .finishLowTen         ;3  @79  carry is set when higher for the next addition.                                 ; always branch
.startBigDivide:
    lda    counterHigh           ;3  @3
    sta    temp                  ;3  @6
    lsr                          ;2  @8
    adc    #13                   ;2  @10
    adc    temp                  ;3  @13
    ror                          ;2  @15
    lsr                          ;2  @17
    lsr                          ;2  @19
    adc    temp                  ;3  @22
    ror                          ;2  @24
    adc    temp                  ;3  @27
    ror                          ;2  @29
    lsr                          ;2  @31
    and    #$7C                  ;2  @33   AND'ing here...
    sta    temp                  ;3  @36   and saving result as highTen (times 4)
    lsr                          ;2  @38
    lsr                          ;2  @40
    sta    highTen               ;3  @43
    adc    temp                  ;3  @46   highTen (times 5)
    asl                          ;2  @48   highTen (times 10)
    sbc    counterHigh           ;3  @51
    eor    #$FF                  ;2  @53
    tay                          ;2  @55   mod 10 result!
    lda    TensRemaining,Y       ;4  @59   Fill the low byte with the tens it should
    sta    lowTen                ;3  @62   have at this point from the high byte divide.
    lda    counterLow            ;3  @65
    adc    ModRemaing,Y          ;4  @69
    bcs    .overflowFound        ;2³ @71/72
    sta    temp                  ;3  @74
    lsr                          ;2  @76
    adc    #13                   ;2  @78
    adc    temp                  ;3  @81
    ror                          ;2  @83
    lsr                          ;2  @85
    lsr                          ;2  @87
    adc    temp                  ;3  @90
    ror                          ;2  @92
    adc    temp                  ;3  @95
    ror                          ;2  @97
    lsr                          ;2  @99
    lsr                          ;2  @101
    lsr                          ;2  @103
    clc                          ;2  @105
.finishLowTen:
    adc    lowTen                ;3  @108
    sta    lowTen                ;3  @111

There is a verification program and source code below. It rom has a black screen for a few seconds before displaying PASS.

div10_16bit(rev2).zip

Here is a second version of the divide by ten. It takes 126 cycles, but uses only 79 bytes. So you can choose whatever routine is best. Code for it is below.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;    UNSIGNED DIVIDE BY 10 (16 BIT)
;    126 cycles (max), 79 bytes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
TensRemaining:
    .byte 0,25,51,76,102,128,153,179,204,230
ModRemaing:
    .byte 0,6,2,8,4,0,6,2,8,4
.startBigDivide:
    ldy    #-2                   ;2  @2   skips a branch the first time through
    lda    counterHigh           ;3  @5
.do8bitDiv:
    sta    temp                  ;3  @8
    lsr                          ;2  @10
    adc    #13                   ;2  @12
    adc    temp                  ;3  @15
    ror                          ;2  @17
    lsr                          ;2  @19
    lsr                          ;2  @21
    adc    temp                  ;3  @24
    ror                          ;2  @26
    adc    temp                  ;3  @29
    ror                          ;2  @31
    lsr                          ;2  @33
    and    #$7C                  ;2  @35   AND'ing here...
    sta    temp                  ;3  @38   and saving result as highTen (times 4)
    lsr                          ;2  @40
    lsr                          ;2  @42
    iny                          ;2  @44
    bpl    .finishLowTen         ;2³ @46/47...120
    sta    highTen               ;3  @49
    adc    temp                  ;3  @52   highTen (times 5)
    asl                          ;2  @54   highTen (times 10)
    sbc    counterHigh           ;3  @57
    eor    #$FF                  ;2  @59
    tay                          ;2  @61   mod 10 result!
    lda    TensRemaining,Y       ;4  @65   Fill the low byte with the tens it should
    sta    lowTen                ;3  @68   have at this point from the high byte divide.
    lda    counterLow            ;3  @71
    adc    ModRemaing,Y          ;4  @75
    bcc    .do8bitDiv            ;2³ @77/78
.overflowFound:
    cmp    #4                    ;2  @79   We have overflowed, but we can apply a shortcut.
    lda    #25                   ;2  @81   Divide by 10 will be at least 25, and the
                                 ;         carry is set when higher for the next addition..
finishLowTen:
    adc    lowTen                ;3  @123
    sta    lowTen                ;3  @126  routine ends at either 87 or 126 cycles