P: n/a

Hi group,
I'm trying to implement two routines to handle 32x32bits and
64x64bits signed integer multiplication on a 32 bits machine in C. It
easy to find descriptions of nonsigned 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.

email address available at http://www.ifi.uio.no/~erikd/index.cgi  
Share this Question
P: n/a

Christopher Dyken <fo****@uio.no> wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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  
P: n/a
 rl*@hoekstrauitgeverij.nl (Richard Bos) writes:
 Christopher Dyken <fo****@uio.no> wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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.
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/elsetests, 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  
P: n/a

Christopher Dyken wrote: rl*@hoekstrauitgeverij.nl (Richard Bos) writes:  Christopher Dyken <fo****@uio.no> wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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.
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/elsetests, 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 highlevel C.

Julian V. Noble
Professor Emeritus of Physics jv*@lessspamformother.virginia.edu
^^^^^^^^^^^^^^^^^^ 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".  
P: n/a

Christopher Dyken wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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?

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!  
P: n/a

Christopher Dyken <fo****@uio.no> wrote: rl*@hoekstrauitgeverij.nl (Richard Bos) writes:  Christopher Dyken <fo****@uio.no> wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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.
As I see it, this strategy involves some if/elsetests, 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*=12*sbx; uy*=12*sby;
result=u_mult(ux, uy);
result*=12*signbit;
return result;
}
This does assume that your 32bit 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  
P: n/a

CBFalconer <cb********@yahoo.com> writes:
 Christopher Dyken wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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?
Unfortunately, I don't have this for reference, but either the
educational standards in Norway are particulary weak, or you went to
Mensacamp 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
32bits signed integers in C.
Regards,
Chris.

email address available at http://www.ifi.uio.no/~erikd/index.cgi  
P: n/a

Christopher Dyken wrote: CBFalconer <cb********@yahoo.com> writes:  Christopher Dyken wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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?
Unfortunately, I don't have this for reference, but either the educational standards in Norway are particulary weak, or you went to Mensacamp 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 32bits 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.

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!  
P: n/a

CBFalconer <cb********@yahoo.com> writes:
 Christopher Dyken wrote: CBFalconer <cb********@yahoo.com> writes:  Christopher Dyken wrote: >> >> I'm trying to implement two routines to handle 32x32bits and >> 64x64bits signed integer multiplication on a 32 bits machine in C. It >> easy to find descriptions of nonsigned 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?
Unfortunately, I don't have this for reference, but either the educational standards in Norway are particulary weak, or you went to Mensacamp 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 32bits 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. :P
 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 bitbybit 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

email address available at http://www.ifi.uio.no/~erikd/index.cgi  
P: n/a

CBFalconer <cb********@yahoo.com> scribbled the following: Christopher Dyken wrote: CBFalconer <cb********@yahoo.com> writes:  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 Mensacamp 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 (pa*****@cc.helsinki.fi)  Finland \
\ http://www.helsinki.fi/~palaste  rules! /
"It's time, it's time, it's time to dump the slime!"
 Dr. Dante  
P: n/a
 rl*@hoekstrauitgeverij.nl (Richard Bos) writes: As I see it, this strategy involves some if/elsetests, 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 32bit 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 breakeven
point between conditionals and multiplications is; well only some
timing will answer that. :)
Regards,
Chris.

email address available at http://www.ifi.uio.no/~erikd/index.cgi  
P: n/a

Christopher Dyken <fo****@uio.no> wrote in message news:<x6*************@lachesis.uio.no>... I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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  
P: n/a

CBFalconer <cb********@yahoo.com> wrote in message news:<40***************@yahoo.com>... Christopher Dyken wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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?
[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 16bit machines).
Why do you think extending integer arithmetic is 'elementary'?

Peter  
P: n/a

Christopher Dyken wrote: CBFalconer <cb********@yahoo.com> writes:  Christopher Dyken wrote: CBFalconer <cb********@yahoo.com> writes:  Christopher Dyken wrote: >> >> I'm trying to implement two routines to handle 32x32bits and >> 64x64bits signed integer multiplication on a 32 bits machine in C. It >> easy to find descriptions of nonsigned 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?
Unfortunately, I don't have this for reference, but either the educational standards in Norway are particulary weak, or you went to Mensacamp 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 32bits 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. :P
 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 bitbybit 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.

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!  
P: n/a

On Tue, 17 Feb 2004 15:14:47 +0100, Christopher Dyken wrote: rl*@hoekstrauitgeverij.nl (Richard Bos) writes:  Christopher Dyken <fo****@uio.no> wrote: I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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.
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/elsetests, 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  
P: n/a

Christopher Dyken <fo****@uio.no> wrote: rl*@hoekstrauitgeverij.nl (Richard Bos) writes:  This does assume that your 32bit 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 breakeven 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  
P: n/a

Christopher Dyken <fo****@uio.no> wrote in message news:<x6*************@lachesis.uio.no>... Hi group,
I'm trying to implement two routines to handle 32x32bits and 64x64bits signed integer multiplication on a 32 bits machine in C. It easy to find descriptions of nonsigned 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  
P: n/a

(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 32bits signed integers in C.
John R. Ehrman: Correction to ``logical'' arithmetric on computers with
two's complement binary arithmetic. Commun. ACM 13(11): 697698 (1970)
John R. Ehrman: "Logical" arithmetic on computers with two's complement
binary arithmetic. Commun. ACM 11(7): 517520 (1968)
 glen   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 7323
 replies: 17
 date asked: Nov 14 '05
