Multiplication!

[systwo]

Hello everyone!

I've been looking into some 16 bit multiplication but I've come across with few problems. I could not understand much of the bitwise based multiplication and I'm guessing I need to do something like them in order to perform math with a 16 bit answer. Is there anyone who may be able to enlighten me?


Thanks!

[ralphdspam]

There are a bunch of routines on WikiTI.

http://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Multiplication

I'm not really sure what you're asking for, can you please elaborate?

[jacobly]

An example may help:

         11001100 = a
       × 10010110 = b
       ----------
         00000000
        11001100
       11001100
      00000000
     11001100
    00000000
   00000000
+ 00000000
-----------------
  111011110001000

So as you can see, in binary, for each bit you add either 0 or a (shifted by some amount), depending on the corresponding bit in b.
The way this is usually done is:
    1. shift the running total left one bit
    2. check the msb of b
    3. if set, add a to the running total
    4. shift b left one bit
    5. repeat steps 1-4 for each bit in b
    6. the answer is the current running total

[chickendude]

Thanks for writing that out, jacobly. z80 arithmetic has always been a bit confusing for me (and i'm not very good at math to boot).

[ZippyDee]

An example may help:

         11001100 = a
       × 10010110 = b
       ----------
         00000000
        11001100
       11001100
      00000000
     11001100
    00000000
   00000000
+ 00000000
-----------------
  111011110001000

So as you can see, in binary, for each bit you add either 0 or a (shifted by some amount), depending on the corresponding bit in b.
The way this is usually done is:
    1. shift the running total left one bit
    2. check the msb of b
    3. if set, add a to the running total
    4. shift b left one bit
    5. repeat steps 1-4 for each bit in b
    6. the answer is the current running total

I think there is a mistake in that written out example...Shouldn't the last iteration be adding 10010110, not 00000000? Also, shouldn't step 4 be "shift b right one bit"?

[Xeda112358]

Jacobly has the best idea that I have seen and it is how I think of it. It really is pretty much like how you learned to multiply in school, but multiplying by one or zero is super easy

[systwo]

Hmm... That never occurred to me. So its like reverse multiplication for me(I usually start on the right). Thank you so much for this! I have been thinking of how to do multiplication with just arithmetic on the a register and it drove me insane!

[ZippyDee]

Er...no, you should be starting on the right still...

I believe jacobly's post should have said:

         11001100 = a
       × 10010110 = b
       ----------
         00000000
        11001100
       11001100
      00000000
     11001100
    00000000
   00000000
+ 11001100
-----------------
  111011110001000

So as you can see, in binary, for each bit you add either 0 or a (shifted by some amount), depending on the corresponding bit in b.
The way this is usually done is:
    1. shift the running total left one bit
    2. check the lsb of b
    3. if set, add a to the running total
    4. shift b right one bit
    5. repeat steps 1-4 for each bit in b
    6. the answer is the current running total

[systwo]

Wouldn't step 2 be check the lsb then? Or is this an endian thing? Also wouldn't shifting the running total left result in the backwards answer? Sorry if these questions are simple, I'm still getting the hang of bitwise operations.

Edit: Oops, didn't see your edit there ZippyDee!

[Runer112]

I'm pretty sure the algorithm jacobly wrote is correct for how multiplication is usually done on z80 systems. Shifting left in situations like this is usually easier and faster on the z80. What may be confusing is that the math printed out above the algorithm steps is not actually showing the algorithm, it's just showing the elementary school multiplication method in binary.

However, you are correct that the last number added to the result of the long-hand multiplication should be 11001100.

[ZippyDee]

Hmm... I guess that does make sense. Looking back over that I realize that I was thinking of shifting the multiplicand (like the example shows) rather than the running total.

[Xeda112358]

As a note that I am sure everybody realises (but I will still go into some detail), the shifting left occurs because in binary that is multiplying by 2 (you can also add it to itself) and this is because it is base 2. When you do that, you are just adding a zero to the end of the number. In the more familiar base of base 10 (or any base above 2), you have to worry about intermediate carry stuff, but it is pretty much the same. If I wanted to do 367*183, it would look like this
183 shift left is 83 with 1 as the digit to use
1*367=367, this is what we add to the accumulator
Shift the 83 left and we have 3 (well, 300), and 8 is the digit to check
Shift the accumulator left to multiply by 10
8*367=2936, this we add to the accumulator
Acc=6606
Acc shifted left to multiply by 10
shift left to get the 3
3*367=1101, add this to the accumulator
Acc=67161

Check it and it works Pretty much, you are doing multiplication "the normal way", but backwards (last digit first). If you notice, the first result was multiplied by a total of 100 which fits (we did 1*367 for 100*367).