24 bit multiplication

Quote from: jacobly on 09 December, 2011, 03:35:58

My first multiplication routine takes 2746 - 4570 cycles, the second takes 1680 - 2880 cycles.

Oh boy, optimization time Cheesy

The best I have so far is somewhere around 1800 cycles average (I'm too lazy to work out the exact probabilities at the moment, and not counting memory delays) using a squaring table and undocumented IX instructions. Input is BDE and CHL, output is BCDEAL. This routine works by expanding the formula 2xy = x²+y²-|x-y|², summed over each of the 9 pairs of bytes in the input.

(I'm not saying this is practical - unless you really have thousands of 24-bit multiplications to perform, you don't need this kind of speed. This is just for fun.)

Code: Select All | Copy To Clipboard

SUBFIRST .macro src1, src2, hdest, ldest
 exx
 ld a, src1
 sub src2
 jr nc, $ + 4
 neg
 exx
 ld l, a
 ld a, ldest
 sub (hl)
 ld ldest, a
 inc h
 ld a, hdest
 sbc a, (hl)
 ld hdest, a
  .endm

SUBNEXT .macro src1, src2, hdest, ldest
 dec h
 ex af, af'
 exx
 ld a, src1
 sub src2
 jr nc, $ + 4
 neg
 exx
 ld l, a
 ex af, af'
 ld a, ldest
 sbc a, (hl)
 ld ldest, a
 inc h
 ld a, hdest
 sbc a, (hl)
 ld hdest, a
  .endm

BDE_times_CHL_sqrdiff_v3:
 ld a, d
 exx
 ld h, high(sqrtab)
 ld l, a
 ld e, (hl)
 inc h
 ld d, (hl)  ; DE = d²
 exx
 ld a, b
 exx
 ld l, a
 ld b, (hl)
 dec h
 ld c, (hl)  ; BC = b²
 exx
 ld a, e
 exx
 ld l, a
 ld a, (hl)
 inc h
 ld h, (hl)
 ld l, a   ; HL = e²
 call BC_DE_HL_times_10101
 push bc
  push hl
   push de
    exx
    ld a, h
    exx
    ld h, high(sqrtab)
    ld l, a
    ld e, (hl)
    inc h
    ld d, (hl)  ; DE = h²
    exx
    ld a, c
    exx
    ld l, a
    ld b, (hl)
    dec h
    ld c, (hl)  ; BC = c²
    exx
    ld a, l
    exx
    ld l, a
    ld a, (hl)
    inc h
    ld h, (hl)
    ld l, a  ; HL = l²
    call BC_DE_HL_times_10101
    pop ix
   add ix, de
   pop de
  adc hl, de
  ex de, hl
  pop hl
 adc hl, bc
 ld b, h
 ld c, l   ; BCDEIX = total
 push af

  ld h, high(sqrtab)
  SUBFIRST e, l, ixh, ixl
  SUBNEXT  d, h, d, e
  SUBNEXT  b, c, b, c
  jp nc, BDE_times_CHL_sqrdiff_v3_nc1
  pop af
 ccf
 push af
BDE_times_CHL_sqrdiff_v3_nc1:

  inc b

  dec h
  SUBFIRST e, h, e, ixh
  SUBNEXT  d, c, c, d
  jr nc, BDE_times_CHL_sqrdiff_v3_nc2
  dec b
  jp nz, BDE_times_CHL_sqrdiff_v3_nc2
  pop af
 ccf
 push af
BDE_times_CHL_sqrdiff_v3_nc2:

  dec h
  SUBFIRST d, l, e, ixh
  SUBNEXT  b, h, c, d
  jr nc, BDE_times_CHL_sqrdiff_v3_nc3
  dec b
  jp nz, BDE_times_CHL_sqrdiff_v3_nc3
  pop af
 ccf
 push af
BDE_times_CHL_sqrdiff_v3_nc3:

  inc c

  dec h
  SUBFIRST b, l, d, e
  jr nc, BDE_times_CHL_sqrdiff_v3_nc4
  dec c
  jp nz, BDE_times_CHL_sqrdiff_v3_nc4
  dec b
  jp nz, BDE_times_CHL_sqrdiff_v3_nc4
  pop af
 ccf
 push af
BDE_times_CHL_sqrdiff_v3_nc4:

  dec h
  SUBFIRST e, c, d, e
  pop hl
 jr nc, BDE_times_CHL_sqrdiff_v3_nc5
 dec c
 jp nz, BDE_times_CHL_sqrdiff_v3_nc5
 dec b
 jp nz, BDE_times_CHL_sqrdiff_v3_nc5
 inc l
BDE_times_CHL_sqrdiff_v3_nc5:

 dec b
 dec c

 rr l
 rr b
 rr c
 rr d
 rr e
 ld a, ixl
 ld l, a
 ld a, ixh
 rra
 rr l
 ret


BC_DE_HL_times_10101:
 push bc
  ld a, h
  ex af, af'
  sub a
  ld c, a
  ld b, l
  add hl, bc
  adc a, a
  ld b, e
  add hl, bc
  adc a, c  ; AHL = [ L+H+E L ]
  pop bc
 push hl
  push bc
   ld c, a
   ld b, 0
   ex af, af'
   ld h, a
   add hl, bc  ; no way this can carry (initial HL is a square)
   ld c, a
   ld b, e
   sub a
   add hl, bc
   adc a, a  ; AHL(SP+2) = [ H+E L+H L+H+E L ]
   add hl, de
   adc a, 0  ; AHL(SP+2) = [ H+E+D L+H+E L+H+E L ]
   pop bc
  add hl, bc
  adc a, 0  ; AHL(SP) = [ H+E+D+B L+H+E+C L+H+E L ]
  ld e, d
  ld d, c
  add hl, de
  adc a, b
  jr nc, BC_DE_HL_times_10101_nc1
  inc b   ; BAHL(SP) = [ B B H+E+D+C+B L+H+E+D+C L+H+E L ]
BC_DE_HL_times_10101_nc1:
  add a, e
  jr nc, BC_DE_HL_times_10101_nc2
  inc b   ; BAHL(SP) = [ B D+B H+E+D+C+B L+H+E+D+C L+H+E L ]
BC_DE_HL_times_10101_nc2:
  pop de
 add a, c
 ld c, a
 ret nc
 inc b   ; BCHLDE = [ B D+C+B H+E+D+C+B L+H+E+D+C L+H+E L ]
 ret

To get back to the topic somewhat, ACagliano, it sounds like you're more interested in squaring than in general multiplication. Squaring can be considerably faster, especially if you use a lookup table (e.g., my best 16-bit squaring routine is around 170 cycles, versus around 800 for general multiplication.)