Re: [ft-devel] FT_MulDiv optimization

[Behdad Esfahbod]

On 14-07-04 03:59 PM, Alexei Podtelezhnikov wrote:
> 
> On Fri, Jul 4, 2014 at 3:30 PM, Behdad Esfahbod <address@hidden
> <mailto:address@hidden>> wrote:
> 
>     On 14-07-04 03:09 PM, Alexei Podtelezhnikov wrote:
>     >
>     >
>     > 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.
> 
>     You could write it with <= instead of <.  No?
> 
>     How about the simpler:
> 
>     a + b <= 92681 - (c >> 16)
> 
>     This has the same number of operations as my previous patch, but more
>     permissive for all practical purposes though not *completely* covering the
>     previous case.
> 
> I agree. The short version is kinda beautiful. It should not overflow by
> itself like this
> 
> (FT_ULong)a + (FT_ULong)b < 92681UL - ((FT_ULong)c >> 16)

Very good point.

-- 
behdad
http://behdad.org/