Fri, 27 Nov 1992 10:53:53 GMT

Related articles |
---|

Modulo n arithmetics fabre@gr.osf.org (Christian Fabre) (1992-11-06) |

Summary : Modulo n arithmetics fabre@gr.osf.org (Christian Fabre) (1992-11-27) |

Newsgroups: | comp.compilers |

From: | Christian Fabre <fabre@gr.osf.org> |

Organization: | Compilers Central |

Date: | Fri, 27 Nov 1992 10:53:53 GMT |

References: | 92-11-029 |

Keywords: | arithmetic, summary |

A while ago I asked a question about modulo arithmetics.

*> I am wondering if any languages or application havily rely on*

*> modulo arithmetics:*

Thanks to all who replied, and especially to Peter Montgomery

<pmontgom@MATH.ORST.EDU> who corected some error of mine ... :-)

*> > e.g.:*

*> > 27+30 = 57 % 51 = 7*

*> > 12*12 = 144 % 51 = 44*

*> *

*> The answers should be 6 and 42.*

Folowing areas where modulo arithmetics could be used

were mentioned:

- Computational number theory. This uses huge moduli (e.g.

150 digits)..

- Time/Angle maths

- Buffering and queing schemes.

- Symbolic computation: uses Z mod p.

- Discrete Fourier transforms can use a commutative

ring of integers modulo a constant.

- Realtime digital signal processing uses it for circular buffer and

shift registers.

- Addressing 64 bits memory spaces on a network of 32 bits machines

requires modulo to compute addresses.

- Communication: TCP uses 32 bits counters to sequences packets.

- Finite elements on a sphere or a circle (adressing).

Taken from another thread of discussion, jlg@cochiti.lanl.gov (J. Giles)

summarizes various falvors of div and mod:

*> There are actually several different divide functions which are useful.*

*> It would be nice if all were supported. There are so many because*

*> integers, and even integers modulo a power of two, do not form a quotient*

*> ring. This means that divide on the integers is inherently inexact. To*

*> give a formal meaning to divide, you must make some choices.*

*>*

*> Definitions:*

*>*

*> |i| is the absolute value function.*

*>*

*> sign(i) = 0 if i==0; i/|i| otherwise.*

*>*

*> Divides:*

*>*

*> floor(n,d) = max integer k <= n/d*

*> ceiling(n,d) = min integer >= n/d*

*> trunc(n,d) = floor(|n|,|d|) * sign(n) * sign(d)*

*> round(n,d) = largest integer k for which |k-n/d| <= 1/2*

*> mdiv(n,d) = floor(n,d) if d is positive, ceiling(n,d) otherwise*

*>*

*> These are *some* of the divide operations that might be useful. The first*

*> four (floor, ceiling, trunc, and round) are quite common. I put in the*

*> last one (mdiv) since it is the one which corresponds to the version of*

*> the mod function which mathematicians like (where the answer is always*

*> positive). Speaking of which, all of these division functions correspond*

*> to a different remainder function:*

*>*

*> rem(n,d) = n - divide(n,d) * d*

*>*

*> Where `divide' is whatever form of division you decide to select. If you*

*> use mdiv() from above as your divide, then the rem() function is the*

*> mathematical modulus. Whichever divide you choose to support, the*

*> corresponding remainder function should be available as well - and*

*> vice-versa.*

Christian.

-----

Christian Fabre, OSF-RI, 2 avenue de Vignate, 38610 Gieres, France.

fabre@gr.osf.org -- Tel: +33 76.63.48.90

fabre@ri.osf.fr -- Fax: +33 76.51.05.32

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.