Re: [9fans] Integer arithmetic: some lessons

[tlaronde@polynum.com]

On Wed, Apr 21, 2010 at 04:28:52PM -0700, Bakul Shah wrote:
>
> > Conclusion: I will have to replace in METAFONT all div involving power
> > of two to binary operations, since if I replace in some places and not
> > in others, I wreak havoc the algorithms since computations are not done
> > the same way for combined chunks.
>
> Replacing div 2^N of a signed number by >>N seems like a mistake.

I know (by theory and by test) that for negative numbers:

1) There is no standard behavior;

2) The result is different with div and shift.

The problem is that in METAFONT, Knuth states explicitely that there may
be a problem depending on the way integers (negative integers) are
handled, but in a lot of the algorithms _floor_ is expected: shift gives
you floor, while div does not.

I have tested simply both gcc and ken-cc and they behave the same for
div. Hence, since for the whole program they do not behave the same (gcc
gives the expect result; on some draws (glyphes), ken-cc does not),
there is something going on.

D.E. Knuth is very precise and there are a lot of details. For example,
in some routines, he has called a variable: be_careful, because to avoid
an overflow, it has to be computed the way it is written, and the
compiler must not optimize (change the order of operation, doing an add
before a substract) => I have made so that this is translated to
"volatile int" since, in "Plan 9 C compilers" Ken Thompson specify that
they are "Arithmetic rewrites" (5.4) and that "volatile" is only handled
as "don't do any optimizations". I hope that "arithmetic rewrites" are
disabled too when "volatile" is set, since that may explain the erratic
result in border line (overflow) cases.

I have to search to find exactly what is going wrong and what is done,
to know whether there are no shifts but the algorithm expects "floor",
or there are other volatile expression, order dependant, that are
rewritten and should not.

Note: changing div by power of two some shifts, gcc still gives the same
results (and pass the test), while ken-cc still not, but do not behave
the same.
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C