My brain has gone to sleep early today...

It's telling me that there is no need, in _signed_ 16x16->16bit multiplication, to consider the sign of either multiplicand or multiplier; the result is the same whether just performed as an unsigned 16x16->16, or by inverting negative parameters and inverting the result (if necessary). As far as I recall, all the problems with this shuffle themselves into the (discarded) upper sixteen bits of the answer.

For signed division, though, this is clearly _not_ the case: e.g. 0x8421 / 2 = 0x4210, which is clearly incorrect for signed values. Here, one must either invert the input(s) (and if necessary, the result), or find an algorithm that maintains sign. It also raises a potential issue with a remainder, I think.

Hmm. Am I right?

Neil

Correct, unfortunately. I've settled for the pre-invert/post-invert solution myself in the past, since it lets you use mostly the same code for signed and unsigned division; in this case, your post-invert flag would be the XOR of the two MSBs. The broad outline would look like this:

(Is there a canonical "correct" answer for whether the sign of the remainder should change? I can't recall.)

Thanks, that's what I came up with. XOR the two highest bits of the dividend and divisor, if the result is true then the result will need inverting, after inverting either (or both) input if negative.

I was curious because I came across info on the web which suggested that this was also necessary for multiplication, but as far as I can see there are no cases where the bottom sixteen bits of the multiply (implied 16x16=32, with the top bits discarded) are incorrect irrespective of the sign of either input.

Neil

It's complicated.

The properties that you almost always want are

• (a/b)*b + (a%b) = a
• abs(a%b) < abs(b)

It can also be nice to have

• abs(a/b) = abs(a)/abs(b)
• sign(a%b) = sign(b)

but unfortunately you can't have both.

Some languages provide two remainder operations, with the sign of the remainder being the sign either of the dividend or the divisor, letting people choose which properties are more important to them. In VHDL, you get


rem is the remainder of a division that rounds towards zero (so 10/-3 = -3) and mod is the remainder of a division that rounds towards negative infinity (so 10/-3 = -4). There might some specialised mathematical languages that provide both of these division operators, but I don't know any - even though VHDL provides both remainders, it has only the one divide. Usually you only get one divide and one remainder, and they're both the "round towards zero" flavour.