32x32 and 64x64 signed integer multiplication

[Christopher Dyken]

Hi group,

I'm trying to implement two routines to handle 32x32-bits and
64x64-bits signed integer multiplication on a 32 bits machine in C. It
easy to find descriptions of non-signed multiplication, however, I
haven't found any good descriptions for the signed counterpart.

Does any of you have a good reference for this topic?

Thanks in advance,
Chris.

 

[Richard Bos]

I'm trying to implement two routines to handle 32x32-bits and
64x64-bits signed integer multiplication on a 32 bits machine in C. It
easy to find descriptions of non-signed multiplication, however, I
haven't found any good descriptions for the signed counterpart.

What about:
- for each signed number, check whether it's signed, check whether these
signs are equal, and remember this fact.
- set both sign bits to +.
- multiply as if they're unsigned.
- check whether the result is too large for a signed number, and if so,
do what you've decided to do on overflow.
- if the sign bits were equal, leave the number as it is. If they
weren't, set its sign bit.

Hardest part is probably deciding what to do on overflow. Crashing is
harsh. Ignoring is perhaps sufficient in many circumstances. Setting an
error flag is probably best.

Richard

 

[Christopher Dyken]

| What about:
| - for each signed number, check whether it's signed, check whether these
| signs are equal, and remember this fact.
| - set both sign bits to +.
| - multiply as if they're unsigned.
| - check whether the result is too large for a signed number, and if so,
| do what you've decided to do on overflow.
| - if the sign bits were equal, leave the number as it is. If they
| weren't, set its sign bit.| Hardest part is probably deciding what to do on overflow. Crashing is
| harsh. Ignoring is perhaps sufficient in many circumstances. Setting an
| error flag is probably best.

Hi Richard,

I have no problem limiting the input values (I define the interval
myself), and thus, I can be sure that no overflows occour. So this is
not an issue.

As I see it, this strategy involves some if/else-tests, which can harm
the pipeline throughput (or am I wrong?) . I've an intuitive feeling
that it should be possible to do this without any conditionals.

Regards,
Chris.

 

[Julian V. Noble]

| What about:
| - for each signed number, check whether it's signed, check whether these
| signs are equal, and remember this fact.
| - set both sign bits to +.
| - multiply as if they're unsigned.
| - check whether the result is too large for a signed number, and if so,
| do what you've decided to do on overflow.
| - if the sign bits were equal, leave the number as it is. If they
| weren't, set its sign bit.
| Hardest part is probably deciding what to do on overflow. Crashing is
| harsh. Ignoring is perhaps sufficient in many circumstances. Setting an
| error flag is probably best.

Hi Richard,

I have no problem limiting the input values (I define the interval
myself), and thus, I can be sure that no overflows occour. So this is
not an issue.

As I see it, this strategy involves some if/else-tests, which can harm
the pipeline throughput (or am I wrong?) . I've an intuitive feeling
that it should be possible to do this without any conditionals.

Regards,
Chris.

Pipeline stalls (because of branches) are machine dependent. Some cpu'sh
ave two pipelines, one for each branch, so it isn't an issue. I myself
prefer to use decisionless code, if at all possible. You might want
to see my article "Avoid Decisions!" in Computers in Physics ca. 1990
or 1991, which discusses the general idea. If you are doing it in
assembly it becomes easier, of course, but it is possible to avoid
(some) branches in high-level C.

--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"God is not willing to do everything and thereby take away
our free will and that share of glory that rightfully belongs
to us." -- N. Machiavelli, "The Prince".

 

[CBFalconer]

I'm trying to implement two routines to handle 32x32-bits and
64x64-bits signed integer multiplication on a 32 bits machine in C. It
easy to find descriptions of non-signed multiplication, however, I
haven't found any good descriptions for the signed counterpart.

Does any of you have a good reference for this topic?

Your grade III arithmetic text book?

 

[Richard Bos]

| What about:
| - for each signed number, check whether it's signed, check whether these
| signs are equal, and remember this fact.
| - set both sign bits to +.
| - multiply as if they're unsigned.
| - check whether the result is too large for a signed number, and if so,
| do what you've decided to do on overflow.
| - if the sign bits were equal, leave the number as it is. If they
| weren't, set its sign bit.

As I see it, this strategy involves some if/else-tests, which can harm
the pipeline throughput (or am I wrong?) . I've an intuitive feeling
that it should be possible to do this without any conditionals.

Well, reading the sign bits might be nothing but bitwise manipulations.
The rest certainly _can_ be done conditionless if multiplies are cheap.
For example:

#define SIGN_BIT ((unsigned type)CHAR_BIT*sizeof(signed type)-1)
signed type s_mult(signed type x, signed type y)
{
unsigned type ux,uy, sbx,sby, signbit;
signed type result;

ux=x; uy=y;
sbx=ux>>SIGN_BIT; sby=uy>>SIGN_BIT;
signbit=sbx^sby;
ux*=1-2*sbx; uy*=1-2*sby;
result=u_mult(ux, uy);
result*=1-2*signbit;

return result;
}

This does assume that your 32-bit type is or behaves as a normal C
integer, including the conversion of negative signed values to unsigned;
and the #define of SIGN_BIT assumes no trap bits, so if you have those,
you'll have to #define your own sign position. Oh, and it requires
<limits.h>, of course.

Richard

 

[Christopher Dyken]

| Your grade III arithmetic text book?

Unfortunately, I don't have this for reference, but either the
educational standards in Norway are particulary weak, or you went to
Mensa-camp or something as a kid, since I cannot recall learning
anything about casting between unsigned and signed ints as well as
signed binary numbers in ground school.

Sarcasm aside, the problem is not to expand (a*2^16+b)*(c*2^16+d) to
ac*2^32 + (ad+bc)*2^16 + bd, but how to program this correctly using
32-bits signed integers in C.


Regards,
Chris.

 

[CBFalconer]

| Your grade III arithmetic text book?

Unfortunately, I don't have this for reference, but either the
educational standards in Norway are particulary weak, or you went to
Mensa-camp or something as a kid, since I cannot recall learning
anything about casting between unsigned and signed ints as well as
signed binary numbers in ground school.

Sarcasm aside, the problem is not to expand (a*2^16+b)*(c*2^16+d) to
ac*2^32 + (ad+bc)*2^16 + bd, but how to program this correctly using
32-bits signed integers in C.

I don't know how Norway got into this, but what do you need to
know other than the multiplication table 1 x 1 = 1 and 1 x 0 = 0
and 0 x 0 = 0, together with the fact that like signs yield
positive products and unlike signs yield negative products. You
don't even have to worry about carries until you add partial
products. Get the data structure and algorithm right and the code
will fall out.

Tips: you can often improve things by breaking the operation up
and using results that conveniently fit into registers. Then a
final addition operation combines them all. Read Knuth.

 

[Christopher Dyken]

| I don't know how Norway got into this, but what do you need to

You referenced my grade III arithmetic book, and since I'm Norwegian,
and thus a product of the Norwegian School system, Norway got into
this.


| know other than the multiplication table 1 x 1 = 1 and 1 x 0 = 0
| and 0 x 0 = 0, together with the fact that like signs yield
| positive products and unlike signs yield negative products. You
| don't even have to worry about carries until you add partial
| products. Get the data structure and algorithm right and the code
| will fall out.

So what you suggest is to implement the bit-by-bit multiplication and
then try to lump together operations afterwards?


| Tips: you can often improve things by breaking the operation up
| and using results that conveniently fit into registers. Then a
| final addition operation combines them all. Read Knuth.

I browsed through Knuth (art of programming) at the library some days
ago. However, I couldn't find anything on signed multiplication (found
quite some stuff on unsigned, though). I think it was one of the early
editions.

Cheers,
Chris

 

[Joona I Palaste]

I don't know how Norway got into this, but what do you need to
know other than the multiplication table 1 x 1 = 1 and 1 x 0 = 0
and 0 x 0 = 0, together with the fact that like signs yield
positive products and unlike signs yield negative products. You
don't even have to worry about carries until you add partial
products. Get the data structure and algorithm right and the code
will fall out.

Christopher Dyken appears to be Norwegian.

 

[Christopher Dyken]

| Well, reading the sign bits might be nothing but bitwise manipulations.
| The rest certainly _can_ be done conditionless if multiplies are cheap.
| For example:[... code omitted ...]
| This does assume that your 32-bit type is or behaves as a normal C
| integer, including the conversion of negative signed values to unsigned;
| and the #define of SIGN_BIT assumes no trap bits, so if you have those,
| you'll have to #define your own sign position. Oh, and it requires
| <limits.h>, of course.

Thanks, that looks interesting! Hmmm, I wonder where the break-even
point between conditionals and multiplications is; well only some
timing will answer that.

Regards,
Chris.

 

[Peter Nilsson]

I'm trying to implement two routines to handle 32x32-bits and
64x64-bits signed integer multiplication on a 32 bits machine in C. It
easy to find descriptions of non-signed multiplication, however, I
haven't found any good descriptions for the signed counterpart.

If you mimic twos complement, then you can just use the unsigned
multiplication methods. BTW, don't assume specific widths for integer
types.

 

[Peter Nilsson]

Your grade III arithmetic text book?

[And Richard called _me_ churlish! ;-]

Granted the question wasn't really suitable for clc since it leaned
towards algorithms and a request for links (rather than discussing ISO
C directly), nonetheless, this response isn't exactly constructive.

Programming is not limited to people who 'did well at maths in
school'. Not every computational trick is 'intuitively obvious from
first principles'. Like most languages, C hides the tedious issues of
implementation of digit arithmetic (e.g. long is still 32+ bits on 8
and 16-bit machines).

Why do you think extending integer arithmetic is 'elementary'?

 

[CBFalconer]

| I don't know how Norway got into this, but what do you need to

You referenced my grade III arithmetic book, and since I'm Norwegian,
and thus a product of the Norwegian School system, Norway got into
this.

| know other than the multiplication table 1 x 1 = 1 and 1 x 0 = 0
| and 0 x 0 = 0, together with the fact that like signs yield
| positive products and unlike signs yield negative products. You
| don't even have to worry about carries until you add partial
| products. Get the data structure and algorithm right and the code
| will fall out.

So what you suggest is to implement the bit-by-bit multiplication and
then try to lump together operations afterwards?

| Tips: you can often improve things by breaking the operation up
| and using results that conveniently fit into registers. Then a
| final addition operation combines them all. Read Knuth.

I browsed through Knuth (art of programming) at the library some days
ago. However, I couldn't find anything on signed multiplication (found
quite some stuff on unsigned, though). I think it was one of the early
editions.

int neg;
unsigned long a, b;
whatever p; /* something that can hold a 64 bit product */
....
neg = (a < 0L) ^ (b < 0L));
p = product(labs(a), labs(b)); /* however you are doing it */
/* test p for overflow */
if (neg) p = negate(p);

you build product and negate.

 

[Mac]

| What about:
| - for each signed number, check whether it's signed, check whether these
| signs are equal, and remember this fact.
| - set both sign bits to +.
| - multiply as if they're unsigned.
| - check whether the result is too large for a signed number, and if so,
| do what you've decided to do on overflow.
| - if the sign bits were equal, leave the number as it is. If they
| weren't, set its sign bit.
| Hardest part is probably deciding what to do on overflow. Crashing is
| harsh. Ignoring is perhaps sufficient in many circumstances. Setting an
| error flag is probably best.

Hi Richard,

I have no problem limiting the input values (I define the interval
myself), and thus, I can be sure that no overflows occour. So this is
not an issue.

As I see it, this strategy involves some if/else-tests, which can harm
the pipeline throughput (or am I wrong?) . I've an intuitive feeling
that it should be possible to do this without any conditionals.

The turnaround on usenet can be kind of slow. It is worth your while to
compose messages with care. If you had a requirement for not using
conditionals, you should have mentioned it in your original post.

Regards,
Chris.

Mac

 

[Christopher Dyken]

[...formulate 32x32-bits signed multiplication...]

[...check sign and do unsigned...]

[...worry about conditionals...]

| The turnaround on usenet can be kind of slow. It is worth your while to
| compose messages with care. If you had a requirement for not using
| conditionals, you should have mentioned it in your original post.

I don't have any specific requirement for not using conditionals, this
fanatic reluctance of mine regarding conditionals is just a result of
my background. I started programming on a non-pipelined cpu, where
only the number of cycles counted. Then I started with pipelined cpus
where a wrong branch predicition would cause a pipeline flush, and
thus should be avoided (if cheap). I'm not sure what the status is for
current architectures are, have to do some research.

However, this threads starts to wander into the realm of philosophy of
algorithm formulation. Not sure if this is appropriate for c.l.c.

Cheers,
Chris.

 

[Richard Bos]

(e-mail address removed) (Richard Bos) writes:
| This does assume that your 32-bit type is or behaves as a normal C
| integer, including the conversion of negative signed values to unsigned;
| and the #define of SIGN_BIT assumes no trap bits, so if you have those,
| you'll have to #define your own sign position. Oh, and it requires
| <limits.h>, of course.

Thanks, that looks interesting! Hmmm, I wonder where the break-even
point between conditionals and multiplications is; well only some
timing will answer that.

Quite. Be prepared for the difference to be smaller than the measurement
error, too.

Richard

 

[Bill Hanna]

Hi group,

I'm trying to implement two routines to handle 32x32-bits and
64x64-bits signed integer multiplication on a 32 bits machine in C. It
easy to find descriptions of non-signed multiplication, however, I
haven't found any good descriptions for the signed counterpart.

Does any of you have a good reference for this topic?

Thanks in advance,
Chris.

The limitation of 32X32 in C is that the result is limited to 32
bits (the lower half result). The correct result is 64 bits. The full
64 bit result can only be obtained by breaking the operands into 16
bit sections and performing partial multiplies and long long sums (64
bit) to obtain the full 64 bit result. This increases the execution
time compared to the 32x32 -> 32 bit result.

Bill Hanna

 

[glen herrmannsfeldt]

(snip)

Sarcasm aside, the problem is not to expand (a*2^16+b)*(c*2^16+d) to
ac*2^32 + (ad+bc)*2^16 + bd, but how to program this correctly using
32-bits signed integers in C.

John R. Ehrman: Correction to ``logical'' arithmetric on computers with
two's complement binary arithmetic. Commun. ACM 13(11): 697-698 (1970)

John R. Ehrman: "Logical" arithmetic on computers with two's complement
binary arithmetic. Commun. ACM 11(7): 517-520 (1968)

-- glen