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
in the answer.

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.
--
|Fidonet:  Thad Smith 1:104/825.14

|
| 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  
 
 [ 3 post ] 

 Relevant Pages 

1. 64-bit integer on a 32-bit machine

2. REQUEST: 64-bit integer math on 32-bit processor

3. Looking for: multiply and divide of 32 bit integers (64 bit result)

4. Help: porting 32-bit app to 64-bit Dec Alpha

5. Calling 64 bit lib. from 32 bit program

6. emulating a 64 bit divide with 2 32 bit registers in ansi c

7. converting signed 64 bit - 32 bit

8. 64 bit operation on 32 bit PC

9. 64-bit chips, 32-bit compatibility?

10. Accessing 32-bit com componet from 64-bit application

11. 32-bit vs 64-bit

12. Tool 2 port 32 bit programms 2 64 bit

 

 
Powered by phpBB® Forum Software