Re: [ft-devel] FT_MulDiv optimization

[Alexei Podtelezhnikov]

On Fri, Jul 4, 2014 at 6:12 AM, Werner LEMBERG <address@hidden> wrote:

>> Well, at the same time it reduces the available range for `c' by
>> more than 50%.
>
> I was greedy with the space for a and b. With a + b < 2*46340
> instead, c can use the same old limit. We can expand c a lot further
> by making a+b only a bit smaller.

OK.  Another reason for a statistical analysis :-)

You force me to think, man. To avoid any overflow it is sufficient to satisfy this inequality

a + b < 2 * sqrt(X - c/2)

where X is 2^31 - 1. Using Taylor series it can replaces with a *stronger* inequality

a + b < 2 * sqrt(X)  - c / (2 * sqrt(X))

or

a + b < 92681.9 - c / 92681.9

Now we get rid of impractical division

a + b < 92681.9 - (c >> 16) + (c >> 18)

where the right side got a bit smaller again as the denominator became 87381.3. We can finally turn the whole thing integer

a + b < 92681 - (c >> 16) + ((c+ 235935) >> 18)

Therefore, we do not need a special limit on c. The whole thing becomes more permissive.