Phép toán modulo

Từ testwiki
Bước tới điều hướng Bước tới tìm kiếm

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) Bản mẫu:Math và (số chia) Bản mẫu:Math, Bản mẫu:Math modulo Bản mẫu:Math (viết tắt là Bản mẫu:Math) là số dư của phép chia có dư Euclid của Bản mẫu:Math cho Bản mẫu:Math. 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 Bản mẫu:Math và Bản mẫu:Math đề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 Bản mẫu:Math là từ 0 đến Bản mẫu:Math. (Bản mẫu:Math mod 1 luôn bằng 0; Bản mẫu:Math 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 Bản mẫu:Math hoặc Bản mẫu:Math 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

Bản mẫu:Colorbox Thương số (Bản mẫu:Math) và Bản mẫu:Colorbox số dư (Bản mẫu:Math) theo các hàm của số bị chia (Bản mẫu:Math), 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ố Bản mẫu:Math và số dư Bản mẫu:Math của phép chia Bản mẫu:Math cho Bản mẫu:Math thỏa mãn

Bản mẫu:NumBlk

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 Bản mẫu:Math hoặc Bản mẫu:Math.Bản mẫu:Ref 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 Bản mẫu:Math hoặc Bản mẫu:Math là số âm. Xem bảng để biết chi tiết. Bản mẫu:Math 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à Bản mẫu:Math.

Bản mẫu:Bulleted list

Theo mô tả của Leijen, Bản mẫu:Quote

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 Bản mẫu:Math và Bản mẫu:Math, 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.Bản mẫu:Cần chú thíchBản mẫu:OR

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 Bản mẫu:Math (số bị chia) là số âm lẻ, Bản mẫu:Math 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

Bản mẫu:Về

Một số máy tính cầm tay có nút của hàm Bản mẫu:Math, và nhiều ngôn ngữ lập trình khác có hàm tương tự, biểu diễn cho Bản mẫu:Math. 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 Bản mẫu:Math (chú ý rằng kiểu 'int' vốn đã sinh ra giá trị rút gọn Bản mẫu:Math)

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ử Bản mẫu:Math 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.[1]

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.

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 |Bản mẫu:Ref 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[2]
div Số bị chia
C (ISO 1999) %, div Số bị chia[3]
C++ (ISO 2011) %, div Số bị chia
C# % Số bị chia
Clarion % Số bị chia
Clojure mod Số chia
rem Số bị chia
COBOLBản mẫu:Ref FUNCTION MOD Số chia
CoffeeScript % Số bị chia
%% Số chia[4]
ColdFusion %, MOD Số bị chia
Common Lisp mod Số chia
rem Số bị chia
Construct 2 %
D % Số bị chia[5]
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 |Bản mẫu:Ref Số chia
Java % Số bị chia
Math.floorMod Số chia
JavaScript % Số bị chia
Julia mod Số chia
rem Số bị chia
LabVIEW mod 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ố chiaBản mẫu:Ref
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ố chiaBản mẫu:Ref
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 âm[6]
mod0 Nearest to zero[6]
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[7]
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ị chia
LabVIEW mod 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

Chú thích

  • Bản mẫu:Note 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.[8]
  • Bản mẫu:Note 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ư]]
  • Bản mẫu:Note Số chia phải là dương, nếu không không xác định.
  • Bản mẫu:Note Như được cài dặt trong ACUCOBOL, Micro Focus COBOL, và có thẻ là các ngôn ngữ khác
  • Bản mẫu:NoteBản mẫu:Note Trật tự tham số đảo ngược, ví dụ, α|ω computes ωmodα, số dư khi chia ω cho α.

Tham khảo

Bản mẫu:Tham khảo

de:Division mit Rest#Modulo

  1. ↑ Bản mẫu:Chú thích web
  2. ↑ Bản mẫu:Chú thích tạp chí. "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".
  3. ↑ open-std.org, mục 6.5.5
  4. ↑ CoffeeScript operators
  5. ↑ Bản mẫu:Chú thích web
  6. ↑ 6,0 6,1 r6rs.org
  7. ↑ Bản mẫu:Chú thích tạp chí "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.".
  8. ↑ Perl documentation
Lấy từ “https://vi.wiki.beta.math.wmflabs.org/w/index.php?title=Phép_toán_modulo&oldid=2321”