Difference between revisions of "Programming:Integer Division"

From CPCWiki - THE Amstrad CPC encyclopedia!
Jump to: navigation, search
(16bit division)
(Fast 32bit division: a bit faster)
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
== 8bit division ==
 +
 +
'''Input:''' HL=Value1, C=Value2
 +
 +
'''Output:''' L=Value1/Value2, H=Value1 MOD Value2
 +
 +
'''Destroyed:''' AF,BC
 +
 +
<pre>
 +
        LD B,8
 +
Div_Next:
 +
        ADD    HL,HL
 +
        LD      A,H
 +
        SUB    C
 +
        JR      C,Div_NXTB
 +
        LD      H,A
 +
        INC    L
 +
Div_NXTB:
 +
        DJNZ    Div_Next
 +
        RET
 +
</pre>
 +
 
== 16bit division ==
 
== 16bit division ==
  
Line 92: Line 114:
  
 
'''Destroyed:''' AF,DE,IY
 
'''Destroyed:''' AF,DE,IY
 +
 +
'''CPC Cycles:''' approximately 7800, 1900 usec
 +
 +
'''Size:'''  91 bytes
  
 
<pre>
 
<pre>
Line 146: Line 172:
 
         ret            ;IY,BC=Value1 DIV Value2
 
         ret            ;IY,BC=Value1 DIV Value2
 
</pre>
 
</pre>
 +
 +
== Fast 32bit division ==
 +
 +
'''Input:''' HL,DE=Value1, BC=Value2
 +
 +
'''Output:''' BCDE=Value1/Value2, HL=Value1 MOD Value2
 +
 +
'''Destroyed:''' AF
 +
 +
'''Not used:''' IX, IY
 +
 +
'''CPC Cycles:''' 1016-2444 (1730 on average), 254-611 usec (432 on average)
 +
 +
'''Size:''' 277 bytes
 +
 +
<pre>
 +
div_r macro
 +
    local t2
 +
    SLA  E
 +
    RL    D
 +
    ADC  HL, HL
 +
 +
    LD    A, L
 +
    ADD  A, C
 +
    LD    A, H
 +
    ADC  A, B
 +
    JR    NC, t2
 +
 +
    ADD  HL, BC
 +
    INC  DE
 +
t2
 +
    endm
 +
div_e macro
 +
    local t1,t2
 +
    SLA  E
 +
    RL    D
 +
    ADC  HL, HL
 +
    JR    C, t1
 +
 +
    LD    A, L
 +
    ADD  A, C
 +
    LD    A, H
 +
    ADC  A, B
 +
    JR    NC, t2
 +
t1
 +
    ADD  HL, BC
 +
    INC  DE
 +
t2
 +
    endm
 +
div32x16 proc  ; BCDE = HLDE/BC, HL = HLDE%BC
 +
    local DIV16, DIV32R, DIV32E
 +
    DEC  BC
 +
    LD    A, B
 +
    CPL
 +
    LD    B, A
 +
    LD    A, C
 +
    CPL
 +
    LD    C, A
 +
    ADD  A, L
 +
    LD    A, B
 +
    ADC  A, H
 +
    JR    NC, DIV16
 +
 +
    PUSH  DE
 +
    EX    DE, HL
 +
    LD    HL, 0000
 +
    CALL  DIV32R
 +
    EX    DE, HL
 +
    EX    (SP), HL
 +
    EX    DE, HL
 +
    CALL  DIV32E
 +
    POP  BC
 +
    RET
 +
DIV16
 +
    CALL  DIV32E
 +
    LD    BC, 0000
 +
    RET
 +
DIV32R  ; DE = HLDE/(-BC), HL = HLDE%(-BC), -BC < $8000
 +
    CALL  $+3
 +
    rept 8
 +
    div_r
 +
    endm
 +
    RET
 +
DIV32E  ; DE = HLDE/(-BC), HL = HLDE%(-BC)
 +
    CALL  $+3
 +
    rept 8
 +
    div_e
 +
    endm
 +
    RET
 +
    endp
 +
</pre>
 +
 +
== Web links ==
 +
 +
* [http://www.smspower.org/Development/DivMod Division implementation for the Sega Master System]
 +
* [http://map.tni.nl/articles/mult_div_shifts.php Multiplications and divisions on the MSX Assembly Page]
 +
 
[[Category:Programming]]
 
[[Category:Programming]]

Latest revision as of 08:27, 26 December 2015

8bit division

Input: HL=Value1, C=Value2

Output: L=Value1/Value2, H=Value1 MOD Value2

Destroyed: AF,BC

        LD B,8
Div_Next:
        ADD     HL,HL
        LD      A,H
        SUB     C
        JR      C,Div_NXTB
        LD      H,A
        INC     L
Div_NXTB:
        DJNZ    Div_Next
        RET

16bit division

Input: BC=Value1, DE=Value2

Output: HL=Value1/Value2, DE=Value1 MOD Value2

Destroyed: AF,BC

clcd16  ld a,e
        or d
        ld hl,0
        ret z
        ld a,b
        ld b,16
clcd161 rl c
        rla
        adc hl,hl
        sbc hl,de
        jr nc,clcd162
        add hl,de
clcd162 ccf
        djnz clcd161
        ex de,hl
        rl c
        rla
        ld h,a
        ld l,c
        ret

24bit division

Input: A,BC=Value1, DE=Value2

Output: HL=Value1/Value2, DE=Value1 MOD Value2

Destroyed: AF,BC,IX,IYL

clcdiv  db #dd:ld l,e
        db #dd:ld h,d   ;IX=Value2
        ld e,a          ;E,BC=Value1(Counter)
        ld hl,0
        db #dd:ld a,l
        db #dd:or h
        ret z
        ld d,l          ;D,HL=CalcVar
        db #fd:ld l,24  ;IYL=Counter
clcdiv1 rl c
        rl b
        rl e
        rl l
        rl h
        rl d
        ld a,l
        db #dd:sub l
        ld l,a
        ld a,h
        db #dd:sbc h
        ld h,a
        ld a,d
        sbc 0
        ld d,a          ;D,HL=D,HL-IX
        jr nc,clcdiv2
        ld a,l
        db #dd:add l
        ld l,a
        ld a,h
        db #dd:adc h
        ld h,a
        ld a,d
        adc 0
        ld d,a
        scf
clcdiv2 ccf
        db #fd:dec l
        jr nz,clcdiv1
        ex de,hl        ;DE=Value1 MOD Value2
        rl c
        rl b
        ld l,c
        ld h,b          ;HL=Value1 DIV Value2
        ret

32bit division

Input: IY,BC=Value1, IX=Value2

Output: IY,BC=Value1/Value2, HL=Value1 MOD Value2

Destroyed: AF,DE,IY

CPC Cycles: approximately 7800, 1900 usec

Size: 91 bytes

clcd32c db 0
clcd32  ld hl,0
        db #dd:ld a,l
        db #dd:or h
        ret z           ;IY,BC=Value1(Counter)
        ld de,0         ;DE,HL=CalcVar
        ld a,32         ;Set Counter to 32
clcd321 ld (clcd32c),a
        rl c
        rl b
        db #fd:ld a,l:rla:db #fd:ld l,a
        db #fd:ld a,h:rla:db #fd:ld h,a
        rl l
        rl h
        rl e
        rl d
        ld a,l
        db #dd:sub l
        ld l,a
        ld a,h
        db #dd:sbc h
        ld h,a
        ld a,e
        sbc 0
        ld e,a
        ld a,d
        sbc 0
        ld d,a
        jr nc,clcd322
        ld a,l
        db #dd:add l
        ld l,a
        ld a,h
        db #dd:adc h
        ld h,a
        ld a,e
        adc 0
        ld e,a
        ld a,d
        adc 0
        ld d,a
        scf
clcd322 ccf
        ld a,(clcd32c)
        dec a
        jr nz,clcd321   ;HL=Value1 MOD Value2
        rl c
        rl b
        db #fd:ld a,l:rla:db #fd:ld l,a
        db #fd:ld a,h:rla:db #fd:ld h,a
        ret             ;IY,BC=Value1 DIV Value2

Fast 32bit division

Input: HL,DE=Value1, BC=Value2

Output: BCDE=Value1/Value2, HL=Value1 MOD Value2

Destroyed: AF

Not used: IX, IY

CPC Cycles: 1016-2444 (1730 on average), 254-611 usec (432 on average)

Size: 277 bytes

div_r macro
     local t2
     SLA   E
     RL    D
     ADC   HL, HL

     LD    A, L
     ADD   A, C
     LD    A, H
     ADC   A, B
     JR    NC, t2

     ADD   HL, BC
     INC   DE
t2
     endm
div_e macro
     local t1,t2
     SLA   E
     RL    D
     ADC   HL, HL
     JR    C, t1

     LD    A, L
     ADD   A, C
     LD    A, H
     ADC   A, B
     JR    NC, t2
t1
     ADD   HL, BC
     INC   DE
t2
     endm
div32x16 proc  ; BCDE = HLDE/BC, HL = HLDE%BC
     local DIV16, DIV32R, DIV32E
     DEC   BC
     LD    A, B
     CPL 
     LD    B, A
     LD    A, C
     CPL 
     LD    C, A
     ADD   A, L
     LD    A, B
     ADC   A, H
     JR    NC, DIV16

     PUSH  DE
     EX    DE, HL
     LD    HL, 0000
     CALL  DIV32R
     EX    DE, HL
     EX    (SP), HL
     EX    DE, HL
     CALL  DIV32E
     POP   BC
     RET
DIV16
     CALL  DIV32E
     LD    BC, 0000
     RET
DIV32R   ; DE = HLDE/(-BC), HL = HLDE%(-BC), -BC < $8000
     CALL  $+3
     rept 8
     div_r
     endm
     RET
DIV32E   ; DE = HLDE/(-BC), HL = HLDE%(-BC)
     CALL  $+3
     rept 8
     div_e
     endm
     RET
     endp 

Web links