modulus là gì

Bách khoa toàn thư há 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 chia 2 số (đôi khi được gọi là modulus).

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

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

Mặc cho dù thông thường được triển khai khi a và n đều là số vẹn toà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 vẹn toàn của n là kể từ 0 cho tới n − 1. (a mod 1 luôn luôn vày 0; a mod 0 là ko xác lập, rất có thể trả về lỗi phân chia mang đến số 0 trong vô số nhiều ngữ điệu xây dựng.) 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 xây dựng không giống nhau trong các công việc khái niệm những sản phẩm này.

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

Trong toán học tập, sản phẩm của luật lệ toán modulo là số dư của luật lệ phân chia sở hữu dư. Dù thế những quy ước không giống vẫn tồn bên trên. Máy vi tính và PC sở hữu vô số phương pháp không giống nhau nhằm tàng trữ và thay mặt cho những số; vì thế khái niệm của bọn chúng về luật lệ toán modulo tùy theo ngữ điệu xây dựng 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 chia a mang đến n thỏa mãn

(1)

Tuy nhiên, vẫn còn đó sự nhập nhằng về vết nếu như số dư không giống không: nhì lựa lựa chọn rất có thể mang đến số dư xẩy ra, một âm và một dương, và nhì lựa lựa chọn mang đến 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 xây dựng tùy nằm trong nhập ngữ điệu và vết của a hoặc n.^[1] Ngôn ngữ Pascal và ALGOL 68 chi phí chuẩn chỉnh lựa chọn số dư dương (hoặc 0) cho dù là khi số phân chia là những số âm, so với một vài ba ngữ điệu xây dựng như C90 thì vết tùy nằm trong nhập setup khi 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 vậy một trong những khối hệ thống khái niệm là a.

Theo tế bào miêu tả của Leijen,

Boute argues that Euclidean division is superior đồ sộ 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 đồ sộ be inferior đồ sộ the other definitions. (Tạm dịch: Boute lập luận rằng luật lệ phân chia sở hữu dư là hơn hẳn đối với những luật lệ phân chia không giống về tính chất đều đều 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 chia sàn, được Knuth cỗ vũ, cũng là một trong những khái niệm chất lượng. Tuy được dùng thoáng rộng, luật lệ phân chia rút gọn gàng được minh chứng 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 chia rút gọn gàng (tiếng Anh: truncated division) đã cho chúng ta biết sự đối xứng của (-a) div n = -(a div n) và a div (-n) = -(a div n), tuy nhiên cũng tương tự luật lệ phân chia thường thì. Bởi vì như thế cả nhì luật lệ phân chia sàn và luật lệ phân chia sở hữu 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 toàn vẹn.^{[cần dẫn nguồn]}

Xem thêm: professionalism là gì

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

Nếu sản phẩm của luật lệ phân chia modulo sở hữu vết của số bị phân chia thì tiếp tục kéo đến 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 vẹn toàn, tớ rất có thể đánh giá số dư khi phân chia mang đến sở hữu vày 1:

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

Khi ngữ điệu xây dựng sở hữu số dư sở hữu vết của số bị phân chia, việc đánh giá tiếp tục sai, bởi 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 đáng tiếc tê liệt bằng phương pháp đánh giá rằng sản phẩm không giống 0 (do số dư vày 0 được kiểm tra 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ào là, số dư modulo rất có thể hoặc vày 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 sở hữu nút của hàm mod(), và nhiều ngữ điệu xây dựng không giống sở hữu hàm tương tự động, màn trình diễn mang đến 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ự mang đến môi trường xung quanh thiếu thốn hàm mod() (chú ý rằng loại 'int' vốn liếng vẫn 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 phen luật lệ phân chia 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 thời gian nhanh rộng lớn. Ví dụ, modulo mang đến lũy quá của 2 rất có thể biễu biểu diễn tương tự vày luật lệ toán bitwise AND:

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

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

Xem thêm: trip over 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ể kéo đến đo lường thời gian nhanh 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 sở hữu dạng expression % constant nhập tê liệt 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õ rệ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 sản phẩm của luật lệ toán modulo sở hữu nằm trong dẫu với số bị phân chia (bao bao gồm C), trừ phi số bị phân chia là loại số vẹn toàn ko vết. Bởi vì như thế nếu như số bị phân chia là số âm thì modulo được xem là số âm trong lúc 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 số minh chứng 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.
  • n^x mod n = 0 với từng số vẹn toàn dương x.
  • Nếu p là số yếu tố ko nên là ước số của b, thì ab^p−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⁻¹ mod n kí hiệu thành phần hòn đảo modular, được khái niệm khi và chỉ khi b và n là những số yếu tố bên nhau, khi vế trái khoáy xác định: [(b⁻¹ 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 chia (định nghĩa): a/b mod n = [(a mod n)(b⁻¹ mod n)] mod n, khi vế nên xác lập (là khi b và math|n}} là những số yếu tố nằm trong nhau). Các tình huống còn sót lại là ko xác lập.
• Phép nhân nghịch ngợm đảo: [(ab mod n)(b⁻¹ mod n)] mod n = a mod n.

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

Xem thêm[sửa | sửa mã nguồn]

• Modulo (Chống khuyết điểm lẫn) và modulo (biệt ngữ) – vô số 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 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ó trước nhập [[remainder#The inequality satisfied by the remainder|bất đẳng thức thỏa mãn nhu cầu vày một trong những dư]]
• ^ Số phân chia nên là dương, còn 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à sở hữu 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ư khi phân chia ω mang đến α.

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