Author Topic: [z80] 16-bit * 16-bit = 32-bit Signed Multiplication  (Read 7663 times)

0 Members and 1 Guest are viewing this topic.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
[z80] 16-bit * 16-bit = 32-bit Signed Multiplication
« on: December 17, 2010, 04:59:42 pm »
This is a somewhat challenging routine I've been trying to develop for z80 assembly. I'm trying to find a way to multiply two signed 16-bit operands together and get a signed 32-bit result.

I already have one working method, although it's fairly hacky. Its general structure is as follows:
  • Xor the high bytes of the two operands and push af
  • Convert the operands into their absolute values
  • Multiply these two values with the normal restoring multiplication algorithm
  • Pop af and return if sign flag is unset
  • Negate the result of the multiplication and return

Somehow, I get the feeling there are faster and/or more elegant solutions than this.

The most elegant solution would just be a modified restoring multiplication algorithm that deals with signed numbers correctly. After having stared down the restoring multiplication algorithm for about the past hour, I don't know how reasonable this is, though. And unless there's some simple change I'm not seeing that would suddenly make this work, any solution of this form would probably consume a lot of extra cycles in each iteration.

Something that has occurred to me as a more achievable and probably faster solution, albeit larger, consists of a test that branches into one of three different versions of the restoring multiplication algorithm. Which algorithm to use would be determined based on whether neither, one, or both of the operands are negative. This is the method I am currently trying to develop. After a bit of messing around with the restoring multiplication algorithm, though, I'm still fairly confused about how to form the two modified algorithms that would be needed.


Any ideas?

Offline Goplat

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 289
  • Rating: +82/-0
    • View Profile
Re: [z80] 16-bit * 16-bit = 32-bit Signed Multiplication
« Reply #1 on: December 17, 2010, 08:19:04 pm »
Here's a possibillity: Since a negative signed number is 65536 less than its interpreted as unsigned, you can just do an unsigned multiplication and if any side is negative, subtract the other side from the high word of the result:
Code: [Select]
a b product

pos pos ab                 = ab
pos neg a(b-65536)         = ab - 65536a
neg pos (a-65536)b         = ab - 65536b
neg neg (a-65536)(b-65536) = ab - 65536(a+b)
Numquam te deseram; numquam te deficiam; numquam circa curram et te desolabo
Numquam te plorare faciam; numquam valedicam; numquam mendacium dicam et te vulnerabo

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [z80] 16-bit * 16-bit = 32-bit Signed Multiplication
« Reply #2 on: December 17, 2010, 08:21:16 pm »
I LOVE YOU GOPLAT

EDIT: Well I don't really love you, that would just be creepy since I don't know you. But still, that's a pretty nice method you pointed out.
« Last Edit: December 17, 2010, 08:26:59 pm by Runer112 »

Offline Quigibo

  • The Executioner
  • CoT Emeritus
  • LV11 Super Veteran (Next: 3000)
  • *
  • Posts: 2031
  • Rating: +1075/-24
  • I wish real life had a "Save" and "Load" button...
    • View Profile
Re: [z80] 16-bit * 16-bit = 32-bit Signed Multiplication
« Reply #3 on: December 17, 2010, 08:48:44 pm »
The routine Axe uses does a 32b=16b*16b operation if you want to use that.  HL contains the lower 16 bits of the result and DE contains the upper 16 bits if I'm not mistaken.

EDIT: Wait nevermind, its unsigned.
« Last Edit: December 17, 2010, 08:54:05 pm by Quigibo »
___Axe_Parser___
Today the calculator, tomorrow the world!

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [z80] 16-bit * 16-bit = 32-bit Signed Multiplication
« Reply #4 on: December 17, 2010, 08:59:27 pm »
Yeah, I already stole borrowed your routine for the fact that it can output a 32-bit result. ;)
« Last Edit: December 17, 2010, 09:00:00 pm by Runer112 »