Z80 Routines:Math:Advance Math

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