Author Topic: Bit Math  (Read 3699 times)

0 Members and 2 Guests are viewing this topic.

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Bit Math
« on: April 29, 2012, 12:19:12 pm »
Just wondering.... Is this the correct way to Multiply numbers, using bit shifting. Modify as needed. And how would you do division?

Code: [Select]
ld c,a
$: rl a
rr b
jr c, +$
jz nz, -$
$: or c
push af
ld a,b
or b
ret z
pop af
jr -2$
;Your next command, upon returning, should be pop af.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Bit Math
« Reply #1 on: April 29, 2012, 12:35:12 pm »
Hmm, it doesn't look quite right if you are trying to multiply registers. I don't know if this will help you?
Code: [Select]

D_Times_E:
;Inputs:
;     D and E are factors
;Outputs:
;     A is the product (lower 8 bits)
;     B is 0
;     C,DE, HL are not changed
;Size:  12 bytes
;Speed: 304+b cycles where b is the number of set bits in E
     xor a         ;This is an optimised way to set A to zero. 4 cycles, 1 byte.
     ld b,8        ;Number of bits in E, so number of times we will cycle through
Loop:
     add a,a       ;We double A, so we shift it left.
     rlc e         ;We want the next bit in E, so it is shifted into the c flag
     jr nc,$+3     ;If it is 0, we don't need to add anything to A
       add a,d     ;Since it was 1, we do A+1*D
     djnz Loop     ;Decrements B, if it isn't zero yet, jump back to Loop:
     ret
Basically, this works like regular multiplication that you would do by hand. Since the above code is using 8-bit registers, there are 8 digits per number. Since bits are only 1 or 0, we only have to multiply by one or zero. Then we just add the result to the accumulator. When we get ready to add the next multiplication, we need to shift the accumulator left. In Decimal, we do this by multiplying by ten (tacking on a zero at the end). In binary, we multiply by 2. I hope this helps?

As for division, the algorithm is actually very similar and uses long division like you learned in grade school, except with binary. Say you have 37/5. In binary, you are doing:

00100101/101.

so you shift the 00100101 and move the overflow into another register. Pretend I have done this 5 times already:
0000010010100000
Now you see, the overflow is not greater than 5, so shift once more:
0000100101000000
Now it is, so we get tricky. First, subtract five from the overflow and increment the other number by 1:
0000010001000001
Now shift again:
0000100010000010
Now it is greater than 5 again, so:
0000001110000011
Shift again:
00000011100000110
And do the proper adjustment:
00000001000000111

Now look at that o_O You have the remainder as 2 and the division is 7. Note that in all, there were 8 shifts. I hope this helps! If you want a division code, feel free to ask :)

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: Bit Math
« Reply #2 on: April 29, 2012, 12:56:14 pm »
Oh, and so to do 2-byte multiplication, you can simply change the counter to 16, and then the input registers to 16-bit ones?

and yeah, the division routine would be great.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Bit Math
« Reply #3 on: April 29, 2012, 12:59:17 pm »
For most of your z80 math routine needs, Z80 Bits is an excellent resource. It has a variety of multiplication, division, square root, and other z80 routines.
« Last Edit: April 29, 2012, 12:59:56 pm by Runer112 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Bit Math
« Reply #4 on: April 29, 2012, 01:08:46 pm »
Also, for future reference, it's a very bad idea to return after pushing something to the stack, since the processor will use the pushed value as the return address. So pushing af, returning, and popping af won't act like you think it will.
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Bit Math
« Reply #5 on: April 29, 2012, 01:36:44 pm »
Yes, Z80 Bits does indeed have some useful routines in there to look at :)

Oh, and so to do 2-byte multiplication, you can simply change the counter to 16, and then the input registers to 16-bit ones?

and yeah, the division routine would be great.
Yep :) Just remember, though, that 16-bit arithmetic sometimes takes a bit more work. For example, shifting HL left is as simple as add hl,hl, but shifting DE left, there is no add de,de instruction. So you have to do something like sla e \ rl d which is 3 bytes larger.

As for division, here is a routine:
Code: [Select]
HL_Div_C:
;Inputs:
;     HL is the numerator
;     C is the denominator
;Outputs:
;     A is the remainder
;     B is 0
;     C is not changed
;     DE is not changed
;     HL is the quotient
;
       ld b,16
       xor a
Loop:
         add hl,hl
         rla
         cp c
         jr c,$+4
           inc l
           sub c
         djnz Loop
       ret
Luckily, division is pretty simple compared to multiplication. DEHL/C is much easier than DEHL*C. XD