mod là phép toán gì

Bách khoa toàn thư hé Wikipedia

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

Bạn đang xem: mod là phép toán 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 phép tắc phân tách đem dư Euclid của a cho tới n. Ví dụ, biểu thức "5 mod 2" vì chưng 1 vì thế 5 phân tách cho tới 2 đem thương số là 2 là số dư là một trong những, trong những khi "9 mod 3" vì chưng 0 tự 9 phân tách 3 đem thương số là 3 và số dư 0; không thể gì vô phép tắc trừ của 9 cho tới 3 nhân 3. (Lưu ý rằng triển khai phép tắc phân tách 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ư phép tắc 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 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ì chưng 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 xây dựng.) Xem số học tập mô-đun nhằm dò thám những quy ước cũ rộng lớn và tương quan được vận dụng vô lý thuyết số.

Khi hoặc a hoặc n là số âm, khái niệm cơ phiên bản bị đánh tan và những ngữ điệu xây dựng không giống nhau trong công việc khái niệm những sản phẩm này.

Tính toán phần dư vô phép tắc toán modulo[sửa | sửa mã nguồn]

Trong toán học tập, sản phẩm của phép tắc toán modulo là số dư của phép tắc phân tách đem 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 đem rất nhiều cách thức không giống nhau nhằm tàng trữ và thay mặt đại diện cho những số; vì thế khái niệm của bọn chúng về phép tắc toán modulo tùy theo ngữ điệu xây dựng hoặc Hartware PC bên dưới cơ phiên bản.

Trong đa số những khối hệ thống PC, thương số q và số dư r của phép tắc 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ề vệ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 xây dựng tùy nằm trong vô ngữ điệu và vệt của a hoặc n.^[1] Ngôn ngữ Pascal và ALGOL 68 chi tiêu chuẩn chỉnh lựa chọn số dư dương (hoặc 0) bao gồm khi số phân tách 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 vô thiết lập 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 vô đ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 đồ 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 phép tắc phân tách đem dư là hơn hẳn đối với những phép tắc phân tách 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ầu với phép tắc phân tách sàn, được Knuth cỗ vũ, cũng là một trong những khái niệm chất lượng tốt. Tuy được dùng thoáng rộng, phép tắc phân tách rút gọn gàng được minh chứng thông thường 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 vô những đặc điểm của chủ yếu phép tắc toán modulo và ko reviews thực sự là phép tắc phân tách 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), nhưng mà cũng tương tự như phép tắc phân tách thường thì. Bởi vì thế cả nhị phép tắc phân tách sàn và phép tắc phân tách đem dư đều không tồn tại tính đối xứng này, phoán đoán của Boute tối thiểu là ko toàn vẹn.^{[cần dẫn nguồn]}

Xem thêm: dấu hiệu nhận biết tứ giác nội tiếp

Các sai lầm không mong muốn thông thường[sửa | sửa mã nguồn]

Nếu sản phẩm của phép tắc phân tách modulo đem vệt của số bị phân tách thì tiếp tục dẫn theo những sai lầm không mong muốn 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, tao rất có thể đánh giá số dư khi phân tách cho tới đem vì chưng 1:

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

Khi ngữ điệu xây dựng đem số dư đem vệt của số bị phân tách, việc đánh giá tiếp tục sai, tự 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 không mong muốn ê bằng phương pháp đánh giá rằng sản phẩm không giống 0 (do số dư vì chưng 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ì chưng 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 ghi chép về phép tắc 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 đem nút của hàm mod(), và nhiều ngữ điệu xây dựng không giống đem 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 nhưng mà người 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 thốn hàm mod() (chú ý rằng loại 'int' vốn liếng đang đượ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 thiết lập sao cho từng phen phép tắc phân tách với số dư được xem. Đôi với nhu yếu đặc biệt quan trọng, bên trên vài ba Hartware, tồn bên trên những phép tắc 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 thao diễn tương tự vì chưng phép tắc 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: làm tròn đến hàng đơn vị

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

Trong những trang bị và ứng dụng nhưng mà thiết lập 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 đem dạng expression % constant vô ê constant là lũy quá của 2 và tự động hóa thiết lập bọn chúng trở nên expression & (constant-1). Vấn đề này được cho phép ghi chép mã rõ nét rộng lớn nhưng mà 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 nhưng mà sản phẩm của phép tắc toán modulo đem 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ố vẹn toàn ko vệt. Bởi vì 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ố phép tắc toán modulo rất có thể được không ngừng mở rộng tương tự động sang trọng những phép tắc 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ắc ko cần là ước số của b, thì ab^p−1 mod p = a mod p, dựa vào tấp 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ắc bên cạnh nhau, khi vế trái ngược 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 tách (định nghĩa): a/b mod n = [(a mod n)(b⁻¹ mod n)] mod n, khi vế cần xác lập (là khi b và math|n}} là những số yếu tắc 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 tặc đả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ữ) – rất nhiều cách thức 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 nhưng mà 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ày toán học tập, nhị lựa lựa chọn này là nhị vô số vô số lựa lựa chọn đã có sẵn vô [[remainder#The inequality satisfied by the remainder|bất đẳng thức vừa lòng vì chưng một trong những dư]]
• ^ Số phân tách cần là dương, còn nếu như không ko xác lập.
• ^ Như được thiết lập dặt vô ACUCOBOL, Micro Focus COBOL, và đem 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 tách ω cho tới α.

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