James Kanze wrote:

> On Jul 2, 4:29 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
>> Default User wrote:
>> > If I have three 64 bit integers and I want to do this
>> > operation on them:
>
>> > x*y/z
>
>> > Lets say that what we are multiplying by (y) is offset by
>> > what we are dividing by (z) so that the final answer will
>> > fit in a 64-bit integer.
>
>> > Let me simplify it by using unsigned chars (8 bits):
>
>> > 254*253/252 = 255
>
>> > But, if we only had 8 bit integers to work with, is there an
>> > algorithm that would use 8 bit integers only to come up with
>> > the right answer of 255 ? The obvious problem is that the
>> > multiplication yields a number much larger than an 8-bit
>> > integer.
>
>> > Where I am going with this is that sometimes I need to
>> > multiply and divide large 64-bit integers and as long as the
>> > resulting number fits in a 64-bit integer, can I do this
>> > with 64-bit integers alone?
>
>> It might be easier (and maybe also more efficient) to use
>> double or long double for the computation and then case back
>> (provided they have more than 64 bit mantissa on your target
>> platform).
>
> Do you know of such a platform? The intermediate value he's
> concerned with can have up to 127 bits, so you'd need a mantissa
> of 127 bits. I think some have existed (perhaps some of the old
> CDC mainframes), but I don't know of any today.

I actually had thought about this before I posted, and you don't need 127
bits mantissa. However, in order to see that, we have to take the OP
serious on his claim that the result will fit into a 64 bit number. Let me
illustrate what happens with decimals. Suppose, we are dealing with 5-digit
decimals in the range [0,99999]. We want to compute a*b/c for such numbers
(truncated to the integral part). Let's assume we have the quotient b/c to
7 decimals (not 10!). Then, the product a*(b/c) is of one of the following
forms:

a * b/c

xxxxx * x.xxxxxx
0xxxx * xx.xxxxx
00xxx * xxx.xxxx
000xx * xxxx.xxx
0000x * xxxxx.xx

If the leading digits are any farther to the left, the product will exceed
10000.

Now observe that a change in the last digit of b/c changes the product
a*(b/c) less than 1. Therefore, it is not a priori hopeless to try to get
the integral part of a*(b/c) via this method. If we throw in one more digit
of precision, we can get within distance 0.1 of the product, which should
be good enough to determine the integral part. I did not carry out a
complete analysis; but based upon the above, I conjecture that a mantissa
of 68 bits will be enough (getting within distance 0.01(binary) of the
product).

Now, looking up floating point formats, I do realize that the OP might still
be out of luck. It appears that quadruple precision is needed.


>> However, there could be some tricky analysis involved to prove
>> the code correct.
>
> *If* the conditions are exactly as he stated, then it's easy to
> prove the code incorrect (and even find example values which
> would fail a test) for IEEE double, or any representation which
> uses less than 127 bits in the mantissa.

It's far from easy to prove incorrectness; it is also far from easy to prove
correctness, though. The heuristic above illustrates some of the
intricacies that one will run into.


Best

Kai-Uwe Bux