# Summary : Modulo n arithmetics

## Christian Fabre <fabre@gr.osf.org>Fri, 27 Nov 1992 10:53:53 GMT

From comp.compilers

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)
| List of all articles for this month |

 Newsgroups: comp.compilers From: Christian Fabre Organization: Compilers Central Date: Fri, 27 Nov 1992 10:53:53 GMT References: 92-11-029 Keywords: arithmetic, summary

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