On Tue, 6 Jul 2021 at 23:39, Dean Rasheed <[email protected]> wrote:
> When I first read this:
>
> + /* half-round until we get down to unitBits */
> + while (rightshifts++ < unit->unitBits)
> + size = half_rounded(size);
>
> it looked to me like it would be invoking half_rounded() multiple
> times, which raised alarm bells because that would risk rounding the
> wrong way. Eventually I realised that by the time it reaches that,
> rightshifts will always equal unit->unitBits or unit->unitBits - 1, so
> it'll never do more than one half-round, which is important.
It's true that based on how the units table is set up now, it'll only
ever do it once for all but the first loop.
I wrote the attached .c file just to try to see if it ever goes wrong
and I didn't manage to find any inputs where it did. I always seem to
get the half rounded value either the same as the shifted value or 1
higher towards positive infinity
$ ./half_rounded -102 3
1. half_round(-102) == -51 :: -102 >> 1 = -51
2. half_round(-51) == -25 :: -51 >> 1 = -26
3. half_round(-25) == -12 :: -26 >> 1 = -13
$ ./half_rounded 6432 3
1. half_round(6432) == 3216 :: 6432 >> 1 = 3216
2. half_round(3216) == 1608 :: 3216 >> 1 = 1608
3. half_round(1608) == 804 :: 1608 >> 1 = 804
Can you give an example where calling half_rounded too many times will
give the wrong value? Keeping in mind we call half_rounded the number
of times that the passed in value would need to be left-shifted by to
get the equivalent truncated value.
David
#define half_rounded(x) (((x) + ((x) < 0 ? 0 : 1)) / 2)
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
int num, times;
int i;
int r, shift;
if (argc < 3)
{
printf("Usage: %s <num> <times>\n");
return -1;
}
num = atoi(argv[1]);
times = atoi(argv[2]);
r = num;
shift = num;
for (i = 0; i < times; i++)
{
int rr = half_rounded(r);
printf("%d. half_round(%d) == %d :: %d >> 1 = %d\n", i+1, r,
rr, shift, shift >> 1);
r = rr;
shift >>= 1;
}
return 0;
}
