Bersiaplah, artikel yang sangat luar biasa menunggu Anda, yang mungkin menghemat wawancara atau menghemat beberapa jam sambil menangkap bug dalam produksi!
Saya secara aktif bekerja pada musim kedua
The Impostor's Guide dan saya menulis tentang sandi RSA untuk SSH, yang jelas merupakan bagian kode yang paling banyak diunduh dalam sejarah TI.
Saya ingin sepenuhnya memahami cerita ini. Siapa yang menemukan kode ini, cara kerjanya, mengapa ia bekerja dan
apakah itu akan berhasil di masa depan . Sekarang saya telah menggali
kisah yang sangat menarik . Saya bukan seorang cryptomaniac dan saya melihat orang lain benar-benar mengisap ke daerah ini. Tetapi saya juga tertarik dengan hal ini, karena ada mink kecil di mana-mana, dan seperti burung gagak, saya
tertarik pada hal -
hal kecil yang
mengkilap di mink yang dalam . Saya juga sangat pandai dalam metafora.
Dalam hal apapun: minggu lalu saya belajar sesuatu yang aneh dan ingin berbagi: ternyata
mod dan sisanya dari divisi itu tidak sama . Sangat lucu bahwa beberapa pembaca melompat dari tempat duduk mereka dan meneriaki kata-kata ini: "Tapi itulah yang selalu saya coba katakan kepada Anda dan semua orang!"
Panggil orang-orang dari sekte "mod bukan sisanya"! Ini untukmu.
Apa itu mod?
Saya harus mempelajari ini, dan juga terakhir kali topik seperti itu muncul. Ini adalah salah satu hal yang Anda
tahu tetapi tidak ingat. Ketika Anda menggunakan mod, kemudian bagi satu nomor dengan yang lain dan ambil sisanya. Jadi:
5 mod 2 akan menjadi 1, karena 5/2 = 2 dengan sisa 1.
Istilah mod berarti operasi
modulo , dengan modul 2 dalam hal ini. Sebagian besar bahasa pemrograman menggunakan
% untuk menunjukkan operasi seperti itu:
5 % 2 = 1 .
Di situlah kita masuk ke area abu-abu yang aneh.
Matematika dial
Saya ingat bagaimana saya mengajar ini di sekolah, dan kemudian lupa. Ada jenis matematika yang disebut "modular aritmatika" yang berhubungan dengan struktur siklik. Cara termudah untuk membayangkan ini adalah dial dengan siklus 12. Untuk seorang matematikawan, dial adalah
mod 12 . Jika Anda ingin memahami apakah mungkin untuk membagi secara merata 253 jam menjadi beberapa hari, maka Anda dapat menerapkan operasi
253 mod 24 ,
hasilnya adalah 13 , jadi jawabannya tidak! Kami dapat menjawab ya hanya jika hasilnya 0.
Pertanyaan lain yang dapat Anda tanyakan adalah: "Jika saya berangkat pukul 6 sore, jam berapa akan tiba pada 16 jam mendatang?" Ini akan menjadi
6 + 16 mod 12 , mis. 10.
Cryptographers menyukai
mod , karena ketika digunakan dengan angka yang sangat besar, Anda dapat membuat sesuatu yang dikenal sebagai "fungsi satu arah." Ini adalah fungsi khusus yang membuatnya mudah untuk menghitung sesuatu dalam satu arah, tetapi tidak sebaliknya.
Jika saya memberi tahu Anda bahwa 9 adalah hasil kuadrat, Anda dapat dengan mudah menentukan apa inputnya. 3. Sebelum Anda melihat keseluruhan proses dari awal hingga selesai. Jika saya mengatakan bahwa 9 adalah hasil dari
mod 29 , maka akan lebih sulit untuk memahami apa inputnya.
Cryptographers menyukai ide ini karena mereka dapat menggunakan pembagian sisa dengan bilangan prima raksasa untuk menghasilkan kunci kriptografi. Ini adalah kisah yang sama sekali berbeda: jika Anda ingin membacanya, Anda dapat membeli buku atau, lebih baik lagi,
mendukung upaya saya untuk menulisnya .
Namun, kami tidak akan menyimpang dari topik.
Sisa dan matematika dial
Sekarang mari kita langsung ke intinya: modulo dan sisanya sederhana sama ketika angkanya positif, tetapi berbeda dalam hal angka negatif.
Pertimbangkan tugas berikut:
const x = 19 % 12; console.log(x);
Berapa nilai
x ? Bagilah angkanya dan dapatkan 7 sebagai sisa dari 12. Ini adalah jawaban yang benar. Bagaimana dengan ini:
const y = 19 % -12; console.log(y);
Dengan menggunakan matematika biasa, kita dapat mengalikan -12 dengan -1, yang memberi 12, dan kita masih memiliki 7, jadi jawaban kita lagi 7.
JavaScript setuju dengan ini:
C # setuju juga:
Google setuju dengan pernyataan pertama, tetapi tidak setuju dengan pernyataan kedua:
Ruby setuju dengan Google:
Atas nama Dijkstra, apa yang terjadi di sini?Beberapa jam yang lalu
Untuk menjawab pertanyaan, Anda perlu memahami perbedaan antara
sisanya dan
modulo .
Pemrogram menggabungkan operasi ini , tetapi tidak boleh melakukan ini, karena mereka memberikan hasil yang sama hanya jika pembagi (dalam kasus kami 12) adalah positif. Anda dapat dengan mudah mengirim bug ke produksi jika pembagi negatif.
Tetapi mengapa ada perbedaan? Pertimbangkan pembagi positif
19 mod 12 pada jam:
Hasil akhir 7. Kami tahu ini dan kami bisa membuktikan secara matematis. Tapi bagaimana dengan
19 mod -12 ?
Di sini Anda perlu menggunakan jam tangan lainnya :
Modul ini -12, dan kita tidak bisa mengabaikan atau mengubahnya dengan mengalikan dengan -1, karena aritmatika modular tidak berfungsi seperti itu. Satu-satunya cara untuk menghitung hasil dengan benar adalah dengan mengatur ulang tanda pada jam sehingga kita bergerak dari -12 atau memutar jam berlawanan arah jarum jam, yang memberikan hasil yang sama.
Mengapa tidak memulai tag dengan -1, pindah ke -2, dll.?
Karena dalam kasus ini, kita akan bergerak mundur dan terus-menerus mengurangi hasilnya hingga mencapai -12, dan pada saat ini kita akan membuat lompatan +12, dan modulo tidak berfungsi seperti itu.
Ini adalah hal yang terkenal.
Sebelum Anda memanggil saya gila dan mulai googling topik:
ini adalah fakta yang terkenal . Bahkan, MDN (Mozilla Developer Network) bahkan melangkah lebih jauh dengan memanggil
% operasi yang tersisa, bukan modulo:
Operator sisanya mengembalikan sisa pembagian satu operan dengan operan lainnya. Dia selalu menerima tanda dividen .
Inilah yang dikatakan Eric Lippert, salah satu dewa C #
tentang modulo dalam C # :
Namun, ini sama sekali bukan apa yang sebenarnya dilakukan oleh operator% dalam C #. % Operator bukan operator modulus kanonik, ini adalah operator sisanya.
Bagaimana dengan bahasa Anda?
Jadi apa
Saya bisa mengerti jika Anda sudah membaca sejauh ini, dan sekarang menggaruk-garuk kepala Anda dan bertanya-tanya apakah itu layak dikhawatirkan. Saya pikir biayanya karena dua alasan:
- Saya bisa membayangkan bagaimana pertanyaan ini akan mengejutkan saya dalam sebuah wawancara.
- Saya bisa membayangkan bagaimana yang satu ini masuk ke produksi, dan pengembang akan mencari tahu selama beberapa jam mengapa matematika tidak berfungsi.
Ini juga fakta yang menyenangkan jika teman programmer Anda yang hebat datang.