function to perform a * b / c in long int format

[Frank Mikkelsen]

Hello group
I am looking for a function written in standard C witch can perform the a
* b / c on a long int without loosing any bits. a * b can exceed 32 bits
and if I carst a,b and c to floats I will still loos precision on the last
bits.
My compiler only supports 4 byte long int and 4 byte float
hope someone can help me

Frank

 

[Eric Sosman]

Hello group
I am looking for a function written in standard C witch can perform the a
* b / c on a long int without loosing any bits. a * b can exceed 32 bits
and if I carst a,b and c to floats I will still loos precision on the last
bits.
My compiler only supports 4 byte long int and 4 byte float
hope someone can help me

If your compiler supports `long long', that'd be
the easiest to implement and would give "perfect" results.

Failing that, does your compiler provide a `double'
that's significantly more precise than `float'? On most
machines `double' isn't large enough to handle `int * int'
with perfect accuracy, but you could get awfully close
with (pseudocode; little matters like signs ignored):

double r = (double)max(a, b) / c;
return (int)(r * min(a, b));

Failing even that, look for a "big number" package;
see the FAQ for some suggestions. Most such packages
are overkill in the sense that they provide "unlimited"
precision whereas you need only double precision, but
some may have double-precision specializations -- or you
could just go ahead and accept the overhead.

And, of course, there's the "roll your own" method.

A lot depends on what the calculation is being used
for. If you're doing something like data compression or
cryptography, say, you need a solution that gives perfect
accuracy in every bit. If you're rescaling an image that's
going to go through anti-aliasing anyhow, you can afford
a little bit of wiggle in the low-order bits; the "double
as ratio" approach might be good enough.

 

[Mike Deskevich]

since i don't know the details of your calculation, i don't know if
this will be helpful. but if b is much larger than c, then you might
be able to get away with

tmp=b/c;
result=a*tmp;

this way it doesn't matter if a*b is too big. but if b is smaller than
c, or even the same order of magnitude as c, then you'd lose precision
in the division step.

i don't know if that's much help or not.

 

[CBFalconer]

I am looking for a function written in standard C witch can
perform the a * b / c on a long int without loosing any bits.
a * b can exceed 32 bits and if I carst a,b and c to floats I
will still loos precision on the last bits.

My compiler only supports 4 byte long int and 4 byte float
hope someone can help me

Look into the div() function (stdlib.h) operating on a and c, and
on b and c. If the remainders are zero you only need to multiply
the quotients. If not, consider making corrections based on the
remainders and the original values. This should work as long as
the original expression does not cause an overflow. You do the
algebra.

 

[Tim Rentsch]

I am looking for a function written in standard C witch can perform the a
* b / c on a long int without loosing any bits. a * b can exceed 32 bits
and if I carst a,b and c to floats I will still loos precision on the last
bits.
My compiler only supports 4 byte long int and 4 byte float
hope someone can help me

I believe the function mldv( a, b, c ) below will calculate a * b / c,
for unsigned arguments, as long as the result fits in an unsigned long.
It also calculates the remainder (variable 'rr') if you should happen
to want that.

If you want signed arithmetic, I leave that as an exercise to the
reader.


unsigned int
mldv( unsigned int a_in, unsigned int b, unsigned int c ){
unsigned int q = b / c;
unsigned int r = b % c;
unsigned int a = a_in;
unsigned int rq = 0;
unsigned int rr = 0;

while( a ){
if( a & 1 ){
rq += q;
if( rr < c - r ) rr += r;
else rr -= c - r, rq += 1;
}

q <<= 1;
if( r < c - r ) r += r;
else r -= c - r, q += 1;

a >>= 1;
}

return rq;
}