Re: A86: Sorry Dux. =-|

[Prev][Next][Index][Thread]

Re: A86: Sorry Dux. =-|




Tercero wrote:

> Joshua J Seagoe wrote:
> >
> > why clear a?
>
> Pardon me while I go bury my head in the sand. <-(
> And Kirk Meyer, almighty creator of SC2K missed that. =)
> Originally, I wanted the output to be ahl.
>
> Russian Peasant's Algorithm:
> made by Dux Gregis
> modified and renamed by Tim Farrell
>         (head currently buried in sand)
> nitpicked by Kirk Meyer
> scrutinized by RabidCow
>
> Really Really Final Version - (Shut Up! =)
>
> ;African Swallow Algorithm_________________________
> ;Input: de * b                                    |
> ;Output: hl                                       |
> ;Destroys: b, de, hl                              |
> ;Size: 14 bytes                                   |
> ;--------------------------------------------------
> ASMult:
>         ld hl, $0000    ;Ugh, I'm tired of changing this comment
> ASMultLp:
>         srl b           ;check bit
>         jp nc, ASkipadd ;if bit = 1 then hl + de
>         add hl, de      ;add'm up
> ASkipadd:
>         add hl, hl      ;mult hl by 2
>         jp nz, ASMultLp ;if b != 0 then keep going
>         ret             ;ret

I don't know if you tested this or not, but this doesn't work.  I'll try
to explain why:

The algorithm works like this:  Shift the smaller number right until it
becomes zero, and each time you shift the smaller #, shift the larger
number left.  At the end of this, all the numbers in the larger # are
added together when bit 0 of the smaller number is set.  But instead of
waiting until its done calculating, you can add it to another register
pair when it carries, so long as you return after it has checked the
carry.
Assuming that b is the smaller # and hl is the larger number and de is
used to collect the shifted hl values:

5x9
b                hl                de

101           1001     ->    1001
10            10010            not affected
1             100100   ->    101101 = 45

You are using hl as both the collector and the left shifter and getting
the wrong numbers.  (you have good intentions of course :-)

Also, I thought about it and decided that more time can be saved over
all if you check which of the input numbers is smallest before the
routine.  Otherwise, 179*0 will loop 7 times when it really doesn't need
to loop at all.

Here's the Russian Peasants' Algorithm again (I doubt there's anything
that will speed it up):

;input= h and l
;output= de is h*l (all reg destroyed but c)

mlt_hl:
 ld de,0              ;clear de initially
 ld a,h
 cp l                   ;check to see which is the greater of h and l
 jr c,mlt_start
 ld h,l
 ld l,a
mlt_start:
 ld b,h
 ld h,d                   ;b is now smaller of the two, hl is the
greater
mlt_loop:
 srl b                   ;if bit 0 is set, add hl to de
 jr nc,skip_collect
 ex de,hl
 add hl,de          ;store addition in de
 ex de,hl
skip collect:
 ret z                   ;return when b is zero (still set from srl)
 add hl,hl              ;shift hl left
 jr mlt_loop
Follow-Ups: References: