Phép toán chia lấy dư

Trong lĩnh vực tính toán, phép toán chia lấy dư dùng để xác định phần dư sau khi chia hai số (thường được gọi là modulus).

Khi có hai số, (số bị chia) a và (số chia) n, a chia lấy dư n (viết tắt là a mod n) là phần dư của phép chia có dư Euclid giữa a và n. Ví dụ, biểu thức '5 mod 2' cho kết quả là 1 vì 5 chia cho 2 có thương là 2 và phần dư là 1, trong khi '9 mod 3' cho kết quả là 0 do 9 chia cho 3 có thương là 3 và phần dư là 0; không còn gì sau khi trừ 9 với 3 nhân 3. (Lưu ý rằng phép chia trên máy tính có thể không cho kết quả giống như phép toán này; thương có thể được biểu diễn dưới dạng số thập phân.)

Mặc dù phép toán này thường áp dụng cho các số nguyên, một số hệ thống tính toán cũng cho phép sử dụng các kiểu số khác. Phần dư của một phép chia modulo nguyên với n thường nằm trong khoảng từ 0 đến n − 1. (a mod 1 luôn cho kết quả là 0; a mod 0 không xác định và có thể gây lỗi chia cho 0 trong nhiều ngôn ngữ lập trình.) Xem số học mô-đun để tìm hiểu thêm về các quy ước và lý thuyết số liên quan.

Khi một trong hai số a hoặc n là số âm, định nghĩa cơ bản có thể bị ảnh hưởng và các ngôn ngữ lập trình có thể xử lý các kết quả này theo cách khác nhau.

Tính toán phần dư trong phép toán chia lấy dư

Trong toán học, phép toán chia lấy dư cho kết quả là phần dư của phép chia có dư. Tuy nhiên, các quy ước khác cũng tồn tại. Các máy tính và máy vi tính có cách lưu trữ và đại diện số khác nhau, vì vậy định nghĩa về phép toán chia lấy dư có thể phụ thuộc vào ngôn ngữ lập trình hoặc phần cứng của máy tính.

Trong hầu hết các hệ thống máy tính, thương số q và phần dư r của phép chia a cho n phải thỏa mãn

(1)

Tuy nhiên, vẫn có sự không nhất quán về dấu khi phần dư không bằng 0: có thể có hai lựa chọn cho phần dư, một âm và một dương, và hai lựa chọn cho thương số. Trong lý thuyết số, thường chọn phần dư dương, nhưng trong các ngôn ngữ lập trình, kết quả có thể khác tùy thuộc vào ngôn ngữ và dấu của a hoặc n. Ví dụ, Pascal và ALGOL 68 tiêu chuẩn chọn phần dư dương (hoặc 0) ngay cả khi số chia âm, trong khi một số ngôn ngữ như C90 có thể thay đổi kết quả dựa trên cài đặt khi n hoặc a là số âm. Xem bảng để biết chi tiết. Phép toán a modulo 0 thường không xác định trong nhiều hệ thống, mặc dù một số định nghĩa là a.

Theo quan điểm của Leijen,

Boute cho rằng phép chia Euclidean vượt trội hơn 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, mặc dù phép chia sàn, được Knuth ủng hộ, cũng là một định nghĩa tốt. Dù được sử dụng rộng rãi, phép chia rút gọn lại chứng tỏ là kém hơn các định nghĩa khác.

— Daan Leijen, Division and Modulus for Computer Scientists

Tuy nhiên, Boute tập trung vào các đặc điểm của phép toán modulo mà không đánh giá việc phép chia rút gọn (truncated division) thể hiện sự đối xứng của (-a) div n = -(a div n) và a div (-n) = -(a div n), giống như phép chia thông thường. Do cả phép chia sàn và phép chia có dư đều thiếu tính đối xứng này, đánh giá của Boute ít nhất là không toàn diện.

Các lỗi thường gặp

Nếu kết quả phép chia modulo có dấu tương tự như số bị chia, điều này có thể dẫn đến những kết quả không mong muốn.

Chẳng hạn, để xác định xem một số nguyên có phải là số lẻ hay không, ta thường kiểm tra phần dư khi chia cho 2 xem có bằng 1 không:

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

Khi ngôn ngữ lập trình sử dụng phép chia với phần dư có dấu của số bị chia, kiểm tra sẽ không chính xác. Nếu n (số bị chia) là số âm lẻ, n mod 2 sẽ trả về −1, dẫn đến hàm kiểm tra trả về false.

Để khắc phục lỗi này, ta có thể kiểm tra xem phần dư có khác 0 hay không (bởi vì phần dư 0 được coi là giống nhau bất kể dấu):

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

Hoặc, bạn có thể nhớ rằng phần dư của phép chia với số lẻ có thể là 1 hoặc −1:

bool is_odd(int n)
  

    
  
   {
 return n % 2 == 1 || n % 2 == -1;
}

Biểu tượng

Nhiều máy tính cầm tay có nút chức năng mod(), và nhiều ngôn ngữ lập trình cũng cung cấp hàm tương tự để tính toán mod(a, n). Một số ngôn ngữ hỗ trợ các ký hiệu như '%', 'mod', hoặc 'Mod' để thực hiện phép toán modulo hoặc lấy số dư, chẳng hạn như

a % n

hoặc

a mod n

hoặc có thể dùng trong các môi trường không có hàm mod() (lưu ý rằng kiểu 'int' thường sinh ra giá trị rút gọn như a/n)

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

Vấn đề hiệu suất

Phép toán modulo có thể được thực hiện sao cho mỗi phép chia với số dư được tính toán chính xác. Đối với những yêu cầu đặc biệt, một số phần cứng có thể sử dụng các phép toán tương tự nhưng nhanh hơn. Ví dụ, phép toán modulo với lũy thừa của 2 có thể được thay thế bằng phép toán AND bitwise:

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

Ví dụ (giả sử x là một 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à phép toán bitwise thực hiện nhanh hơn phép toán modulo, việc sử dụng các phương pháp thay thế này có thể giúp cải thiện hiệu suất.

Các trình biên dịch tối ưu hóa có khả năng nhận diện các biểu thức dạng expression % constant với constant là lũy thừa của 2 và tự động chuyển đổi chúng thành expression & (constant-1). Điều này giúp mã nguồn trở nên rõ ràng hơn mà không làm giảm hiệu suất. Tuy nhiên, 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 phải có cùng dấu với số bị chia (như trong C), trừ khi số bị chia là số nguyên không dấu. Nếu số bị chia là số âm, phép modulo sẽ cho kết quả âm, trong khi expression & (constant-1) luôn cho kết quả 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 rất hữu ích trong các chứng minh mật mã học, chẳng hạn như trao đổi khóa Diffie-Hellman.

• Phần tử đơn vị:
  • (a mod n) mod n = a mod n.
  • n mod n = 0 với mọi số nguyên dương x.
  • Nếu p là số nguyên tố không chia hết cho b, thì ab mod p = a mod p, theo định lý nhỏ Fermat.
• Phần tử đảo:
  • [(−a mod n) + (a mod n)] mod n = 0.
  • b mod n kí hiệu phần tử đảo modular, được định nghĩa khi và chỉ khi b và n là các số nguyên tố cùng nhau, khi vế trái 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 chia (định nghĩa): a/b mod n = [(a mod n)(b mod n)] mod n, khi vế phải xác định (tức là khi b và n là các số nguyên tố cùng nhau). Các trường hợp khác là không xác định.
• Phép nhân nghịch đảo: [(ab mod n)(b mod n)] mod n = a mod n.

Dấu hiệu Mod trong các ngôn ngữ lập trình

• Thuật ngữ 'Modulo' và 'modulo' – từ 'modulo' được sử dụng theo nhiều cách khác nhau, tất cả đều bắt nguồn từ cuốn sách của Carl F. Gauss năm 1801 về số học mô đun (tựa Anh: 'introduction of modular arithmetic').
• Lũy thừa Modular

Chú thích

• ^ Perl sử dụng toán tử modulo số học không phụ thuộc vào phần cứng. Xem tài liệu Perl để biết thêm ví dụ và các trường hợp đặc biệt.
• ^ Về mặt toán học, đây là một trong nhiều cách lựa chọn có sẵn theo [[remainder#The inequality satisfied by the remainder|bất đẳng thức thỏa mãn với số dư]]
• ^ Số chia phải là số dương, nếu không sẽ không xác định được.
• ^ Như được định nghĩa trong ACUCOBOL, Micro Focus COBOL, và một số ngôn ngữ khác.
• ^ ^ Thứ tự tham số ngược, ví dụ, α|ω tính toán số dư của ω khi chia cho α.