Difference between revisions of "Programming:Integer Division"

From CPCWiki - THE Amstrad CPC encyclopedia!
Jump to: navigation, search
(the new fast division added)
(Fast 32bit division: a bit faster)
 
(3 intermediate revisions by the same user not shown)
Line 114: Line 114:
  
 
'''Destroyed:''' AF,DE,IY
 
'''Destroyed:''' AF,DE,IY
 +
 +
'''CPC Cycles:''' approximately 7800, 1900 usec
 +
 +
'''Size:'''  91 bytes
  
 
<pre>
 
<pre>
Line 168: Line 172:
 
         ret            ;IY,BC=Value1 DIV Value2
 
         ret            ;IY,BC=Value1 DIV Value2
 
</pre>
 
</pre>
 
  
 
== Fast 32bit division ==
 
== Fast 32bit division ==
Line 179: Line 182:
  
 
'''Not used:''' IX, IY
 
'''Not used:''' IX, IY
 +
 +
'''CPC Cycles:''' 1016-2444 (1730 on average), 254-611 usec (432 on average)
 +
 +
'''Size:''' 277 bytes
  
 
<pre>
 
<pre>
div macro
+
div_r macro
     local t1,t2
+
     local t2
     ADD   HL, HL
+
     SLA   E
     EX   DE, HL
+
     RL   D
     ADD   HL, HL
+
     ADC   HL, HL
    EX    DE, HL
+
    JP    NC, t1
+
  
    INC  HL
 
t1
 
 
     LD    A, L
 
     LD    A, L
 
     ADD  A, C
 
     ADD  A, C
 
     LD    A, H
 
     LD    A, H
 
     ADC  A, B
 
     ADC  A, B
     JP   NC, t2
+
     JR   NC, t2
  
 
     ADD  HL, BC
 
     ADD  HL, BC
 
     INC  DE
 
     INC  DE
t2
+
t2
 
     endm
 
     endm
 +
div_e macro
 +
    local t1,t2
 +
    SLA  E
 +
    RL    D
 +
    ADC  HL, HL
 +
    JR    C, t1
  
div32x16 proc  ; BCDE = HLDE/BC, HL = HLDE%BC
+
    LD    A, L
     local t1, DIV32_, DIV320
+
    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
 
     DEC  BC
 
     LD    A, B
 
     LD    A, B
Line 214: Line 233:
 
     LD    A, B
 
     LD    A, B
 
     ADC  A, H
 
     ADC  A, H
     JP   NC, DIV32_
+
     JR   NC, DIV16
  
 
     PUSH  DE
 
     PUSH  DE
 
     EX    DE, HL
 
     EX    DE, HL
 
     LD    HL, 0000
 
     LD    HL, 0000
     CALL  DIV320
+
     CALL  DIV32R
 
     EX    DE, HL
 
     EX    DE, HL
 
     EX    (SP), HL
 
     EX    (SP), HL
 
     EX    DE, HL
 
     EX    DE, HL
     CALL  DIV320
+
     CALL  DIV32E
 
     POP  BC
 
     POP  BC
 
     RET
 
     RET
DIV32_
+
DIV16
     CALL  DIV320
+
     CALL  DIV32E
 
     LD    BC, 0000
 
     LD    BC, 0000
 
     RET
 
     RET
DIV320   ; DE = HLDE/(-BC), HL = HLDE%(-BC)
+
DIV32R   ; DE = HLDE/(-BC), HL = HLDE%(-BC), -BC < $8000
     CALL  t1
+
     CALL  $+3
t1
+
 
     rept 8
 
     rept 8
     div
+
     div_r
 +
    endm
 +
    RET
 +
DIV32E  ; DE = HLDE/(-BC), HL = HLDE%(-BC)
 +
    CALL  $+3
 +
    rept 8
 +
    div_e
 
     endm
 
     endm
 
     RET
 
     RET
 
     endp  
 
     endp  
 
</pre>
 
</pre>
 +
 
== Web links ==
 
== Web links ==
  

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