Looking for: multiply and divide of 32 bit integers (64 bit result) 
Author Message
 Looking for: multiply and divide of 32 bit integers (64 bit result)

I am looking for any decent implementation (in C) that does multiply and
divide in the 64 bit domain.

(No, this is not for a homework assignment!)

So, when I multiply two 32 bit quantities, I want a 64 bit number, and I
need to be able to divide a 64 bit quantity by a 32 bit quantity...

I'm sure somebody has done this before, so if you know of any public
domain code, please let me know...thanks....
--
----
Avinash Chopde



Wed, 27 Nov 1996 02:51:37 GMT  
 Looking for: multiply and divide of 32 bit integers (64 bit result)

Quote:

>I am looking for any decent implementation (in C) that does multiply and
>divide in the 64 bit domain.

>So, when I multiply two 32 bit quantities, I want a 64 bit number, and I
>need to be able to divide a 64 bit quantity by a 32 bit quantity...

See the following for most of what you need:

Baker, H.G.  Computing A*B (mod N) Efficiently in ANSI C.  ACM Sigplan Not.
27,1 (Jan 1992), 95-98.



Wed, 27 Nov 1996 12:10:01 GMT  
 Looking for: multiply and divide of 32 bit integers (64 bit result)

| I am looking for any decent implementation (in C) that does multiply and
| divide in the 64 bit domain.

Here are some routines that I recently wrote that handle unsigned 64 bit
quantities.  The multiplication and division routines are based on assembly
langage algorithms.  Overflow and other mathematical errors are not
handled.

I have been told that these routines are "slow."  I suppose that the next
step in speeding them up would be unrolling a few of the loops, but I
haven't gotten around to that yet.

You are free to use them, but make sure that I retain credit.
---------------------------------------------------------------------------

#ifndef MATH64_H
#define MATH64_H

typedef struct int64_tag {
    unsigned short int v[4];

Quote:
} int64, *int64p;

int64 dcl64(unsigned short int a, unsigned short int b, unsigned short int c, unsigned short int d);
int cmp64 (int64 x, int64 y);

int64 add64 (int64 x, int64 y);
int64 sub64 (int64 x, int64 y);
int64 mul64 (int64 x, int64 y);
int64 div64 (int64 x, int64 y);

unsigned long int int64_to_ulong (int64 x);
int64 ulong_to_int64 (unsigned long int x);

#endif /* MATH64_H */
---------------------------------------------------------------------------

typedef struct int64_tag {
    unsigned short int v[4];

Quote:
} int64, *int64p;

int64 dcl64 (unsigned short int a, unsigned short int b, unsigned short int c, unsigned short int d)
{
    int64 z;

    z.v[0] = a;
    z.v[1] = b;
    z.v[2] = c;
    z.v[3] = d;
    return z;

Quote:
} /* dcl64 */

int cmp64 (int64 x, int64 y)
{
    int i, result;

    for (i = 4; i > 0; i--)
    {
        if (x.v[i-1] > y.v[i-1])
        {
            result = 1;
            i = 0;
        }
        else if (x.v[i-1] < y.v[i-1])
        {
            result = -1;
            i = 0;
        }
        else
        {
            result = 0;
        }
    }
    return result;

Quote:
} /* cmp64 */

int64 add64 (int64 x, int64 y)
{
    int i;
    unsigned long int temp;
    int64 z;

    temp = (unsigned lont int) 0;

    for (i = 0; i < 4; i++)
    {
        temp = (unsigned long int) (x.v[i] + y.v[i] + (temp >> 16));
        z.v[i] = (unsigned short int) temp;
    }
    return z;

Quote:
} /* add64 */

int64 sub64 (int64 x, int64 y)
{
    int i, borrow;
    unsigned long int temp;
    int64 z;

    for (i = 0; i < 4; i++)
    {
        if (x.v[i] < y.v[i] && i != 3)
        {
            x.v[i+1]--;
            borrow = 1;
        }
        else
        {
            borrow = 0;
        }

        temp = (unsigned long int) (x.v[i] + (borrow << 16) - y.v[i]);
        z.v[i] = (unsigned short int) temp;
    }
    return z;

Quote:
} /* sub64 */

int64 mul64 (int64 x, int64 y)
{
    int i, j, carry;
    unsigned long int temp;
    int64 z;

    z = dcl64 (0, 0, 0, 0);

    for (j = 0; j < 64; j++)
    {
        carry = 0;
        for (i = 0; i < 4; i++)
        {
            temp = (unsigned long int) ((z.v[i] << 1) + carry);
            carry = z.v[i] >> 15;
            z.v[i] = (unsigned short int) temp;
        }

        carry = 0;
        for (i = 0; i < 4; i++)
        {
            temp = (unsigned long int) ((x.v[i] << 1) + carry);
            carry = x.v[i] >> 15;
            x.v[i] = (unsigned short int) temp;
        }

        if (carry)
        {
            z = add64 (z, y);
        }
    }
    return z;

Quote:
} /* mul64 */

int64 div64 (int64 x, int64 y)
{
    int i, j, carry;
    unsigned long int temp;
    int64 r, z;

    r = dcl64 (0, 0, 0, 0);
    z = dcl64 (0, 0, 0, 0);

    for (j = 0; j < 64; j++)
    {
        carry = 0;
        for (i = 0; i < 4; i++)
        {
            temp = (unsigned long int) ((x.v[i] << 1) + carry);
            carry = x.v[i] >> 15;
            x.v[i] = (unsigned short int) temp;
        }

        for (i = 0; i < 4; i++)
        {
            temp = (unsigned long int) ((r.v[i] << 1) + carry);
            carry = r.v[i] >> 15;
            r.v[i] = (unsigned short int) temp;
        }

        if (cmp64 (r, y) >= 0)
        {
            carry = 1;
            r = sub64 (r, y);
        }
        else
        {
            carry = 0;
        }

        for (i = 0; i < 4; i++)
        {
            temp = (unsigned long int) ((z.v[i] << 1) + carry);
            carry = z.v[i] >> 15;
            z.v[i] = (unsigned short int) temp;
        }
    }
    return z;

Quote:
} /* div64 */

unsigned long int int64_to_ulong (int64 x)
{
    unsigned long int z;

    z = (unsigned long int) (x.v[0] + (x.v[1] << 16));
    return z;

Quote:
} /* int64_to_ulong */

int64 ulong_to_int64 (unsigned long int x)
{
    int64 z;
    unsigned short int a, b;

    a = (unsigned short int) x;
    b = (unsigned short int) (x >> 16);

    z = dcl64 (a, b, 0, 0);
    return z;

Quote:
} /* ulong_to_int64 */

---------------------------------------------------------------------------
| --
| Avinash Chopde

--
Sean Dockery                        |  Tickle us, do we not laugh?
Griffin Software Development Group  |  {*filter*} us, do we not bleed?



Wed, 27 Nov 1996 19:08:38 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. top 32 bits of 64-bit product of two 32-bit integers

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

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

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

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

6. Calling 64 bit lib. from 32 bit program

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