3 Dec 2000 00:26:35 -0500

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) |

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.