[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ft-devel] FT_MulDiv optimization
From: |
Behdad Esfahbod |
Subject: |
Re: [ft-devel] FT_MulDiv optimization |
Date: |
Fri, 04 Jul 2014 16:41:26 -0400 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0 |
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/
- Re: [ft-devel] FT_MulDiv optimization, (continued)
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Alexei Podtelezhnikov, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Behdad Esfahbod, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Behdad Esfahbod, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Alexei Podtelezhnikov, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Behdad Esfahbod, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Alexei Podtelezhnikov, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization,
Behdad Esfahbod <=
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Alexei Podtelezhnikov, 2014/07/04
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/05
- Re: [ft-devel] FT_MulDiv optimization, Alexei Podtelezhnikov, 2014/07/05
- Re: [ft-devel] FT_MulDiv optimization, Werner LEMBERG, 2014/07/08