Summary : Modulo n arithmetics

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

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