Dasar pemikiran apa yang digunakan ketika desainer bahasa pemrograman memutuskan tanda apa yang dihasilkan dari operasi modulo?

9

Akan melalui Modulo operasi (jalan saya masuk sambil menjelajahi perbedaan antara remdanmod ) saya datang di:

Dalam matematika hasil operasi modulo adalah sisa dari divisi Euclidean. Namun, konvensi lain dimungkinkan. Komputer dan kalkulator memiliki berbagai cara untuk menyimpan dan mewakili angka; sehingga definisi mereka tentang operasi modulo tergantung pada bahasa pemrograman dan / atau perangkat keras yang mendasarinya.

Pertanyaan:

  • Akan melalui divisi Euclidean saya menemukan bahwa remainnder dari operasi ini selalu positif (atau 0). Apa batasan perangkat keras komputer yang mendasari perancang bahasa pemrograman berbeda dari matematika?
  • Setiap bahasa pemrograman menetapkannya, atau tidak terdefinisi, aturan yang sesuai dengan hasil operasi modulo mendapatkan tanda itu. Dasar pemikiran apa yang diadopsi saat membuat aturan ini? Dan jika perangkat keras yang mendasarinya memprihatinkan, maka seharusnya aturan tidak berubah sesuai dengan itu, terlepas dari bahasa pemrograman?
Jari-jari yang berdarah
sumber
1
Dalam kode saya, saya hampir selalu membutuhkan modulo bukan sisanya. Tidak tahu mengapa sisanya sangat populer.
CodesInChaos
8
Terkait Apa bedanya? Remainder vs Modulus - Blog Eric Lippert (oleh salah satu desainer C #, tapi saya yakin dia bergabung dengan tim setelah keputusan ini dibuat)
CodesInChaos
1
Jika Anda terus membaca artikel Wikipedia (di luar bagian yang Anda kutip), itu menjelaskan apa yang Anda kutip dengan cukup baik. Bagaimana dengan penjelasan itu yang membuat Anda bingung?
Robert Harvey
1
Satu pertanyaan terkait adalah operasi mana yang secara langsung memetakan ke instruksi CPU. Dalam implementasi c didefinisikan, yang sesuai dengan filosofi c pemetaan langsung ke perangkat keras pada platform sebanyak mungkin. Jadi itu tidak menentukan hal-hal yang mungkin berbeda di antara CPU.
CodesInChaos
5
Pemrograman @BleedingFingers sering menggunakan divisi integer yang menuju nol, misalnya (-3)/2 == -1. Definisi ini dapat bermanfaat. Ketika Anda ingin %konsisten dengan divisi ini memenuhi x == (x/y)*y + x % yAnda berakhir dengan definisi yang %digunakan dalam C #.
CodesInChaos

Jawaban:

6

Perangkat keras dari semua komputer modern cukup kuat untuk mengimplementasikan operasi mod dari salah satu tanda tanpa dampak kinerja (atau sepele). Ini bukan alasannya.

Harapan umum dari kebanyakan bahasa komputer adalah bahwa (a div b) * b + (a mod b) = a. Dengan kata lain, div dan mod yang dipertimbangkan bersama-sama membagi angka menjadi beberapa bagian yang andal dapat disatukan kembali. Persyaratan ini eksplisit dalam standar C ++. Konsep ini terkait erat dengan pengindeksan array multi dimensi. Saya sudah sering menggunakannya.

Dari sini dapat dilihat bahwa div dan mod akan mempertahankan tanda a jika b positif (seperti biasanya).

Beberapa bahasa menyediakan fungsi 'rem ()' yang terkait dengan mod dan memiliki beberapa pembenaran matematis lainnya. Saya tidak pernah perlu menggunakan ini. Lihat misalnya frem () dalam Gnu C. [diedit]

david.pfx
sumber
Saya pikir itu rem(a,b)lebih mirip mod(a,b)jika itu positif atau mod(a,b) + btidak.
user40989
3
(a div b) * b + (a mod b) = a- ini, sangat banyak. Bahkan, bertentangan dengan bagaimana Wikipedia menjelaskan memperluasnya ke angka negatif di divisi Euclidean (terutama "Sisanya adalah satu-satunya dari empat angka yang tidak pernah bisa negatif.") Membingungkan saya karena saya selalu diajarkan bahwa sisanya dapat negatif di setiap kelas matematika di tingkat itu.
Izkata
@ user40989: Saya katakan saya tidak akan pernah menggunakannya. Lihat edit!
david.pfx
4

Untuk pemrograman biasanya Anda inginkan X == (X/n)*n + X%n; oleh karena itu bagaimana modulo didefinisikan tergantung pada bagaimana pembagian integer didefinisikan.

Dengan pemikiran ini, Anda benar-benar bertanya " Alasan apa yang digunakan ketika desainer bahasa pemrograman memutuskan bagaimana divisi integer bekerja? "

Sebenarnya ada sekitar 7 pilihan:

  • bulat hingga tak terbatas negatif
  • bulat hingga tak terbatas positif
  • bulat ke nol
  • beberapa versi "bulat ke terdekat" (dengan perbedaan dalam bagaimana sesuatu seperti 0,5 dibulatkan)

Sekarang pertimbangkan -( (-X) / n) == X/n. Saya ingin ini benar, karena hal lain tampaknya tidak konsisten (itu berlaku untuk floating point) dan tidak logis (kemungkinan penyebab bug dan juga potensi optimasi yang terlewatkan). Ini membuat 2 pilihan pertama untuk pembagian bilangan bulat (pembulatan menuju kedua tak terbatas) tidak diinginkan.

Semua pilihan "putaran ke terdekat" terasa menyebalkan untuk pemrograman, terutama ketika Anda melakukan sesuatu seperti bitmap (misalnya offset = index / 8; bitNumber = index%8;).

Yang meninggalkan pembulatan ke nol sebagai pilihan "berpotensi paling waras", yang menyiratkan bahwa modulo mengembalikan nilai dengan tanda yang sama dengan pembilang (atau nol).

Catatan: Anda juga akan mencatat bahwa sebagian besar CPU (semua CPU yang saya ketahui) melakukan pembagian integer dengan cara yang sama "bulat ke nol". Ini mungkin karena alasan yang sama.

Brendan
sumber
Tetapi divisi pemotongan memiliki inkonsistensi sendiri juga: Divisi pecah (a+b*c)/b == a % bdan a >> n == a / 2 ** n, yang divisi lantai memiliki perilaku waras.
dan04
Contoh pertama Anda tidak masuk akal. Contoh kedua Anda adalah kekacauan untuk programmer: untuk positif dan positif dan konsisten, untuk negatif dan positif tergantung pada bagaimana pergeseran kanan didefinisikan (aritmatika vs logis), dan untuk negatif dan rusak (misalnya 1 >> -2 == a / 2 ** (-2)).
Brendan
Contoh pertama adalah salah ketik: yang saya maksudkan (a + b * c) % b == a % b, yaitu %operatornya adalah pembagi-periodik dalam dividen, yang seringkali penting. Sebagai contoh, dengan pembagian lantai, day_count % 7memberi Anda hari dalam seminggu, tetapi dengan divisi pemotongan, ini istirahat untuk tanggal sebelum zaman.
dan04
0

Pertama, saya akan mengulangi bahwa modulo b harus sama dengan a - b * (a div b), dan jika bahasa tidak menyediakan itu, Anda berada dalam kekacauan matematika yang mengerikan. Ekspresi itu a - b * (a div b) sebenarnya berapa banyak implementasi menghitung modulo b.

Ada beberapa kemungkinan alasan. Yang pertama adalah Anda menginginkan kecepatan maksimum, sehingga div b didefinisikan sebagai apa pun yang digunakan prosesor akan menyediakan. Jika prosesor Anda memiliki instruksi "div", maka div b adalah apa pun yang dilakukan oleh instruksi div (selama itu adalah sesuatu yang tidak sepenuhnya gila).

Yang kedua adalah Anda menginginkan beberapa perilaku matematika tertentu. Pertama-tama mari kita asumsikan b> 0. Cukup masuk akal jika Anda ingin hasil dari div b dibulatkan menjadi nol. Jadi 4 div 5 = 0, 9 div 5 = 1, -4 div 5 = -0 = 0, -9 div 5 = -1. Ini memberi Anda (-a) div b = - (a div b) dan (-a) modulo b = - (a modulo b).

Ini cukup masuk akal tetapi tidak sempurna; misalnya (a + b) div b = (a div b) + 1 tidak berlaku, katakanlah jika a = -1. Dengan b tetap> 0, biasanya ada (b) nilai yang mungkin untuk sedemikian sehingga div b memberikan hasil yang sama, kecuali ada 2b - 1 nilai a dari -b + 1 ke b-1 di mana div b sama dengan 0 Ini juga berarti bahwa modulo b akan negatif jika a negatif. Kami ingin agar modulo b selalu berupa angka dalam rentang dari 0 hingga b-1.

Di sisi lain, itu juga cukup masuk akal untuk meminta bahwa ketika Anda pergi melalui nilai berturut-turut dari a, modulo b harus melalui nilai-nilai dari 0 ke b-1 kemudian mulai dengan 0 lagi. Dan untuk meminta (a + b) div b harus (a div b) + 1. Untuk mencapai itu, Anda ingin hasil dari div b dibulatkan ke arah-infinity, jadi -1 div b = -1. Sekali lagi, ada kerugiannya. (-a) div b = - (a div b) tidak berlaku. Membagi berulang kali dengan dua atau angka apa pun b> 1 pada akhirnya tidak akan memberi Anda hasil 0.

Karena ada konflik, bahasa harus memutuskan set keunggulan mana yang lebih penting bagi mereka dan memutuskan sesuai.

Untuk b negatif, sebagian besar orang tidak bisa memahami apa yang seharusnya div dan modulo b di tempat, jadi cara sederhana adalah mendefinisikan bahwa div b = (-a) div (-b) dan a modulo b = (-a) modulo (-b) jika b <0, atau apa pun hasil alami dari menggunakan kode untuk positif b.

gnasher729
sumber