bug-grep
[Top][All Lists]

## Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value

 From: Charles Levert Subject: Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value Date: Fri, 8 Jul 2005 12:45:37 -0400 User-agent: Mutt/1.4.1i

```* On Friday 2005-07-08 at 08:21:10 -0400, Charles Levert wrote:
> So it suffices to show that
>
>     3  >  a * (log_2(2^(b + 2) + 2) - log_2(2^b + 2))
>
> for a given value of b, for my upper bound
> to get even looser compared to Knuth's when
> that b is increased to b + 2.  By taking the
> power of 2 on each side, this inequality can be
> transformed into
>
>     8 + phi  >  (2^(b + 2) + 2) / (2^b + 2)
>
>     8 + phi  >  (4 * 2^b + 2) / (2^b + 2)
>
>     (8 + phi) * (2^b + 2)  >  (4 * 2^b + 2)
>
>     (8 + phi) * 2^b + (8 + phi) * 2  >  4 * 2^b + 2
>
>     (8 + phi) * 2^b + (16 + 2 * phi)  >  4 * 2^b + 2
>
>     ((8 + phi) - 4) * 2^b  >  2 - (16 + 2 * phi)
>
>     (4 + phi) * 2^b  >  -14 - 2 * phi
>
>     positive > negative

Before anyone else points out my mistake with
"8 + phi", here's the corrected development.
The conclusion still holds.

3                            >  a * (log_2(2^(b + 2) + 2) - log_2(2^b + 2))
3/a                          >  log_2(2^(b + 2) + 2) - log_2(2^b + 2)
2^(3/a)                      >  (2^(b + 2) + 2) / (2^b + 2)
2^(3/a) * (2^b + 2)          >  (2^(b + 2) + 2)
2^(3/a) * 2^b + 2^(3/a) * 2  >  4 * 2^b + 2
(2^(3/a) - 4) * 2^b          >  (1 - 2^(3/a)) * 2
0.236067977499791 * 2^b      >  -6.47213595499958
positive                     >  negative

```