View source for Talk:Programming:Integer Multiplication

The FastMult routine using logs can be optimised somewhat from it's original by removing the slow SET instructions and extra direct addressing operation:

<pre>
FastMult:
  ld      l,c
  ld      h,&82
  ld      d,(hl)          ; d = 32 * log_2(c)
  
  ld      l,b
  ld      a,(hl)          ; a = 32 * log_2(b)
  
  add     a,d
  ld      l,a
  ld      a,0
  adc     a,0
  ld      h,a             ; hl = d + a
  
  add     hl,hl
  set     2,h             ; hl = hl + $0400
  set     7,h             ; hl = hl + &8000
  
  ld      e,(hl)
  inc     hl
  ld      d,(hl)          ; de = 2^((hl)/32)
  
  ret
</pre>

to

<pre>
FastMult:
  ld      l,c
  ld      h,&82
  ld      d,(hl)          ; d = 32 * log_2(c)
  
  ld      l,b
  ld      a,(hl)          ; a = 32 * log_2(b)
  
  add     a,d
  ld      l,a
  adc     &42
  sub l
  ld      h,a             ; hl = d + a
  
  add     hl,hl
  
  ld      e,(hl)
  inc     l
  ld      d,(hl)          ; de = 2^((hl)/32)
  
  ret
</pre>

The add hl,hl can also be removed if the tables are split with low-byte in one page and high-byte in the other and changing the &42 to &84. Since there are 512 entries in the anti-log table, you'd need two INC L's.

:So the more optimal way would look like this:

<pre>
FastMult:
  ld      l,c
  ld      h,logtab/256
  ld      a,(hl)          ; a = 32 * log_2(c)
  ld      l,b
  add     (hl)            ; cf,a = 32 * log_2(c) + 32 * log_2(b)
  ld      l,a
  ld      a,h
  adc     1
  ld      h,a
  ld      e,(hl)
  inc     h
  inc     h
  ld      d,(hl)          ; de = 2^((hl)/32)
  ret
</pre>

The two low and highbyte antilogtabs have to follow directly after the logtab. -- [[User:Prodatron|Prodatron]] 11:51, 7 May 2007 (CEST)