|
From: | Alexei Podtelezhnikov |
Subject: | Re: [ft-devel] FT_MulDiv optimization |
Date: | Fri, 4 Jul 2014 15:59:13 -0400 |
On 14-07-04 03:09 PM, Alexei Podtelezhnikov wrote:You could write it with <= instead of <. No?
>
>
> 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.
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.
[Prev in Thread] | Current Thread | [Next in Thread] |