Phép toán modulo

Trong điện toán, phép toán modulo là phép toán tìm số dư của phép chia 2 số (đôi khi được gọi là modulus).

Cho hai số dư, (số bị chia)  và (số chia) ,  modulo  (viết tắt là ) là số dư của phép chia có dư Euclid của  cho . Ví dụ, biểu thức "5 mod 2" bằng 1 vì 5 chia cho 2 có thương số là 2 là số dư là 1, trong khi "9 mod 3" bằng 0 do 9 chia 3 có thương số là 3 và số dư 0; không còn gì trong phép trừ của 9 cho 3 nhân 3. (Lưu ý rằng thực hiện phép chia bằng máy tính cầm tay sẽ không hiển thị kết quả giống như phép toán này; thương số sẽ được biểu diễn dưới dạng phần thập phân.)

Mặc dù thường được thực hiện khi  và  đều là số nguyên, nhiều hệ tính toán cho phép sử dụng các kiểu khác của toán học bằng số. Giới hạn của một modulo nguyên của  là từ 0 đến . ( mod 1 luôn bằng 0;  là không xác định, có thể trả về lỗi chia cho số 0 trong nhiều ngôn ngữ lập trình.) Xem số học mô-đun để tìm các quy ước cũ hơn và liên quan được áp dụng trong lý thuyết số.

Khi hoặc  hoặc  là số âm, định nghĩa cơ bản bị phá vỡ và các ngôn ngữ lập trình khác nhau trong việc định nghĩa các kết quả này.
Tính toán phần dư trong phép toán modulo
Trong toán học, kết quả của phép toán modulo là số dư của phép chia có dư. Tuy vậy các quy ước khác vẫn tồn tại. Máy vi tính và máy tính có nhiều cách khác nhau để lưu trữ và đại diện cho các số; do đó định nghĩa của chúng về phép toán modulo phụ thuộc vào ngôn ngữ lập trình hoặc phần cứng máy tính bên dưới cơ bản.

Trong hầu hết các hệ thống máy tính, thương số  và số dư  của phép chia  cho  thỏa mãn


Tuy nhiên, vẫn còn sự nhập nhằng về dấu nếu số dư khác không: hai lựa chọn có thể cho số dư xảy ra, một âm và một dương, và hai lựa chọn cho thương số xảy ra. Trong lý thuyết số, thông thường số dư dương luôn được chọn, nhưng lựa chọn của các ngôn ngữ lập trình tùy thuộc vào ngôn ngữ và dấu của  hoặc . Ngôn ngữ Pascal và ALGOL 68 tiêu chuẩn chọn số dư dương (hoặc 0) kể cả khi số chia là các số âm, đối với một vài ngôn ngữ lập trình như C90 thì dấu tùy thuộc vào cài đặt khi hoặc  hoặc  là số âm. Xem bảng để biết chi tiết.  modulo 0 là không xác định trong hầu hết các hệ thống, mặc dù một số hệ thống định nghĩa là .

Theo mô tả của Leijen,

Tuy nhiên, Boute tập trung vào các tính chất của chính phép toán modulo và không đánh giá sự thật là phép chia rút gọn (tiếng Anh: truncated division) cho thấy sự đối xứng của  và , mà cũng giống phép chia thông thường. Bởi vì cả hai phép chia sàn và phép chia có dư đều không có tính đối xứng này, phán đoán của Boute ít nhất là không toàn diện.

Các sai lầm thông thường
Nếu kết quả của phép chia modulo có dấu của số bị chia thì sẽ dẫn đến các sai lầm đáng ngạc nhiên.

Ví dụ, để kiểm tra tính lẻ của một số nguyên, ta có thể kiểm tra số dư khi chia cho có bằng 1:

bool is_odd(int n) {
    return n % 2 == 1;
}

Khi ngôn ngữ lập trình có số dư có dấu của số bị chia, việc kiểm tra sẽ sai, do khi  (số bị chia) là số âm lẻ,  mod 2 trả về −1, và hàm trả về false.

Có thể sửa lại sai lầm đó bằng cách kiểm tra rằng kết quả khác 0 (do số dư bằng 0 được xem xét như nhau bất kể dấu):

bool is_odd(int n) {
    return n % 2 != 0;
}

Hay là, bằng việc hiểu trước rằng với bất kỳ số lẻ nào, số dư modulo có thể hoặc bằng 1 hoặc −1:

bool is_odd(int n) {
    return n % 2 == 1 || n % 2 == -1;
}

Ký hiệu

Một số máy tính cầm tay có nút của hàm , và nhiều ngôn ngữ lập trình khác có hàm tương tự, biểu diễn cho . Một vài ngôn ngữ hỗ trợ các biễu thức mà dùng "%", "mod", hoặc "Mod" là toán tử modulo hoặc toán tử lấy số dư, chẳng hạn
a % n
hoặc
a mod n
hoặc tương đương cho môi trường thiếu hàm  (chú ý rằng kiểu 'int' vốn đã sinh ra giá trị rút gọn )
a - (n * int(a/n))

Vấn đề hiệu suất
Phép toán modulo có thể được cài đặt sao cho mỗi lần phép chia với số dư được tính. Đôi với nhu cầu đặc biệt, trên vài phần cứng, tồn tại các phép toán tương tự nhưng nhanh hơn. Ví dụ, modulo cho lũy thừa của 2 có thể biễu diễn tương đương bởi phép toán bitwise AND:
x % 2n == x & (2n - 1)

Ví dụ (giả sử  là số nguyên dương):
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7

Trong các thiết bị và phần mềm mà cài đặt toán tử bitwise hiệu quả hơn toán tử modulo, các dạng thay thế này có thể dẫn đến tính toán nhanh hơn.

Các trình biên dịch tối ưu hóa có thể nhận diện các biểu thức có dạng expression % constant trong đó constant là lũy thừa của 2 và tự động cài đặt chúng thành expression & (constant-1). Điều này cho phép viết mã rõ ràng hơn mà không ảnh hưởng đến hiệu suất. Cách tối ưu hóa này không áp dụng cho các ngôn ngữ mà kết quả của phép toán modulo có cùng dẫu với số bị chia (bao gồm C), trừ phi số bị chia là kiểu số nguyên không dấu. Bởi vì nếu số bị chia là số âm thì modulo sẽ là số âm trong khi expression & (constant-1) sẽ luôn dương.

Tính tương đương
Một số phép toán modulo có thể được mở rộng tương tự sang các phép toán toán học khác. Điều này có tính hữu dụng trong các chứng minh mật mã học, chẳng hạn trao đổi khóa Diffie-Hellman.
Phần tử đơn vị:
.
 với mọi số nguyên dương .
 Nếu  là số nguyên tố không phải là ước số của , thì , dựa theo định lý nhỏ Fermat.
Phần tử đảo:
.
 kí hiệu phần tử đảo modular, được định nghĩa khi và chỉ khi  và  là các số nguyên tố cùng nhau, khi vế trái xác định: .
Tính phân phối:
.
.
Phép chia (định nghĩa): , khi vế phải xác định (là khi  và math|n}} là các số nguyên tố cùng nhau). Các trường hợp còn lại là không xác định.
Phép nhân nghịch đảo: .
Dấu Mod trong các ngôn ngữ lập trình
+ Toán tử modulo của số nguyên trong nhiều ngôn ngữ lập trình khác nhau Ngôn ngữ Toán tử Kết quả có cùng dấu với ABAP MOD Luôn không âm ActionScript % Số bị chia Ada mod Số chia rem Số bị chia ALGOL 68 ÷×, mod Luôn không âm AMPL mod Số bị chia APL | Số chia AppleScript mod Số bị chia AutoLISP (rem d n) Số dư AWK % Số bị chia BASIC Mod Không xác định bash % Số bị chia bc % Số bị chia C (ISO 1990) % Định nghĩa tùy thuộc cài đặt div ngôn ngữ lập trình C++ (ISO 1998) % Định nghĩa tùy thuộc cài đặt. "the binary % operator yields the remainder from the division of the first expression by the second..... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined". div Số bị chia C (ISO 1999) %, div Số bị chiaopen-std.org, mục 6.5.5 C++ (ISO 2011) %, div Số bị chia C# % Số bị chia Clarion % Số bị chia Clojure mod Số chia rem Số bị chia COBOL FUNCTION MOD Số chia CoffeeScript % Số bị chia %% Số chiaCoffeeScript operators ColdFusion %, MOD Số bị chia Common Lisp mod Số chia rem Số bị chiaConstruct 2% D % Số bị chia Dart % Luôn không âm remainder() Số bị chia Eiffel \\  Erlang rem Số bị chia Euphoria mod Số chia remainder Số bị chia F# % Số bị chia FileMaker Mod Số chia Forth mod tùy thuộc vào cài đặt Fortran mod Số bị chia modulo Số chia Frink mod Số chia GameMaker: Studio (GML) mod, % Số bị chia GDScript % Số bị chia Go % Số bị chia Haskell mod Số chia rem Số bị chia Haxe % Số bị chia Kotlin % Số bị chia J | Số chia Java % Số bị chia Math.floorMod Số chia JavaScript % Số bị chia Julia mod Số chia rem Số bị chiaLabVIEWmod Số bị chia LibreOffice =MOD() Số chia Lua 5 % Số chia Lua 4 mod(x,y) Số chia Liberty BASIC MOD Số bị chia Mathcad mod(x,y) Số chia Maple e mod m Luôn không âm Mathematica Mod[a, b] Số chia MATLAB mod Số chia rem Số bị chia Maxima mod Số chia remainder Số bị chia Maya Embedded Language % Số bị chia Microsoft Excel =MOD() Số chia Minitab MOD Số chia mksh % Số bị chia Modula-2 MOD Số chia REM Số bị chia MUMPS # Số chia Netwide Assembler (NASM, NASMX) % toán tử modulo không dấu %% toán tử modulo có dấu Oberon MOD Số chia Object Pascal, Delphi mod Số bị chia OCaml mod Số bị chia Occam \ Số bị chia Pascal (ISO-7185 and -10206) mod Luôn không âm Perl % Số chia PHP % Số bị chia PIC BASIC Pro \\ Số bị chia PL/I mod Số chia (ANSI PL/I) PowerShell % Số bị chia Progress modulo Số bị chia Prolog (ISO 1995) mod Số chia rem Số bị chia PureBasic %,Mod(x,y) Số bị chia Python % Số chia math.fmod Số bị chia Racket remainder Số bị chia RealBasic MOD Số bị chia R %% Số chia Rexx // Số bị chia RPG %REM Số bị chia Ruby %, modulo() Số chia remainder() Số bị chia Rust % Số bị chia Scala % Số bị chia Scheme modulo Số chia remainder Số bị chia Scheme R6RS mod Luôn không âmr6rs.org mod0 Nearest to zero Seed7 mod Số chia rem Số bị chia SenseTalk modulo Số chia rem Số bị chia Smalltalk \\ Số chia rem: Số bị chia Spin // Số chia SQL (SQL:1999) mod(x,y) Số bị chia SQL (SQL:2012) % Số bị chia Standard ML mod Số chia Int.rem Số bị chia Stata mod(x,y) Luôn không âm Swift % Số bị chia Tcl % Số chia Torque % Số bị chia Turing mod Số chia Verilog (2001) % Số bị chia VHDL mod Số chia rem Số bị chia VimL % Số bị chia Visual Basic Mod Số bị chia x86 assembly IDIV Số bị chia XBase++ % Số bị chia Mod() Số chia Z3 theorem prover div, mod Luôn không âm

+ Toán tử modulo của số chấm động trong nhiều ngôn ngữ lập trình Ngôn ngữ Toán tử Kết quả có cùng dấu với ABAP MOD Luôn không âm C (ISO 1990) fmod Số bị chia "The fmod function returns the value x - i * y, for some integer i such that, if y is nonzero, the result as the same sign as x and magnitude less than the magnitude of y.". C (ISO 1999) fmod Số bị chia remainder Gần với số 0 C++ (ISO 1998) std::fmod Số bị chia C++ (ISO 2011) std::fmod Số bị chia std::remainder Gần với số 0 C# % Số bị chia Common Lisp mod Số chia rem Số bị chia D % Số bị chia Dart % Luôn không âm remainder() Số bị chia F# % Số bị chia Fortran mod Số bị chia modulo Số chia Go math.Mod Số bị chia Haskell (GHC) Data.Fixed.mod' Số chia Java % Số bị chia JavaScript % Số bị chiaLabVIEWmod Số bị chia Microsoft Excel =MOD() Số chia OCaml mod_float Số bị chia Perl POSIX::fmod Số bị chia Perl6 % Số chia PHP fmod Số bị chia Python % Số chia math.fmod Số bị chia Rexx // Số bị chia Ruby %, modulo() Số chia remainder() Số bị chia Scheme R6RS flmod Luôn không âm flmod0 Gần với số 0 Standard ML Real.rem Số bị chia Swift truncatingRemainder(dividingBy:) Số bị chia XBase++  % Số bị chia Mod() Số chia

Xem thêm
Modulo (Chống nhầm lẫn) và modulo (biệt ngữ) – nhiều cách sử dụng từ modulo, tất cả đều phát sinh từ cuốn sách Nhập môn số học mô đun (tựa Anh:introduction of modular arithmetic) của Carl F. Gauss năm 1801.
Lũy thừa Modular

Chú thích
  Perl sử dụng toán tử modulo số học mà độc lập với máy tính. Để biết thêm ví dụ và các ngoại lệ, xem tài liệu Perl về toán tử nhân.Perl documentation
  Trên phương diện toán học, hai lựa chọn này là hai trong số vô số lựa chọn có sẵn trong bất đẳng thức thỏa mãn bằng một số dư
  Số chia phải là dương, nếu không không xác định.
  Như được cài dặt trong ACUCOBOL, Micro Focus COBOL, và có thẻ là các ngôn ngữ khác
  Trật tự tham số đảo ngược, ví dụ, α|ω computes , số dư khi chia ω cho α.

Tham khảo

Thể loại:Phép toán hai ngôi
Thể loại:Số học máy tính
Thể loại:Số học Modulo
Thể loại:Toán tử (lập trình)

de:Division mit Rest#Modulo