Editing Modulo (section)

==Generalizations==

===Modulo with offset===

Sometimes it is useful for the result of {{mvar|a}} modulo {{mvar|n}} to lie not between 0 and {{math|''n'' − 1}}, but between some number {{mvar|d}} and {{math|''d'' + ''n'' − 1}}. In that case, {{mvar|d}} is called an ''offset'' and {{math|1=''d'' = 1}} is particularly common. 

There does not seem to be a standard notation for this operation, so let us tentatively use {{math|''a'' mod<sub>''d''</sub> ''n''}}. We thus have the following definition:<ref name="Mathematica Mod" >{{cite web |url=https://reference.wolfram.com/language/ref/Mod.html |title=Mod |author=<!--Not stated--> |date= 2020  |website= Wolfram Language & System Documentation Center  |publisher=[[Wolfram Research]] |access-date=April 8, 2020 }}</ref> {{math|1=''x'' = ''a'' mod<sub>''d''</sub> ''n''}} just in case {{math|''d'' ≤ ''x'' ≤ ''d'' + ''n'' − 1}} and {{math|1=''x'' mod ''n'' = ''a'' mod ''n''}}. Clearly, the usual modulo operation corresponds to zero offset: {{math|1=''a'' mod ''n'' = ''a'' mod<sub>0</sub> ''n''}}. 

The operation of modulo with offset is related to the [[Floor and ceiling functions|floor function]] as follows:
::<math>a \operatorname{mod}_d n = a - n \left\lfloor\frac{a-d}{n}\right\rfloor.</math>
To see this, let <math display="inline">x = a - n \left\lfloor\frac{a-d}{n}\right\rfloor</math>. We first show that {{math|1=''x'' mod ''n'' = ''a'' mod ''n''}}. It is in general true that {{math|1=(''a'' + ''bn'') mod ''n'' = ''a'' mod ''n''}} for all integers {{mvar|b}}; thus, this is true also in the particular case when <math display="inline">b = -\!\left\lfloor\frac{a-d}{n}\right\rfloor</math>; but that means that <math display="inline">x \bmod n = \left(a - n \left\lfloor\frac{a-d}{n}\right\rfloor\right)\! \bmod n = a \bmod n</math>, which is what we wanted to prove. It remains to be shown that {{math|''d'' ≤ ''x'' ≤ ''d'' + ''n'' − 1}}. Let {{mvar|k}} and {{mvar|r}} be the integers such that {{math|1=''a'' − ''d'' = ''kn'' + ''r''}} with {{math|0 ≤ ''r'' ≤ ''n'' − 1}} (see [[Euclidean division]]). Then <math display="inline">\left\lfloor\frac{a-d}{n}\right\rfloor = k</math>, thus <math display="inline">x = a - n \left\lfloor\frac{a-d}{n}\right\rfloor = a - n k = d +r</math>. Now take {{math|0 ≤ ''r'' ≤ ''n'' − 1}} and add {{mvar|d}} to both sides, obtaining {{math|''d'' ≤ ''d'' + ''r'' ≤ ''d'' + ''n'' − 1}}. But we've seen that {{math|1=''x'' = ''d'' + ''r''}}, so we are done.

The modulo with offset {{math|''a'' mod<sub>''d''</sub> ''n''}} is implemented in [[Mathematica]] as {{code|Mod[a, n, d]}}&thinsp;.<ref name="Mathematica Mod" />

=== Implementing other modulo definitions using truncation ===
Despite the mathematical elegance of Knuth's floored division and Euclidean division, it is generally much more common to find a truncated division-based modulo in programming languages. Leijen provides the following algorithms for calculating the two divisions given a truncated integer division:<ref name="Leijen" />

<syntaxhighlight lang="c">
/* Euclidean and Floored divmod, in the style of C's ldiv() */
typedef struct {
  /* This structure is part of the C stdlib.h, but is reproduced here for clarity */
  long int quot;
  long int rem;
} ldiv_t;

/* Euclidean division */
inline ldiv_t ldivE(long numer, long denom) {
  /* The C99 and C++11 languages define both of these as truncating. */
  long q = numer / denom;
  long r = numer % denom;
  if (r < 0) {
    if (denom > 0) {
      q = q - 1;
      r = r + denom;
    } else {
      q = q + 1;
      r = r - denom;
    }
  }
  return (ldiv_t){.quot = q, .rem = r};
}

/* Floored division */
inline ldiv_t ldivF(long numer, long denom) {
  long q = numer / denom;
  long r = numer % denom;
  if ((r > 0 && denom < 0) || (r < 0 && denom > 0)) {
    q = q - 1;
    r = r + denom;
  }
  return (ldiv_t){.quot = q, .rem = r};
}
</syntaxhighlight>

For both cases, the remainder can be calculated independently of the quotient, but not vice versa. The operations are combined here to save screen space, as the logical branches are the same.<!--

The other modes of rounding are:
<syntaxhighlight lang="c">
/* Round-division */
ldiv_t ldivR(long numer, long denom) {

}

/* Ceiling-division */
ldiv_t ldivC(long numer, long denom) {

}
</syntaxhighlight>
-->