Phép toán modulo – Wikipedia tiếng Việt

250px Divmod.svg Thương số (

q

) và số dư (

r

) theo những hàm của số bị chia (

a

), bằng cách tiêu dùng những thuật toán khác nhauThương số ( ) và ) theo những hàm của số bị chia ( ), bằng cách tiêu dùng những thuật toán khác nhau

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ố (thỉnh thoảng được gọi là modulus).

Cho hai 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 chia mang dư Euclid của a cho n. Ví dụ, biểu thức "5 mod 2" bằng 1 vì 5 chia cho 2 mang thương số là 2 là số dư là 1, trong lúc "9 mod 3" bằng 0 do 9 chia 3 mang thương số là 3 và số dư 0; ko 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 sử dụng máy tính cầm tay sẽ ko hiển thị kết quả giống như phép toán này; thương số sẽ được trình diễn dưới dạng phần thập phân.)

Mặc dù thường được thực hiện lúc an đều là số nguyên, nhiều hệ tính toán cho phép sử dụng những 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 n là tù 0 tới n − 1. (a mod 1 luôn bằng 0; a mod 0 là ko xác định, mang thể trả về lỗi chia cho số 0 trong nhiều tiếng nói lập trình.) Xem số học mô-đun để tìm những quy ước cũ hơn và liên quan được vận dụng trong lý thuyết số.

Lúc hoặc a hoặc n là số âm, khái niệm cơ bản bị phá vỡ và những tiếng nói lập trình khác nhau trong việc khái niệm những kết quả này.

Tính toán phần dư trong phép toán modulo[sửa|sửa mã nguồn]

Trong toán học, hiệu quả của phép toán modulo là số dư của phép chia mang dư. Tuy vậy những quy ước khác vẫn sống sót. Máy vi tính và máy tính mang nhiều cách khác nhau để tích trữ và đại diện thay mặt cho những số ; do đó khái niệm của chúng về phép toán modulo nhờ vào vào ngôn từ 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 những hệ thống máy tính, thương số q và số dư r của phép chia a cho n thỏa mãn

q ∈ Z a = n q + r | r | < | n | { displaystyle { begin { aligned } q , và in mathbb { Z } a , và = nq + r | r | , và < | n | end { aligned } } }26e400cfa04a88df0482f7e69b4e9304dabede4a

(1)

Tuy nhiên, vẫn còn sự nhập nhằng về dấu nếu số dư khác ko: hai lựa chọn mang 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 những tiếng nói lập trình tùy thuộc vào tiếng nói và dấu của a hoặc n. Tiếng nói Pascal và ALGOL 68 tiêu chuẩn chọn số dư dương (hoặc 0) kể cả lúc số chia là những số âm, đối với một vài tiếng nói lập trình như C90 thì dấu tùy thuộc vào cài đặt lúc hoặc n hoặc a là số âm. Xem bảng để biết chi tiết. a modulo 0 là ko xác định trong hầu hết những hệ thống, mặc dù một số hệ thống định tức là a.

Theo miêu tả của Leijen ,

Boute argues that Euclidean division is superior to 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 to be inferior to the other definitions. ( Tạm dịch : Boute lập luận rằng phép chia mang dư là tiêu biểu vượt trội so với những phép chia khác về tính đều đặn và những tính chất toán học hữu dụng, mặc dầu với phép chia sàn, được Knuth ủng hộ, cũng là một khái niệm tốt. Tuy được sử dụng thoáng rộng, phép chia rút gọn được chứng tỏ kém hơn những khái niệm khác. )Division and Modulus for Computer Scientists[9]— Daan Leijen ,

Tuy nhiên, Boute tập trung vào những tính chất của chính phép toán modulo và ko thẩm định sự thực là phép chia rút gọn (tiếng Anh: truncated division) cho thấy sự đối xứng của (-a) div n = -(a div n) và a div (-n) = -(a div n), 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 mang dư đều ko mang tính đối xứng này, suy đoán của Boute ít nhất là ko toàn diện.[cần dẫn nguồn]

Những sai trái đáng tiếc thường thì[sửa|sửa mã nguồn]

Nếu hiệu quả của phép chia modulo mang dấu của số bị chia thì sẽ dẫn tới những sai trái đáng tiếc đáng sửng sốt .Ví dụ, để rà soát tính lẻ của một số nguyên, ta hoàn toàn mang thể rà soát số dư lúc chia cho mang bằng 1 :

boolis_odd(intn){
returnnphần trăm2= =1;
}

Lúc tiếng nói lập trình mang số dư mang dấu của số bị chia, việc rà soát sẽ sai, do lúc n (số bị chia) là số âm lẻ, n mod 2 trả về −1, và hàm trả về false.

Sở hữu thể sửa lại sai trái đáng tiếc đó bằng cách rà soát rằng hiệu quả khác 0 ( do số dư bằng 0 được xem xét như nhau bất kể dấu ) :

boolis_odd(intn){
returnnphần trăm2

!=

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 hoàn toàn mang thể hoặc bằng 1 hoặc − 1 :

boolis_odd(intn) 

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

Một số máy tính cầm tay mang nút của hàm mod(), và nhiều tiếng nói lập trình khác mang hàm tương tự, trình diễn cho mod(a, n). Một vài tiếng nói tương trợ những biễu thức mà tiêu 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 mod() (chú ý rằng kiểu 'int' vốn đã sinh ra trị giá rút gọn 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 hoàn toàn mang thể được thiết lập sao cho mỗi lần phép chia với số dư được tính. Đôi với nhu yếu đặc trưng quan yếu, trên vài phần cứng, sống sót những phép toán tựa như nhưng nhanh hơn. Ví dụ, modulo cho lũy thừa của 2 hoàn toàn mang thể biễu diễn tương tự bởi phép toán bitwise AND :

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

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

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

Trong những thiết bị và ứng dụng mà setup toán tử bitwise hiệu suất cao hơn toán tử modulo, những dạng thay thế sửa chữa này hoàn toàn mang thể dẫn tới giám sát nhanh hơn. [ 10 ]

Những trình biên dịch tối ưu hóa mang thể nhận diện những biểu thức mang 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à ko tác động tới hiệu suất. Cách tối ưu hóa này ko vận dụng cho những tiếng nói mà kết quả của phép toán modulo mang cùng dẫu với số bị chia (bao gồm C), trừ phi số bị chia là kiểu số nguyên ko dấu. Bởi vì nếu số bị chia là số âm thì modulo sẽ là số âm trong lúc expression & (constant-1) sẽ luôn dương.

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

Một số phép toán modulo hoàn toàn mang thể được lan rộng ra tựa như sang những phép toán toán học khác. Điều này mang tính hữu dụng trong những chứng tỏ mật mã học, ví dụ tiêu biểu trao đổi khóa Diffie-Hellman .

  • Phần tử đơn vị:
    • (a mod n) mod n = a mod n

      .

    • nx mod n = 0

      với mọi số nguyên dương

      x

      .

    • Nếu

      p

      là số nhân tố ko phải là ước số của

      b

      , thì

      abp−1 mod p = a mod p

      , dựa theo định lý nhỏ Fermat.

  • Phần tử đảo:
    • [(−a mod n) + (a mod n)] mod n = 0

      .

    • b−1 mod n

      kí hiệu phần tử đảo modular, được khái niệm lúc và chỉ lúc

      b

      n

      là những số nhân tố cùng nhau, lúc vế trái 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 chia (khái niệm):

    a

    /

    b

    mod n = [(a mod n)(b−1 mod n)] mod n

    , lúc vế phải xác định (là lúc

    b

    và math|n}} là những số nhân tố cùng nhau). Những trường hợp còn lại là ko xác định.

  • Phép nhân nghịch đảo:

    [(ab mod n)(b−1 mod n)] mod n = a mod n

    .

Source: https://bloghong.com
Category: Là Gì