Z80 Routines:Math:Advance Math - Revision history

Zeda: (using real name for credits)

2019-09-30T23:08:38Z

(using real name for credits)

Zeda: using better GCD algorithm

2019-09-30T23:07:26Z

using better GCD algorithm

Zeda: Updated with a better implementation of ncr

2019-09-30T23:05:51Z

Updated with a better implementation of ncr

Zeda at 17:26, 9 January 2012

2012-01-09T17:26:50Z

Zeda: Created page with 'Advanced_Math Advanced_Math == Introduction == These are routines designed for math of a slightly higher level. These d…'

2012-01-09T17:25:16Z

Created page with 'Advanced_Math Advanced_Math == Introduction == These are routines designed for math of a slightly higher level. These d…'

New page

[[Category:Z80 Routines:Math|Advanced_Math]]
[[Category:Z80 Routines|Advanced_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" 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.

<nowiki>
;===============================================================
nCrHL_DE:
;===============================================================
;Inputs:
; hl is "n"
; de is "r"
;Outputs:
; interrupts off
; a is 0
; bc is an intermediate result
; de is "n"
; hl is the result
; a' is not changed
; bc' is "r"+1
; de' is the same as bc
; hl' is "r" or the compliment, whichever is smaller
;===============================================================
or a ;reset carry flag
sbc hl,de
ret c ;r should not be bigger than n
sbc hl,de \ add hl,de
jr nc,$+3
ex de,hl
;hl is R
push de
ld bc,1 ;A
exx
pop de ;N
ld bc,1 ;C
ld h,b \ ld l,c ;D
nCrLoop:
push de
push hl
call DE_Times_BC ;Returns BC unchanged, DEHL is the product
push hl \ exx \ pop de
push hl
call DE_Div_BC ;Returns HL is the quotient, BC is not changed
pop de
push hl \ ex de,hl \ exx \ pop hl
ld b,h \ ld c,l
pop de \ add hl,de
pop de \ inc de
exx
inc bc
or a \ sbc hl,bc \ add hl,bc
exx
jr nc,nCrLoop
ret
</nowiki>

=== GCDHL_BC ===

This finds the greatest common divisor (GCD) of HL and BC.
<nowiki>
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
</nowiki>

=== 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

← Older revision		Revision as of 23:08, 30 September 2019
Line 153:		Line 153:

	== Credits and Contributions ==		== Credits and Contributions ==
−	* '''Zeda ~~(Xeda) Elnara~~''' for the nCr and GCD algorithm	+	* '''Zeda Thomas''' for the nCr and GCD algorithm

@@ Line 86: / Line 86: @@
   </nowiki>
-=== GCDHL_BC ===
+=== GCDHL_DE ===
-This finds the greatest common divisor (GCD) of HL and BC.
+This finds the greatest common divisor (GCD) of HL and DE using the binary GCD algorithm to improve performance.
   <nowiki>
-GCDHL_BC:
+gcdHL_DE:
-;Inputs:
+;gcd(HL,DE)->HL
-;     HL is a number
+;Output:
-;     BC is a number
+;   B=0
-;Outputs:
+;   HL is the GCD of the inputs
-;     A is 0
-;     BC is the GCD
-;     DE is 0
 ;Destroys:
-;     HL
+;   A,DE
-;Size:  25 bytes
+;     DE is guaranteed 0 unless the output is 0 (which only happens if one of the inputs is 0).
-;Speed: 30 to 49708 cycles
+;Uses the binary GCD algorithm
-;       -As slow as about 126 times per second at 6MHz
+;65 bytes
-;       -As fast as about 209715 times per second at 6MHz
-;Speed break down:
+;B is our cofactor-of-2 counter
-;     If HL=BC, 30 cycles
+     ld b,0
-;     24+1552x
-;     If BC>HL, add 20 cycles
+;If HL=0, return 0
-;     *x is from 1 to at most 32 (because we use 2 16-bit numbers)
+     ld a,h \ or l \ ret z
-−
-     or a \ sbc hl,bc     ;B7ED42    19
+;If DE=0, return 0
-     ret z                ;C8        5|11
+    ex de,hl
-     add hl,bc            ;09        11
+    ld a,h \ or l \ jr nz,gcd_test_cofactor_of_2
-     jr nc,$+8            ;3006      11|31
+    ret
-       ld a,h             ;7C        --
-       ld h,b             ;60        --
+gcd_cofactor_2_loop:
-       ld b,a             ;47        --
+    inc b
-       ld a,l             ;7D        --
+    srl h \ rr l
-       ld l,c             ;69        --
+    srl d \ rr e
-       ld c,a             ;4F        --
+gcd_test_cofactor_of_2:
-Loop:
+    inc b
-     call HL_Div_BC       ;CD****    1511    returns BC unchanged, DE is the remainder
+    ld a,e
-     ld a,d \ or e        ;7AB2      8
+    or l
-     ret z                ;C8        5|11
+    rra
-     ld h,b \ ld l,c      ;6069      8
+    jr nc,gcd_cofactor_2_loop
-     ld b,d \ ld c,e      ;424B      8
-     jr $-10              ;18F8      12
+gcd_remove_factors_of_2_op2:
   </nowiki>

@@ Line 8: / Line 8: @@
 === 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>
-;===============================================================
+;Written by Zeda
-nCrHL_DE:
-;===============================================================
+; Requires
-;Inputs:
+;    mul16          ;BC*DE ==> DEHL
-;     hl is "n"
+;    DEHL_Div_BC    ;DEHL/BC ==> DEHL
-;     de is "r"
 ;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
   </nowiki>

@@ Line 1: / Line 1: @@
-[[Category:Z80 Routines:Math|Advanced_Math]]
+[[Category:Z80 Routines:Math|Advanced Math]]
-[[Category:Z80 Routines|Advanced_Math]]
+[[Category:Z80 Routines|Advanced Math]]
 == Introduction ==