top 32 bits of 64-bit product of two 32-bit integers
Author Message
top 32 bits of 64-bit product of two 32-bit integers

I would be interested if any of {C,C++,fortran90} can do the following:

AFAIK, most modern CPUs calculate the product of two unsigned 32-bit integers
as a 64-bit integer, and return the bottom 32-bits.  Is there a fast way to
access the top 32 bits of that product in {C,C++,Fortran90}, or is there a
quick way to access the assembly language routine that does so?  Or is the
only way to do this to use the "doubled-precision-multiply" technique:

top32(A*B) =    top16( top16( bot16(A)*bot16(B) )
+ bot16(A)*top16(B)
+ top16(A)*bot16(B) )
+ top16(A)*top16(B)

And would the resulting code be somewhat portable?  How about getting the top
64 bits of the 128-bit product of two 64-bit integers [I work on a DEC Alpha
AXP running OSF/1]?

I don't want to start flame wars, I'm just curious!  Given a task, I use
whatever tool works to get the task done, so I have no emotional involvement

E-mail replies appreciated.  I'll summarize if there is interest.
Thanks,
--
-- Ted
------------------------------------------------------------------------------
Dept. of Applied Math, FS-20    University of Washington    Seattle, WA  98195

------------------------------------------------------------------------------

Mon, 21 Apr 1997 02:45:22 GMT
top 32 bits of 64-bit product of two 32-bit integers

> I would be interested if any of {C,C++,Fortran90} can do the
> following:

> AFAIK, most modern CPUs calculate the product of two unsigned 32-bit
> integers as a 64-bit integer, and return the bottom 32-bits.  Is
> there a fast way to access the top 32 bits of that product in
> {C,C++,Fortran90}, or is there a quick way to access the assembly
> language routine that does so?

There is in some compilers, using non-standard extensions, such as embedded
assembly code, or you can call a separate assembly routine.

> Or is the
> only way to do this to use the "doubled-precision-multiply" technique:

>         top32(A*B) =    top16( top16( bot16(A)*bot16(B) )
>                              + bot16(A)*top16(B)
>                              + top16(A)*bot16(B) )
>                       + top16(A)*top16(B)

> And would the resulting code be somewhat portable?

That is the portable way to do it.  Note, however, that this definition isn't
suitable for implementation, because of possible overflow.  Here is an
implementation that should be portable:

/* ISO C 32x32 to 64 bit unsigned multiply */

#define LOW16(x)    ((x) & 0xffff)
#define HIGH16(x)   (((x)>>16) & 0xffff)

/* mpy32 returns the full product of two 32-bit integers.
** It should work with any ISO-compliant C compiler.
*/
void mpy32 (
unsigned long a,    /* multiplicand, 0 - (2^32-1) */
unsigned long b,    /* multiplier,   0 - (2^32-1) */
unsigned long *ph,  /* MS 32 bits of a*b */
unsigned long *pl   /* LS 32 bits of a*b */
) {
unsigned long pm;   /* intermediate term */

*pl = LOW16(a) * LOW16(b);
pm  = HIGH16(a) * LOW16(b);
*ph = HIGH16(a) * HIGH16(b) + HIGH16(pm);
pm  = LOW16(pm) + LOW16(a) * HIGH16(b) + HIGH16(*pl);
*ph+= HIGH16(pm);
*pl = (LOW16(pm) << 16) + LOW16(*pl);

Quote:
}

> How about getting the top 64 bits of the 128-bit product of two
> 64-bit integers [I work on a DEC Alpha AXP running OSF/1]?

Same concept, same technique.
--

|
| Standard disclaimer: The views of this user are strictly his own!
| From High Mountain Software & The Bailey Information Exchange BBS
| +1 303 674 0147, Bailey, Colorado, USA 1200-14400 Baud 8N1 24 Hrs
| Gateway Info: Fidonet: 1:104/825.0 (.10), Internet Domain: hms.com

Wed, 23 Apr 1997 07:39:14 GMT
top 32 bits of 64-bit product of two 32-bit integers

Quote:
> AFAIK, most modern CPUs calculate the product of two unsigned 32-bit integers
> as a 64-bit integer, and return the bottom 32-bits.  Is there a fast way to
> access the top 32 bits of that product in {C,C++,Fortran90}, or is there a
> quick way to access the assembly language routine that does so?  Or is the
> only way to do this to use the "doubled-precision-multiply" technique:

>         top32(A*B) =    top16( top16( bot16(A)*bot16(B) )
>                              + bot16(A)*top16(B)
>                              + top16(A)*bot16(B) )
>                       + top16(A)*top16(B)

> And would the resulting code be somewhat portable?  How about getting the top
> 64 bits of the 128-bit product of two 64-bit integers [I work on a DEC Alpha
> AXP running OSF/1]?

A general multiple precision integer solution: write your own package for it
or get one already written (g++/GNU C++ comes with an Integer class, which
seems to work fine for very very large integers).

For an AXP solution: On an AXP running VMS, then you can in C use the type
__int64, or in FORTRAN (FORTRAN77) use the type INTEGER*8, both will give
you a full 64 bit integer.

Arne

Arne Vajh?j                             local DECNET:  KO::ARNE
Computer Department                     PSI:           PSI%238310013040::ARNE

Tue, 22 Apr 1997 01:14:10 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages