Re: types, was New Book: The School of Niklaus Wirth

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>
> Jerry Leichter <jerrold.leichter@smarts.com> writes:
>>For *division*, however, things break down: 1/-1 is -1 in signed
>>arithmetic, but 0 in unsigned arithmetic. The unsigned form gives you
>>the division in the ring of integers mod 2^n,
>
>If you mean "ring of (integers mod 2^n)", then you are wrong. E.g.,
>
>3*6=2 (mod 16)
>i.e.,
>2/3=6 (mod 16)
>
>In contrast, the integer division in all programming languages I know
>gives 0 for 2/3.


Right; in fact division doesn't even make sense in a ring (unless it
also happens to be a field), since not every element has an inverse.


A neat way to find the inverse of an element, if it exists, in the
ring of integers mod 2^W (where W is the implementation's word size)
is:


unsigned int n, inv;
/* ... */
inv = n;
while (n != 0 && n != 1)
inv *= (n *= n);


Proof of correctness (and termination!) left as an exercise :-)
For example,


3 * 6 = 18 (mod 2^32), and
        6 = 18 * 2863311531 (mod 2^32)




--Joe English


    jenglish@flightlab.com

Return to the comp.compilers page.
Search the comp.compilers archives again.