Phép toán modulo

(Đổi hướng từ 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ương, (số bị chia) a và (số chia) n, a modulo n (viết tắt là a mod n) là số dư của phép chia có dư Euclid của a cho n. 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 an đề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 n là từ 0 đến n − 1. (a mod 1 luôn bằng 0; a mod 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 a hoặc n 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

     Thương số (q) và      số dư (r) theo các hàm của số bị chia (a), bằng cách dùng các thuật toán khác nhau

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ố qsố dư r của phép chia a cho n 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 a hoặc n.[1] Ngôn ngữ PascalALGOL 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 n hoặc a là số âm. Xem bảng để biết chi tiết. a 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à a.

  • Nhiều cài đặt sử dụng phép chia rút gọn mà trong đó thương số được định nghĩa bởi hàm rút gọn q = trunc(a/n) do đó theo phương trình (1) số dư sẽ có cùng dấu với số bị chia. Thương số được làm tròn về số không: bằng số nguyên đầu tiên có phần hướng tới không của thương số hữu tỉ.
  • Donald Knuth[1] mô tả phép chia sàn trong đó thương số được định nghĩa bởi hàm floor q = ⌊a/n, do đó theo phương trình (1) số dư sẽ có cùng dấu với số chia. Do hàm floor, thương số luôn được làm tròn xuống kể cả khi nó là số âm.
  • Raymond T. Boute[2] mô tả định nghĩa phép chia có dư trong đó số dư luôn không âm, 0 ≤ r, phù hợp với giải thuật phép chia có dư. Trong đó,

    hoặc tương đương

    với sgnhàm sign, do đó

  • Ngôn ngữ Common Lisp cũng định nghĩa phép chia làm tròn và phép chia trần, trong đó thương số cho bởi q = round(a/n)q = ⌈a/n tương ứng.
  • IEEE 754 định nghĩa hàm số dư trong đó thương số là a/n được làm tròn dựa trên quy ước làm tròn đến số gần nhất. Do vậy, dấu của số dư được chọn là gần với số 0 nhất.

Theo mô tả của Leijen,

Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition. Despite its widespread use, truncated division is shown to be inferior to the other definitions.(Tạm dịch: Boute lập luận rằng phép chia có dư là vượt trội so với các phép chia khác về tính đều đặn và các thuộc tính toán học hữu ích, dù rằng với phép chia sàn, được Knuth ủng hộ, cũng là một định nghĩa tốt. Tuy được sử dụng rộng rãi, phép chia rút gọn được chứng minh kém hơn các định nghĩa khác.)

— Daan Leijen, Division and Modulus for Computer Scientists[3]

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 (-a) div n = -(a div n)a div (-n) = -(a div n), 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ần dẫn nguồ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 n (số bị chia) là số âm lẻ, n 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 mod(), và nhiều ngôn ngữ lập trình khác có hàm tương tự, biểu diễn cho mod(a, n). 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 mod() (chú ý rằng kiểu 'int' vốn đã sinh ra giá trị rút gọn a/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ử x 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.[4]

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ị:
  • Phần tử đảo:
    • [(−a mod n) + (a mod n)] mod n = 0.
    • b−1 mod n kí hiệu phần tử đảo modular, được định nghĩa khi và chỉ khi bn là các số nguyên tố cùng nhau, khi vế trái xác định: [(b−1 mod n)(b mod n)] mod n = 1.
  • Tính phân phối:
    • (a + b) mod n = [(a mod n) + (b mod n)] mod n.
    • ab mod n = [(a mod n)(b mod n)] mod n.
  • Phép chia (định nghĩa): a/b mod n = [(a mod n)(b−1 mod n)] mod n, khi vế phải xác định (là khi b 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: [(ab mod n)(b−1 mod n)] mod n = a mod n.

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
ABAPMODLuôn không âm
ActionScript%Số bị chia
AdamodSố chia
remSố bị chia
ALGOL 68÷×, modLuôn không âm
AMPLmodSố bị chia
APL|[2]Số chia
AppleScriptmodSố bị chia
AutoLISP(rem d n)Số dư
AWK%Số bị chia
BASICModKhô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
divngôn ngữ lập trình
C++ (ISO 1998)%Định nghĩa tùy thuộc cài đặt[5]
divSố bị chia
C (ISO 1999)%, divSố bị chia[6]
C++ (ISO 2011)%, divSố bị chia
C#%Số bị chia
Clarion%Số bị chia
ClojuremodSố chia
remSố bị chia
COBOL[3]FUNCTION MODSố chia
CoffeeScript%Số bị chia
%%Số chia[7]
ColdFusion%, MODSố bị chia
Common LispmodSố chia
remSố bị chia
Construct 2%
D%Số bị chia[8]
Dart%Luôn không âm
remainder()Số bị chia
Eiffel\\
ErlangremSố bị chia
EuphoriamodSố chia
remainderSố bị chia
F#%Số bị chia
FileMakerModSố chia
Forthmodtùy thuộc vào cài đặt
FortranmodSố bị chia
moduloSố chia
FrinkmodSố chia
GameMaker: Studio (GML)mod, %Số bị chia
GDScript%Số bị chia
Go%Số bị chia
HaskellmodSố chia
remSố bị chia
Haxe%Số bị chia
Kotlin%Số bị chia
J|[4]Số chia
Java%Số bị chia
Math.floorModSố chia
JavaScript%Số bị chia
JuliamodSố chia
remSố bị chia
LabVIEWmodSố bị chia
LibreOffice=MOD()Số chia
Lua 5%Số chia
Lua 4mod(x,y)Số chia
Liberty BASICMODSố bị chia
Mathcadmod(x,y)Số chia
Maplee mod mLuôn không âm
MathematicaMod[a, b]Số chia
MATLABmodSố chia
remSố bị chia
MaximamodSố chia
remainderSố bị chia
Maya Embedded Language%Số bị chia
Microsoft Excel=MOD()Số chia
MinitabMODSố chia
mksh%Số bị chia
Modula-2MODSố chia
REMSố bị chia
MUMPS#Số chia
Netwide Assembler (NASM, NASMX)%toán tử modulo không dấu
%%toán tử modulo có dấu
OberonMODSố chia[5]
Object Pascal, DelphimodSố bị chia
OCamlmodSố bị chia
Occam\Số bị chia
Pascal (ISO-7185 and -10206)modLuôn không âm
Perl%Số chia[6]
PHP%Số bị chia
PIC BASIC Pro\\Số bị chia
PL/ImodSố chia (ANSI PL/I)
PowerShell%Số bị chia
ProgressmoduloSố bị chia
Prolog (ISO 1995)modSố chia
remSố bị chia
PureBasic%,Mod(x,y)Số bị chia
Python%Số chia
math.fmodSố bị chia
RacketremainderSố bị chia
RealBasicMODSố bị chia
R%%Số chia
Rexx//Số bị chia
RPG%REMSố bị chia
Ruby%, modulo()Số chia
remainder()Số bị chia
Rust%Số bị chia
Scala%Số bị chia
SchememoduloSố chia
remainderSố bị chia
Scheme R6RSmodLuôn không âm[9]
mod0Nearest to zero[9]
Seed7modSố chia
remSố bị chia
SenseTalkmoduloSố chia
remSố 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 MLmodSố chia
Int.remSố bị chia
Statamod(x,y)Luôn không âm
Swift%Số bị chia
Tcl%Số chia
Torque%Số bị chia
TuringmodSố chia
Verilog (2001)%Số bị chia
VHDLmodSố chia
remSố bị chia
VimL%Số bị chia
Visual BasicModSố bị chia
x86 assemblyIDIVSố bị chia
XBase++%Số bị chia
Mod()Số chia
Z3 theorem proverdiv, modLuô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
ABAPMODLuôn không âm
C (ISO 1990)fmodSố bị chia[10]
C (ISO 1999)fmodSố bị chia
remainderGần với số 0
C++ (ISO 1998)std::fmodSố bị chia
C++ (ISO 2011)std::fmodSố bị chia
std::remainderGần với số 0
C#%Số bị chia
Common LispmodSố chia
remSố bị chia
D%Số bị chia
Dart%Luôn không âm
remainder()Số bị chia
F#%Số bị chia
FortranmodSố bị chia
moduloSố chia
Gomath.ModSố bị chia
Haskell (GHC)Data.Fixed.mod'Số chia
Java%Số bị chia
JavaScript%Số bị chia
LabVIEWmodSố bị chia
Microsoft Excel=MOD()Số chia
OCamlmod_floatSố bị chia
PerlPOSIX::fmodSố bị chia
Perl6%Số chia
PHPfmodSố bị chia
Python%Số chia
math.fmodSố bị chia
Rexx//Số bị chia
Ruby%, modulo()Số chia
remainder()Số bị chia
Scheme R6RSflmodLuôn không âm
flmod0Gần với số 0
Standard MLReal.remSố bị chia
SwifttruncatingRemainder(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.[11]
  • ^ 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 [[remainder#The inequality satisfied by the remainder|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