Difference between revisions of "Z80 Routines:Math:Advance Math"

From WikiTI
Jump to: navigation, search
(Updated with a better implementation of ncr)
Line 8: Line 8:
 
=== nCr Algorithm ===
 
=== nCr Algorithm ===
  
−
This computes "n choose r" using an algorithm that makes use of both shadow registers and other calls. This can very likely be optimised, so feel free to edit with a new version.
+
This computes "n choose r" in such a way as to avoid overflow unless the final result would overflow 16 bits.
  
 
  <nowiki>
 
  <nowiki>
−
;===============================================================
+
;Written by Zeda
−
nCrHL_DE:
+
 
−
;===============================================================
+
; Requires
−
;Inputs:
+
;    mul16          ;BC*DE ==> DEHL
−
;     hl is "n"
+
;    DEHL_Div_BC    ;DEHL/BC ==> DEHL
−
;     de is "r"
+
 
 +
ncr_HL_DE:
 +
;"n choose r", defined as n!/(r!(n-r)!)
 +
;Computes "HL choose DE"
 +
;Inputs: HL,DE
 
;Outputs:
 
;Outputs:
−
;     interrupts off
+
;   HL is the result
−
;    a is 0
+
;       "HL choose DE"
−
;    bc is an intermediate result
+
;   carry flag reset means overflow
−
;     de is "n"
+
;Destroys:
−
;     hl is the result
+
;   A,BC,DE,IX
−
;     a' is not changed
+
;Notes:
−
;     bc' is "r"+1
+
;  Overflow is returned as 0
−
;     de' is the same as bc
+
;   Overflow happens if HL choose DE exceeds 65535
−
;     hl' is "r" or the compliment, whichever is smaller
+
;  This algorithm is constructed in such a way that intermediate
−
;===============================================================
+
;   operations won't erroneously trigger overflow.
−
    or a                     ;reset carry flag
+
;66 bytes
−
    sbc hl,de
+
  ld bc,1
−
    ret c                   ;r should not be bigger than n
+
  or a
−
    sbc hl,de \ add hl,de
+
  sbc hl,de
−
    jr nc,$+3
+
  jr c,ncr_oob
−
      ex de,hl
+
  jr z,ncr_exit
−
                            ;hl is R
+
  sbc hl,de
−
    push de
+
  add hl,de
−
    ld bc,1                ;A
+
  jr c,$+3
−
    exx
+
  ex de,hl
−
    pop de                  ;N
+
  ld a,h
−
    ld bc,1                ;C
+
  or l
−
    ld h,b \ ld l,c         ;D
+
  push hl
−
nCrLoop:
+
  pop ix
−
    push de
+
ncr_exit:
−
    push hl
+
  ld h,b
−
    call DE_Times_BC        ;Returns BC unchanged, DEHL is the product
+
  ld l,c
−
    push hl \ exx \ pop de
+
  scf
−
    push hl
+
  ret z
−
    call DE_Div_BC          ;Returns HL is the quotient, BC is not changed
+
ncr_loop:
−
    pop de
+
  push bc \ push de
−
    push hl \ ex de,hl \ exx \ pop hl
+
  push hl \ push bc
−
    ld b,h \ ld c,l
+
  ld b,h
−
    pop de \ add hl,de
+
  ld c,l
−
    pop de \ inc de
+
  call mul16          ;BC*DE ==> DEHL
−
    exx
+
  pop bc
−
    inc bc
+
  call DEHL_Div_BC    ;result in DEHL
−
    or a \ sbc hl,bc \ add hl,bc
+
  ld a,d
−
    exx
+
  or e
−
    jr nc,nCrLoop
+
  pop bc
−
    ret
+
  pop de
 +
  jr nz,ncr_overflow
 +
  add hl,bc
 +
  jr c,ncr_overflow
 +
  pop bc
 +
  inc bc
 +
  ld a,b
 +
  cp ixh
 +
  jr c,ncr_loop
 +
  ld a,ixl
 +
  cp c
 +
  jr nc,ncr_loop
 +
  ret
 +
ncr_overflow:
 +
  pop bc
 +
  xor a
 +
  ld b,a
 +
ncr_oob:
 +
  ld h,b
 +
  ld l,b
 +
  ret
 +
 
 
  </nowiki>
 
  </nowiki>
  

Revision as of 15:05, 30 September 2019


Introduction

These are routines designed for math of a slightly higher level. These don't necessarily contribute to everyday coding, but might be useful for an OS that handles such math (or programming language).

nCr Algorithm

This computes "n choose r" in such a way as to avoid overflow unless the final result would overflow 16 bits. 

;Written by Zeda

; Requires
;    mul16          ;BC*DE ==> DEHL
;    DEHL_Div_BC    ;DEHL/BC ==> DEHL

ncr_HL_DE:
;"n choose r", defined as n!/(r!(n-r)!)
;Computes "HL choose DE"
;Inputs: HL,DE
;Outputs:
;   HL is the result
;       "HL choose DE"
;   carry flag reset means overflow
;Destroys:
;   A,BC,DE,IX
;Notes:
;   Overflow is returned as 0
;   Overflow happens if HL choose DE exceeds 65535
;   This algorithm is constructed in such a way that intermediate
;   operations won't erroneously trigger overflow.
;66 bytes
  ld bc,1
  or a
  sbc hl,de
  jr c,ncr_oob
  jr z,ncr_exit
  sbc hl,de
  add hl,de
  jr c,$+3
  ex de,hl
  ld a,h
  or l
  push hl
  pop ix
ncr_exit:
  ld h,b
  ld l,c
  scf
  ret z
ncr_loop:
  push bc \ push de
  push hl \ push bc
  ld b,h
  ld c,l
  call mul16          ;BC*DE ==> DEHL
  pop bc
  call DEHL_Div_BC    ;result in DEHL
  ld a,d
  or e
  pop bc
  pop de
  jr nz,ncr_overflow
  add hl,bc
  jr c,ncr_overflow
  pop bc
  inc bc
  ld a,b
  cp ixh
  jr c,ncr_loop
  ld a,ixl
  cp c
  jr nc,ncr_loop
  ret
ncr_overflow:
  pop bc
  xor a
  ld b,a
ncr_oob:
  ld h,b
  ld l,b
  ret

GCDHL_BC

This finds the greatest common divisor (GCD) of HL and BC. 

GCDHL_BC:
;Inputs:
;     HL is a number
;     BC is a number
;Outputs:
;     A is 0
;     BC is the GCD
;     DE is 0
;Destroys:
;     HL
;Size:  25 bytes
;Speed: 30 to 49708 cycles
;       -As slow as about 126 times per second at 6MHz
;       -As fast as about 209715 times per second at 6MHz
;Speed break down:
;     If HL=BC, 30 cycles
;     24+1552x
;     If BC>HL, add 20 cycles
;     *x is from 1 to at most 32 (because we use 2 16-bit numbers)
;
     or a \ sbc hl,bc     ;B7ED42    19
     ret z                ;C8        5|11
     add hl,bc            ;09        11
     jr nc,$+8            ;3006      11|31
       ld a,h             ;7C        --
       ld h,b             ;60        --
       ld b,a             ;47        --
       ld a,l             ;7D        --
       ld l,c             ;69        --
       ld c,a             ;4F        --
Loop:
     call HL_Div_BC       ;CD****    1511    returns BC unchanged, DE is the remainder
     ld a,d \ or e        ;7AB2      8
     ret z                ;C8        5|11
     ld h,b \ ld l,c      ;6069      8
     ld b,d \ ld c,e      ;424B      8
     jr $-10              ;18F8      12

LCM

This is as simple as multiplying the two numbers and dividing by the GCD.


Credits and Contributions

  • Zeda (Xeda) Elnara for the nCr and GCD algorithm
Retrieved from "https://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Advance_Math&oldid=11633"