modulus là gì

Bách khoa toàn thư banh Wikipedia

Trong năng lượng điện toán, luật lệ toán modulo là luật lệ toán thăm dò số dư của luật lệ phân tách 2 số (đôi Lúc được gọi là modulus).

Bạn đang xem: modulus là gì

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

Mặc mặc dù thông thường được triển khai Lúc an đều là số nguyên vẹn, nhiều hệ đo lường được cho phép dùng những loại không giống của toán học tập ngay số. Giới hạn của một modulo nguyên vẹn của n là kể từ 0 cho tới n − 1. (a mod 1 luôn luôn bởi vì 0; a mod 0 là ko xác lập, rất có thể trả về lỗi phân tách cho tới số 0 trong không ít ngữ điệu lập trình sẵn.) Xem số học tập mô-đun nhằm thăm dò những quy ước cũ rộng lớn và tương quan được vận dụng nhập lý thuyết số.

Khi hoặc a hoặc n là số âm, khái niệm cơ bạn dạng bị đánh tan và những ngữ điệu lập trình sẵn không giống nhau trong các công việc khái niệm những thành quả này.

Tính toán phần dư nhập luật lệ toán modulo[sửa | sửa mã nguồn]

     Thương số (q) và      số dư (r) theo đuổi những hàm của số bị phân tách (a), bằng phương pháp sử dụng những thuật toán không giống nhau

Trong toán học tập, thành quả của luật lệ toán modulo là số dư của luật lệ phân tách với dư. Tuy nhưng những quy ước không giống vẫn tồn bên trên. Máy vi tính và PC với nhiều phương pháp không giống nhau nhằm tàng trữ và đại diện thay mặt cho những số; bởi vậy khái niệm của bọn chúng về luật lệ toán modulo tùy theo ngữ điệu lập trình sẵn hoặc Hartware PC bên dưới cơ bạn dạng.

Trong đa số những khối hệ thống PC, thương số q và số dư r của luật lệ phân tách a cho tới n thỏa mãn

(1)

Tuy nhiên, vẫn tồn tại sự nhập nhằng về lốt nếu như số dư không giống không: nhì lựa lựa chọn rất có thể cho tới số dư xẩy ra, một âm và một dương, và nhì lựa lựa chọn cho tới thương số xẩy ra. Trong lý thuyết số, thường thì số dư dương luôn luôn được lựa chọn, tuy nhiên lựa lựa chọn của những ngữ điệu lập trình sẵn tùy nằm trong nhập ngữ điệu và lốt của a hoặc n.[1] Ngôn ngữ Pascal và ALGOL 68 tiêu xài chuẩn chỉnh lựa chọn số dư dương (hoặc 0) bao gồm Lúc số phân tách là những số âm, so với một vài ba ngữ điệu lập trình sẵn như C90 thì lốt tùy nằm trong nhập setup Lúc hoặc n hoặc a là số âm. Xem bảng để tìm hiểu cụ thể. a modulo 0 là ko xác lập nhập đa số những khối hệ thống, tuy nhiên một trong những khối hệ thống khái niệm là a.

Theo tế bào mô tả của Leijen,

Boute argues that Euclidean division is superior vĩ đại 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 vĩ đại be inferior vĩ đại the other definitions. (Tạm dịch: Boute lập luận rằng luật lệ phân tách với dư là hơn hẳn đối với những luật lệ phân tách không giống về tính chất thường xuyên và những tính chất toán học tập hữu ích, mặc dù với luật lệ phân tách sàn, được Knuth cỗ vũ, cũng là một trong khái niệm đảm bảo chất lượng. Tuy được dùng rộng thoải mái, luật lệ phân tách rút gọn gàng được chứng tỏ kém cỏi rộng lớn những khái niệm không giống.)

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

Tuy nhiên, Boute triệu tập nhập những đặc thù của chủ yếu luật lệ toán modulo và ko reviews thực sự là luật lệ phân tách rút gọn gàng (tiếng Anh: truncated division) đã cho chúng ta thấy sự đối xứng của (-a) div n = -(a div n)a div (-n) = -(a div n), tuy nhiên cũng giống như luật lệ phân tách thường thì. Bởi vì như thế cả nhì luật lệ phân tách sàn và luật lệ phân tách với dư đều không tồn tại tính đối xứng này, trí khôn của Boute tối thiểu là ko trọn vẹn.[cần dẫn nguồn]

Xem thêm: thump là gì

Các sai lầm đáng tiếc thông thường[sửa | sửa mã nguồn]

Nếu thành quả của luật lệ phân tách modulo với lốt của số bị phân tách thì tiếp tục dẫn theo những sai lầm đáng tiếc xứng đáng kinh ngạc.

Ví dụ, nhằm đánh giá tính lẻ của một trong những nguyên vẹn, tớ rất có thể đánh giá số dư Lúc phân tách cho tới với bởi vì 1:

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

Khi ngữ điệu lập trình sẵn với số dư với lốt của số bị phân tách, việc đánh giá tiếp tục sai, tự Lúc 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 đáng tiếc cơ bằng phương pháp đánh giá rằng thành quả không giống 0 (do số dư bởi vì 0 được đánh giá như nhau bất kể dấu):

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

Hay là, bằng sự việc hiểu trước rằng với ngẫu nhiên số lẻ này, số dư modulo rất có thể hoặc bởi vì 1 hoặc −1:

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

Ký hiệu[sửa | sửa mã nguồn]

section này viết lách về luật lệ toán mod nhị phân. Đối với kí hiệu (mod m), coi Quan hệ đồng dư.

Một số PC di động cầm tay với nút của hàm mod(), và nhiều ngữ điệu lập trình sẵn không giống với hàm tương tự động, trình diễn cho tới mod(a, n). Một vài ba ngữ điệu tương hỗ những biễu thức tuy nhiên sử 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 tự cho tới môi trường xung quanh thiếu hụt hàm mod() (chú ý rằng loại 'int' vốn liếng tiếp tục sinh đi ra độ quý hiếm rút gọn gàng a/n)

a - (n * int(a/n))

Vấn đề hiệu suất[sửa | sửa mã nguồn]

Phép toán modulo rất có thể được setup sao cho từng thứ tự luật lệ phân tách với số dư được xem. Đôi với yêu cầu quan trọng đặc biệt, bên trên vài ba Hartware, tồn bên trên những luật lệ toán tương tự động tuy nhiên nhanh chóng rộng lớn. Ví dụ, modulo cho tới lũy quá của 2 rất có thể biễu trình diễn tương tự bởi vì luật lệ toán bitwise AND:

x % 2n == x & (2n - 1)

Ví dụ (giả sử x là số nguyên vẹn dương):

Xem thêm: hedges là gì

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7

Trong những vũ trang và ứng dụng tuy nhiên setup toán tử bitwise hiệu suất cao rộng lớn toán tử modulo, những dạng thay cho thế này rất có thể dẫn theo đo lường nhanh chóng rộng lớn.[4]

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

Tính tương đương[sửa | sửa mã nguồn]

Một số luật lệ toán modulo rất có thể được không ngừng mở rộng tương tự động quý phái những luật lệ toán toán học tập không giống. Điều này còn có tính hữu dụng trong những chứng tỏ mật mã học tập, ví dụ điển hình trao thay đổi khóa Diffie-Hellman.

  • Phần tử đơn vị:
    • (a mod n) mod n = a mod n.
    • nx mod n = 0 với từng số nguyên vẹn dương x.
    • Nếu p là số thành phần ko cần là ước số của b, thì abp−1 mod p = a mod p, dựa trên quyết định lý nhỏ Fermat.
  • Phần tử đảo:
    • [(−a mod n) + (a mod n)] mod n = 0.
    • b−1 mod n kí hiệu thành phần hòn đảo modular, được khái niệm Lúc và chỉ Lúc bn là những số thành phần bên nhau, Lúc vế trái ngược 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 phân tách (định nghĩa): a/b mod n = [(a mod n)(b−1 mod n)] mod n, Lúc vế cần xác lập (là Lúc b và math|n}} là những số thành phần nằm trong nhau). Các tình huống sót lại là ko xác lập.
  • Phép nhân nghịch ngợm đảo: [(ab mod n)(b−1 mod n)] mod n = a mod n.

Dấu Mod trong những ngữ điệu lập trình[sửa | sửa mã nguồn]

Toán tử modulo của số nguyên vẹn trong không ít ngữ điệu lập trình sẵn không giống nhau
Ngôn ngữ Toán tử Kết trái ngược với nằm trong lốt với
ABAP MOD Luôn ko âm
ActionScript % Số bị chia
Ada mod Số chia
rem Số bị chia
ALGOL 68 ÷×, mod Luôn ko âm
AMPL mod Số bị chia
APL |[2] 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 nằm trong thiết lập đặt
div ngôn ngữ lập trình
C++ (ISO 1998) % Định nghĩa tùy nằm trong thiết lập đặt[5]
div Số bị chia
C (ISO 1999) %, div Số bị chia[6]
C++ (ISO 2011) %, div Số bị chia
C# % Số bị chia
Clarion % Số bị chia
Clojure mod Số chia
rem Số bị chia
COBOL[3] FUNCTION MOD Số chia
CoffeeScript % Số bị chia
%% Số chia[7]
ColdFusion %, MOD Số bị chia
Common Lisp mod Số chia
rem Số bị chia
Construct 2 %
D % Số bị chia[8]
Dart % Luôn ko â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 nằm trong nhập thiết lập đặ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 |[4] 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 ko â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 ko dấu
%% toán tử modulo với dấu
Oberon MOD Số chia[5]
Object Pascal, Delphi mod Số bị chia
OCaml mod Số bị chia
Occam \ Số bị chia
Pascal (ISO-7185 and -10206) mod Luôn ko âm
Perl % Số chia[6]
PHP % Số bị chia
PIC BASIC Pro \\ Số bị chia
PL/I mod Số phân tách (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 ko âm[9]
mod0 Nearest vĩ đại zero[9]
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 ko â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 ko âm
Toán tử modulo của số chấm động trong không ít ngữ điệu lập trình
Ngôn ngữ Toán tử Kết trái ngược với nằm trong lốt với
ABAP MOD Luôn ko âm
C (ISO 1990) fmod Số bị chia[10]
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 ko â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 ko â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[sửa | sửa mã nguồn]

  • Modulo (Chống sai lầm lẫn) và modulo (biệt ngữ) – nhiều phương pháp dùng kể từ modulo, toàn bộ đều đột biến kể từ cuốn sách Nhập môn số học tập tế bào đun (tựa Anh:introduction of modular arithmetic) của Carl F. Gauss năm 1801.
  • Lũy quá Modular

Chú thích[sửa | sửa mã nguồn]

  • ^ Perl dùng toán tử modulo số học tập tuy nhiên song lập với PC. Để hiểu biết thêm ví dụ và những nước ngoài lệ, coi tư liệu Perl về toán tử nhân.[11]
  • ^ Trên mặt mũi toán học tập, nhì lựa lựa chọn này là nhì nhập số vô số lựa lựa chọn đã có sẵn nhập [[remainder#The inequality satisfied by the remainder|bất đẳng thức vừa lòng bởi vì một trong những dư]]
  • ^ Số phân tách cần là dương, nếu như không ko xác lập.
  • ^ Như được thiết lập dặt nhập ACUCOBOL, Micro Focus COBOL, và với thẻ là những ngữ điệu khác
  • ^ ^ Trật tự động thông số hòn đảo ngược, ví dụ, α|ω computes , số dư Lúc phân tách ω cho tới α.

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Knuth, Donald. E. (1972). The Art of Computer Programming. Addison-Wesley.
  2. ^ Boute, Raymond T. (tháng 4 năm 1992). “The Euclidean definition of the functions div and mod”. ACM Transactions on Programming Languages and Systems. ACM Press (New York, NY, USA). 14 (2): 127–144. doi:10.1145/128861.128862.
  3. ^ Leijen, Daan (Tháng 3 năm 2001). “Division and Modulus for Computer Scientists (Tạm dịch: Phép phân tách và Phép Modulus của những ngôi nhà khoa học tập máy tính)” (PDF). Truy cập ngày 25 mon 12 năm 2014.
  4. ^ Horvath, Adam (ngày 5 mon 7 năm 2012). “Faster division and modulo operation - the power of two”.
  5. ^ “ISO/IEC 14882:2003: programming languages – C++”. 5.6.4: International Organization for Standardization (ISO), International Electrotechnical Commission (IEC). 2003. Quản lý CS1: vị trí (liên kế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".
  6. ^ open-std.org, mục 6.5.5
  7. ^ CoffeeScript operators
  8. ^ “Expressions”. D ngữ điệu lập trình sẵn 2.0. Digital Mars. Truy cập ngày 29 mon 7 năm 2010.
  9. ^ a b r6rs.org
  10. ^ “ISO/IEC 9899:1990: programming languages – C”. 7.5.6.4: ISO, IEC. 1990. Quản lý CS1: vị trí (liên kết) "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 vãn the magnitude of y.".
  11. ^ Perl documentation