# 32x32 and 64x64 signed integer multiplication

Discussion in 'C Programming' started by Christopher Dyken, Feb 17, 2004.

1. ### Christopher DykenGuest

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?

Chris.

--

Christopher Dyken, Feb 17, 2004

2. ### Richard BosGuest

Christopher Dyken <> wrote:

> 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.

- 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

Richard Bos, Feb 17, 2004

3. ### Christopher DykenGuest

(Richard Bos) writes:
| Christopher Dyken <> wrote:
>
>> 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.

>

| - 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.

--

Christopher Dyken, Feb 17, 2004
4. ### Julian V. NobleGuest

Christopher Dyken wrote:
>
> (Richard Bos) writes:
> | Christopher Dyken <> wrote:
> >
> >> 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.

> >

> | - 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.
>
> --
> email address available at http://www.ifi.uio.no/~erikd/index.cgi

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

^^^^^^^^^^^^^^^^^^
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".

Julian V. Noble, Feb 17, 2004
5. ### CBFalconerGuest

Christopher Dyken wrote:
>
> 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?

--
Chuck F () ()
Available for consulting/temporary embedded and systems.

CBFalconer, Feb 17, 2004
6. ### Richard BosGuest

Christopher Dyken <> wrote:

> (Richard Bos) writes:
> | Christopher Dyken <> wrote:
> >
> >> 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.

> >

> | - 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

Richard Bos, Feb 17, 2004
7. ### Christopher DykenGuest

CBFalconer <> writes:

| Christopher Dyken wrote:
>>
>> 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?

>

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.

--

Christopher Dyken, Feb 17, 2004
8. ### CBFalconerGuest

Christopher Dyken wrote:
> CBFalconer <> writes:
> | Christopher Dyken wrote:
> >>
> >> 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?

> >

>
> 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
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

--
Chuck F () ()
Available for consulting/temporary embedded and systems.

CBFalconer, Feb 17, 2004
9. ### Christopher DykenGuest

CBFalconer <> writes:
| Christopher Dyken wrote:
>> CBFalconer <> writes:
>> | Christopher Dyken wrote:
>> >>
>> >> 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?
>> >

>>
>> 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

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

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

--

Christopher Dyken, Feb 17, 2004
10. ### Joona I PalasteGuest

CBFalconer <> scribbled the following:
> Christopher Dyken wrote:
>> CBFalconer <> writes:
>>
>> 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.

> 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.

--
/-- Joona Palaste () ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"It's time, it's time, it's time to dump the slime!"
- Dr. Dante

Joona I Palaste, Feb 17, 2004
11. ### Christopher DykenGuest

(Richard Bos) writes:
>> 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:
>

[... 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

Regards,
Chris.

--

Christopher Dyken, Feb 17, 2004
12. ### Peter NilssonGuest

Christopher Dyken <> wrote in message news:<>...
>
> 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

Peter Nilsson, Feb 18, 2004
13. ### Peter NilssonGuest

CBFalconer <> wrote in message news:<>...
> Christopher Dyken wrote:
> >
> > 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?

>

[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'?

--
Peter

Peter Nilsson, Feb 18, 2004
14. ### CBFalconerGuest

Christopher Dyken wrote:
> CBFalconer <> writes:
> | Christopher Dyken wrote:
> >> CBFalconer <> writes:
> >> | Christopher Dyken wrote:
> >> >>
> >> >> 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?
> >> >
> >>
> >> 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
>
> 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
>
> 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.

--
Chuck F () ()
Available for consulting/temporary embedded and systems.

CBFalconer, Feb 18, 2004
15. ### MacGuest

On Tue, 17 Feb 2004 15:14:47 +0100, Christopher Dyken wrote:

> (Richard Bos) writes:
> | Christopher Dyken <> wrote:
>>
>>> 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.

>>

> | - 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

Mac, Feb 18, 2004
16. ### Christopher DykenGuest

[OT] Re: 32x32 and 64x64 signed integer multiplication

"Mac" <> writes:
| On Tue, 17 Feb 2004 15:14:47 +0100, Christopher Dyken wrote:
>
>> (Richard Bos) writes:
>> | Christopher Dyken <> wrote:
>>> [...formulate 32x32-bits signed multiplication...]

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

| 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.

--

Christopher Dyken, Feb 18, 2004
17. ### Richard BosGuest

Christopher Dyken <> wrote:

> (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

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

Richard

Richard Bos, Feb 18, 2004
18. ### Bill HannaGuest

Christopher Dyken <> wrote in message news:<>...
> 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?
>
> 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

Bill Hanna, Feb 21, 2004
19. ### glen herrmannsfeldtGuest

(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

glen herrmannsfeldt, Feb 24, 2004