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:

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)
{
}
}
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

 Page 1 of 1 [ 3 post ]

Relevant Pages