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

jenglish@flightlab.com (Joe English)
3 Dec 2000 00:26:35 -0500

          From comp.compilers

Related articles
Re: Re: New Book: The School of Niklaus Wirth ollanes@pobox.com (Orlando Llanes) (2000-11-05)
Re: types, was New Book: The School of Niklaus Wirth joachim_d@gmx.de (Joachim Durchholz) (2000-11-25)
Re: types, was New Book: The School of Niklaus Wirth jerrold.leichter@smarts.com (Jerry Leichter) (2000-11-30)
Re: types, was New Book: The School of Niklaus Wirth anton@mips.complang.tuwien.ac.at (2000-12-01)
Re: types, was New Book: The School of Niklaus Wirth jenglish@flightlab.com (2000-12-03)
| List of all articles for this month |

From: jenglish@flightlab.com (Joe English)
Newsgroups: comp.compilers
Date: 3 Dec 2000 00:26:35 -0500
Organization: Advanced Rotorcraft Technology, Inc.
References: 00-11-046 00-11-152 00-11-165 00-12-009
Keywords: types
Posted-Date: 03 Dec 2000 00:26:34 EST

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


Post a followup to this message

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