Modulo (rest): Definition, regler og forskelle i programmering

Modulo (rest): Klar forklaring på definition, regler og hvordan forskellige programmeringssprog/hardware håndterer resten — med eksempler og praktiske forskelle.

I matematik er resultatet af modulo-operationen resten af en aritmetisk division. Som bekendt giver en aritmetisk division af to hele tal en kvotient og en rest.

Der er dog også andre konventioner mulige. Computere og lommeregnere har forskellige måder at lagre og repræsentere tal på. Deres definition af modulo-operationen afhænger af programmeringssproget og/eller den underliggende hardware.

Formel og matematisk definition

Givet to hele tal a (dividenden) og b (divisor, b ≠ 0) siger den grundlæggende restdeling (Euclidske division) at der findes entydige heltal q (kvotient) og r (rest) så:

a = q · b + r, hvor 0 ≤ r < |b|.

Den matematiske modulo-resten er ofte valgt, så r er ikke-negativ og mindre end den absolutte værdi af divisoren. Denne konvention bruges i talteori og ved beregninger på ringe og klasser modulo n (fx "a ≡ c (mod n)").

Forskellen mellem "remainder" og "modulo" i programmering

I programmeringssprog eksisterer typisk en operator (ofte skrevet %) eller en funktion til at beregne rest/remainder. Der er dog to forskellige konventioner, der ofte forveksles:

• Truncating remainder (remainder med kvotient afrundet mod 0): Kvotienten q findes ved at afrunde divisionen mod 0 (truncation). Resten r = a − q·b får samme fortegn som dividenden a. Dette er fx tilfældet i moderne C/C++ og Java.
• Euclidean modulo: Resten r vælges, så 0 ≤ r < |b|. Denne variant giver altid en ikke-negativ rest (når |b| bruges som modulus). Python og nogle andre sprog følger denne konvention for operatoren %, mens andre sprog kan tilbyde både "rem" og "mod" som separate funktioner (f.eks. Haskell har rem og mod).

Konkrete eksempler

• 17 % 5 = 2 (både matematik og de fleste sprog)
• -17 % 5:
  • Matematisk (Euclid): 3, fordi -17 = (-4)·5 + 3
  • C/Java (trunc toward 0): -2, fordi kvotienten er -3 og -17 - (-3·5) = -2
  • Python (%): 3 (Python vælger resten med samme fortegn som divisor)
• -17 % -5:
  • Euclid modulo (brug |b|): resultat er 3 (0 ≤ r < 5)
  • Sprog der bruger sign(r) = sign(dividend) vil give r med samme fortegn som a

Regler og nyttige identiteter

• a = b·q + r med r i det interval, som konventionen kræver (enten 0 ≤ r < |b| eller sign(r) = sign(a)).
• Hvis b deler a (b | a), så er r = 0.
• Modular aritmetik: a ≡ r (mod b) — to tal er kongruente modulo b, hvis deres differens er delelig med b.
• Kombinationsregel: (a + c) mod b = ((a mod b) + (c mod b)) mod b og tilsvarende for subtraktion og multiplikation. Dette gælder i den matematiske (Euclidske) forstand og praktisk i programmering så længe man justerer for sprogkonventioner om fortegn.

Programmeringssprog — hvad gør de?

• C/C++ (modern standard): Integer division trunceres mod 0, og resten har samme fortegn som dividenden. Tidligere C-standarder lod det være implementation-afhængigt.
• Java: Samme opførsel som C: kvotient trunceres mod 0, resten har samme fortegn som dividenden.
• Python: Operatoren % giver en rest med samme fortegn som divisoren (Euclid-lignende), dvs. resultatet for a % b ligger i intervallet 0 ≤ r < |b| hvis b > 0.
• JavaScript: % er en rest-operator, der følger tegnet af dividenden (som i C/Java).
• Haskell: Adskiller rem (rest med samme fortegn som dividend) og mod (modulus med samme fortegn som divisor).

Hvordan få altid ikke-negativ rest i sprog der giver negative rester?

Hvis du ønsker en Euclid-lignende ikke-negativ rest i et sprog hvor % kan være negativ (fx C/Java/JS), kan du rette resultatet med:

Hvis b > 0: r = a % b; if (r < 0) r += b;

Et generelt udtryk der virker hvis b kan være negativ er: r = a % b; if (r < 0) r += (b > 0 ? b : -b);

En anden smart formel (for b > 0): r = ((a % b) + b) % b — men vær opmærksom på effektiviteten og overflow i et konkret sprog.

Flydende tal og specialfunktioner

For flydende tal findes funktioner som fmod (C) og math.fmod (Python), som returnerer rest i samme tegn som dividenden. Mange sprog definerer også en mathematiske fmod og en "mod" i højere niveau biblioteker som følger den matematiske (Euclid) konvention. Vær derfor opmærksom på hvilken funktion du bruger ved flydende modulo.

Anvendelser

• Tid og dato (klokkeslæt, ugedage): beregninger på cirkulære størrelser.
• Hashing og spredning i datastrukturer.
• Kryptografi (modulær multiplikation og eksponentiering).
• Cirkulære buffere og indeksering i arrays.

Praktiske råd

• Sæt dig ind i dit sprogs konvention for % eller remainder-funktionen før du stoler på resultater med negative tal.
• Hvis du altid behøver en ikke-negativ rest, implementer en lille hjælpefunktion som korrigerer negative resultater.
• Brug klare navne i din kode (fx mod_euclid(a,b) eller rem_trunc(a,b)) så det er tydeligt hvilken konvention du anvender.

Kort sagt: "modulo" i matematik er normalt defineret så resten er ikke-negativ og mindre end |b|, mens konkrete programmeringssprog kan have andre, praktiske definitioner. Kend din platforms definition, især når negative tal er involveret.

Søg efter bogstav