On Jul 2, 7:16am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
> Default User wrote:
> > Hi,
>
> >> There's the MulDiv function from Windows, which is implemented in ReactOS
> >>http://www.reactos.org/generated/dox...8c-source.html
>
> > Thanks for the ideas guys, this is basically what I am looking for, but
> > this code counts on RtlEnlargedUnsignedDivide which in turn counts on
> > (ULONGLONG).
>
> > I realize there are bignum libraries out there, but I am really only
> > looking
> > for a small single algorithm to do this. I will be dealing with integers
> > only, and in such a way that I balance the Numerator/Denominator so thatI
> > know the result will fit properly.
>
> > In this case I am looking to make 64 bit integers perform 128 bit like
> > multiplication/division, but I would think I could easily adapt code
> > designed to make 32 bit integers perform 64 bit like
> > multiplication/division. Does anyone have any simple/short code made 64
> > bit integers from 32 bit integers, from a time before 64 bit integers were
> > available natively in the compiler?
>
> Addition is easy.
>
> Multiplication can be done like so: split the 64bit factors into high and
> low unsinged longs of 32 bits. Then you have to compute
>
> ( a * 2^32 + b ) * ( c * 2^32 + d )
> =
> a*c *2^64
> +
> (a-b)*(d-c) *2^32
> +
> a*c *2^32
> +
> b*d *2^32
> +
> c*d;
>
> which requires computing the three 64bit products ac, (a-b)(d-c), and cd.
> The rest is bit shifting and addition (which we agreed is easy :-).
>
> Alternatively, you could also do:
>
> ( a * 2^32 + b ) * ( c * 2^32 + d )
> =
> a*c *2^64
> +
> a*d *2^32
> +
> b*c *2^32
> +
> b*d
>
> which requires computing four 64bit products but is slightly less demanding
> on additions and bit shifting (also it does not involve dealing with
> differences).
>
> The tricky part is division. I have no idea how to do that efficiently.
>
> > The calculations I am trying to perform can be done in double, but it is
> > 150 times slower according to some testing I've done which is why I'd
> > rather stick to integers if I can.
>
> 150 times slower compared to what? If you already have a solution that beats
> floating point arithmetic by a factor of 150, you are probably all set and
> it won't get any better. If you don't, you seem to be comparing a solution
> to a non-solution.
>
> Best
>
> Kai-Uwe Bux

not sure but if one splits the 128-bit product in to 64-bit digits:

int64 proH,proL;

then (s)he might be able to use the algorithm that has been used - for
hundreds of years - to manually calculate the decimal division of
numbers.I am a computer generation guy and do not remember how I used
to divide two numbers in primary school mathematics course but
somebody must remember it.

regards,
FM.