Donald Knuth adalah seorang ilmuwan komputer yang sangat peduli dengan keakuratan buku yang dia sarankan satu dolar hex ($2,56, 0x$1,00) untuk setiap "kesalahan" yang ditemukan, dengan kesalahan didefinisikan sebagai segala sesuatu yang "salah secara teknis, historis, tipografi, atau politik". Saya sangat ingin mendapatkan cek dari Knuth, jadi saya memutuskan untuk mencari kesalahan dalam magnum opusnya "Seni Pemrograman" (TAOCP). Kami berhasil menemukan tiga. Sesuai dengan kata-katanya, Knut mengirimkan cek 0x$3,00.

Seperti yang Anda lihat, ini bukanlah cek yang sebenarnya. Knuth biasa mengirimkan cek sebenarnya, tetapi berhenti pada tahun 2008 karena penipuan yang merajalela. Dia sekarang mengirimkan "sertifikat deposito pribadi" ke Bank San Serriff (Bos). Dia bilang dia bersedia mengirim uang sungguhan jika diperlukan, tapi sepertinya itu terlalu merepotkan.

Saya menemukan dua kesalahan ketik dan satu kesalahan historis. Saya akan mencantumkannya dalam urutan mengurangi hal-hal sepele.

Salah ketik #1

Kesalahan ketik pertama ada di halaman 392 volume ketiga “Penyortiran dan Pencarian”, baris kedelapan dari bawah: “Setelah pencarian gagal, terkadang (terkadang) diinginkan untuk memasukkan catatan baru ke dalam tabel yang berisi K; metode yang melakukan ini disebut algoritma pencarian dan penyisipan. Kesalahannya adalah sebaliknya beberapa waktu harus kadang-kadang.

Tentu saja kesalahan seperti itu tidak mengherankan. Pasti ada beberapa kesalahan ketik dalam artikel ini saja (tidak ada imbalan jika menemukannya). Yang benar-benar mengejutkan adalah hal ini luput dari perhatian begitu lama. Halaman 392 tidak terkubur jauh di dalam bagian matematika, melainkan halaman pertama Bab XNUMX "Cari"! Mungkin salah satu bagian buku yang paling banyak dibaca. Secara teori, seharusnya ada kesalahan ketik paling sedikit, tapi tidak.

Ngomong-ngomong, jika Anda pernah berpikir untuk membaca TAOCP, cobalah. Banyak yang akan mengatakan demikian direktori, tidak dimaksudkan untuk dibaca langsung, tetapi ini tidak benar. Penulis mempunyai sudut pandang yang jelas dan gaya yang khas. Satu-satunya hal yang menghambat keterbacaan adalah kompleksitas matematika. Namun, ada solusi sederhana: bacalah sampai Anda memahami matematika yang tidak Anda pahami, lewati saja, dan lanjutkan ke bagian berikutnya yang dapat Anda pahami. Membaca dengan cara ini, saya melewatkan setidaknya 80% isi bukunya, tetapi 20% lainnya bagus!

Dikatakan juga bahwa TAOCP tidak relevan, sudah usang atau tidak berlaku untuk "pemrograman nyata". Hal ini juga tidak benar. Misalnya, bagian pertama setelah pendahuluan membahas tentang menemukan elemen dalam array yang tidak diurutkan. Algoritma paling sederhana sudah tidak asing lagi bagi semua programmer. Mulai penunjuk di awal array, lalu lakukan hal berikut dalam satu lingkaran:

1. Periksa apakah elemen saat ini adalah yang diinginkan. Jika demikian, kami mengembalikannya; jika tidak
2. Periksa apakah penunjuk berada di luar batas array. Jika demikian, kembalikan kesalahan; jika tidak
3. Perbesar dan lanjutkan.

Sekarang pertimbangkan: rata-rata berapa banyak pemeriksaan batas yang dibutuhkan algoritma ini? Dalam kasus terburuk, ketika array tidak berisi elemen, setiap elemen dalam daftar akan memerlukan satu pemeriksaan, dan rata-rata akan menjadi seperti . Algoritme pencarian yang lebih cerdas dapat dilakukan hanya dengan satu pemeriksaan batas. Lampirkan elemen yang diinginkan ke akhir array, lalu mulai penunjuk di awal array dan lakukan hal berikut dalam satu lingkaran:

1. Periksa apakah elemen saat ini adalah yang diinginkan. Jika demikian, kami mengembalikan respons jika penunjuk berada di dalam array, atau kesalahan jika tidak. Jika tidak
2. Perbesar dan lanjutkan.

Dengan satu atau lain cara, elemen tersebut dijamin akan ditemukan, dan pemeriksaan batas hanya dilakukan satu kali jika hal ini terjadi. Ini adalah ide yang mendalam, namun cukup sederhana bahkan untuk programmer pemula. Saya mungkin tidak dapat menjelaskan relevansi pekerjaan ini kepada orang lain, namun saya dapat langsung menerapkan kebijaksanaan ini pada kode pribadi dan profesional. Buku TAOCP penuh dengan permata seperti itu (agar adil, banyak juga hal aneh di dalamnya, seperti semacam gelembung).

"Cari, cari
Begitu lama
Cari, cari
aku hanya ingin menari"
— Luther Vandross, "Pencarian" (1980)

Salah ketik #2

Kesalahan ketik kedua ada di Volume 4A, Algoritma Kombinatorial, Bagian 1. Halaman 60 menjelaskan masalah yang melibatkan penjadwalan komedian untuk tampil di berbagai kasino. Beberapa komedian kehidupan nyata dikutip sebagai contoh, termasuk Lily Tomlin, Weird Al Yankovic, dan Robin Williams, yang masih hidup saat buku tersebut diterbitkan. Knuth selalu mencantumkan nama lengkap dalam indeks, sehingga Williams terdaftar di halaman 882 sebagai "Williams, Robin McLorim." Tapi nama tengahnya diakhiri dengan “n” dan bukan “m”, yaitu McLaurin.

McLaurin adalah nama gadis ibunya. Dia adalah cicit dari Anselmus Joseph McLaurin, Gubernur Mississippi ke-34. Pemerintahannya, rupanya, tidak dikenang karena hal yang baik. Dari buku Mississippi: Sejarah:

“Peristiwa terpenting selama pemerintahan McLaurin adalah deklarasi perang Amerika Serikat terhadap Spanyol pada musim semi tahun 1898... Sayangnya, perang tersebut mungkin telah memberikan kesempatan kepada beberapa pejabat pemerintah untuk melakukan suap. McLaurin dituduh melakukan berbagai praktik yang meragukan, termasuk nepotisme dan penggunaan kewenangan pengampunan yang berlebihan. Selama gerakan pertarakan, para kritikus menuduh gubernur sebagai seorang pemabuk, dan dia mengakuinya secara terbuka.”

Kesalahan sejarah

Mempertimbangkan algoritma perkalian tradisional dari kurikulum sekolah. Berapa banyak perkalian satu digit yang diperlukan? Misalkan Anda mengalikan -nomor digit pada -sedikit . Kalikan dulu angka pertama untuk setiap digit satu per satu. Kemudian kalikan angka kedua untuk setiap digit satu per satu dan seterusnya sampai Anda menyelesaikan semua angka . Oleh karena itu diperlukan perkalian tradisional perkalian primitif. Khususnya, mengalikan dua angka dengan peringkat yang diperlukan perkalian satu digit.

Ini buruk, tetapi proses dapat dioptimalkan menggunakan metode yang dikembangkan oleh matematikawan Soviet Anatoly Alekseevich Karatsuba. Mari kita berpura-pura seperti itu и  - angka desimal dua digit; yaitu, ada angka , , , seperti yang и (menggeneralisasi algoritma ini ke angka yang lebih besar memerlukan beberapa manipulasi; meskipun tidak terlalu sulit, agar tidak membuat kesalahan dalam detailnya, lebih baik saya tetap menggunakan contoh sederhana). Kemudian , , . Mengalikan binomial menghasilkan . Saat ini kami masih punya perkalian satu digit: , , , . Sekarang mari kita menambah dan mengurangi . Setelah beberapa kali penataan ulang, yang akan saya tinggalkan sebagai latihan untuk pembaca, ternyata  - hanya tiga perkalian satu digit! (Ada beberapa koefisien konstan, tetapi hanya dapat dihitung dengan menjumlahkan dan menggeser angkanya).

Jangan minta bukti, tapi Algoritma Karatsuba (digeneralisasi secara rekursif dari contoh di atas) meningkatkan metode perkalian tradisional dengan operasi sebelumnya . Harap dicatat bahwa ini adalah peningkatan nyata pada algoritme, bukan pengoptimalan untuk perhitungan mental. Memang benar, algoritme ini tidak cocok untuk aritmatika mental, karena memerlukan biaya overhead yang besar untuk operasi rekursif. Selain itu, efeknya tidak akan terwujud sepenuhnya hingga jumlahnya menjadi cukup besar (untungnya, algoritma Karatsuba telah digantikan oleh metode yang lebih cepat: pada bulan Maret 2019, sebuah algoritma diterbitkan yang hanya membutuhkan n mencatat n perkalian; percepatan hanya berlaku untuk jumlah yang sangat besar).

Algoritma ini dijelaskan pada halaman 295 Volume XNUMX, Algoritma Semi-Numerik. Di sana Knuth menulis: “Sangat mengherankan bahwa ide ini hanya ditemukan di 1962 tahun,” ketika sebuah artikel yang menjelaskan algoritma Karatsuba diterbitkan. Tetapi! Pada tahun 1995, Karatsuba menerbitkan makalah “Computational Complexity”, yang menyatakan beberapa hal: 1) sekitar tahun 1956, Kolmogorov mengemukakan bahwa perkalian tidak dapat dilakukan dalam waktu kurang dari Langkah; 2) di 1960 tahun Karatsuba menghadiri seminar di mana Kolmogorov mempresentasikan hipotesisnya n². 3) “Tepat dalam satu minggu,” Karatsuba mengembangkan algoritma “membagi dan menaklukkan”; 4) pada tahun 1962 Kolmogorov menulis dan menerbitkan sebuah artikel atas nama Karatsuba dengan deskripsi algoritma. “Saya baru mengetahui artikel ini setelah diterbitkan ulang.”

Jadi kesalahannya adalah itu bukannya 1962 harus ditentukan 1960 tahun. Itu saja.

analisis

Menemukan kesalahan tidak memerlukan keahlian khusus.

1. Kesalahan pertama sesederhana mungkin dan berada di tempat yang relatif terlihat (awal bab). Orang bodoh mana pun pasti akan menemukannya; Ternyata akulah orang bodoh itu.
2. Menemukan kesalahan ketik kedua membutuhkan keberuntungan dan ketekunan, tetapi bukan keterampilan. Indeks untuk "Williams" ada di halaman kedua dari belakang volume ini, bagian yang cukup menonjol dari buku ini. Saya baru saja membolak-balik indeks (kedengarannya tidak menyedihkan, karena ada telur Paskah yang disembunyikan di indeks Knuth. Misalnya, ada entri dalam bahasa Arab dan Ibrani, keduanya menunjuk ke halaman 66. Tapi halaman itu tidak menyebutkan salah satu bahasa; sebaliknya ini mengacu pada “bahasa yang dibaca dari kanan ke kiri”). Dan nama kedua menarik perhatian saya. Karena saya biasanya membaca Wikipedia, saya memeriksa Robin Williams dan melihat ada perbedaan.
3. Saya berharap saya dapat mengatakan bahwa saya melakukan penelitian serius untuk menemukan kesalahan sejarah, namun sebenarnya saya hanya melihat Halaman Wikipedia tentang algoritma Karatsuba. Baris pertama berbunyi: “Algoritma Karatsuba adalah algoritma perkalian yang cepat. Ditemukan oleh Anatoly Karatsuba pada tahun 1960 dan diterbitkan pada tahun 1962." Setelah itu yang tersisa hanyalah menambahkan dua dan dua.

Kedepannya saya ingin menemukan bug yang lebih signifikan, terutama pada kode Knuth. Saya juga ingin menemukan bug di volume pertama Algoritma Dasar. Mungkin saya akan menemukannya, tapi entah kenapa perpustakaan setempat hanya memiliki volume 2, 3 dan 4A.

Fakta keuangan:

• Secara total, kontribusi saya pada TAOCP hanya terdiri dari tiga karakter: satu tambahan s, penggantian m pada n и 2 pada 0. Dengan harga $2,56, ini adalah beberapa simbol yang cukup menguntungkan; Jika Anda dibayar uang sebanyak itu, sebuah artikel berisi 1000 kata (rata-rata empat karakter) akan memberi Anda sepuluh ribu.
• Dengan tiga dolar heksadesimal, saya, bersama 29 warga lainnya, berada di peringkat ke-69 dalam daftar deposan terkaya di San Serriff Bank (per 1 Mei 2019).

Diskusi lain tentang cek dari Knuth

• Cara mendapatkan cek dari Knuth

  Rekomendasi umum untuk menemukan kesalahan dalam buku Knuth. Kebanyakan masalah ini berkaitan dengan kesalahan teknis, yang tidak saya alami. Ada satu saran yang saya anggap serius:

  Sebaiknya tunggu hingga Anda mengumpulkan serangkaian kesalahan untuk dikirimkan. Dengan menggabungkan beberapa kesalahan nyata tetapi tidak terlalu berharga, Anda meningkatkan kemungkinan bahwa salah satu kesalahan tersebut benar-benar dianggap sebagai kesalahan atau nasihat. Jika Anda mengirimkan kesalahan satu per satu, setiap kesalahan mungkin ditolak.

  Saya tidak ingin hanya mengirimkan kesalahan ketik yang tidak masuk akal, tetapi menuruti saran tersebut dan mengirimkan surat hanya ketika saya menemukan kesalahan sejarah yang tampaknya cukup serius.

• Cek Ashutosh Mehra

  Ashutosh Mehra adalah investor terkaya ketiga di San Serriff dengan kekayaan bersih 0x$207.f0 di BoSS.

• Periksa beberapa bug non-fungsional dalam kode TeX asli
• Miscellaneous: #1 #2 #3 #4 #5 #6

Sumber: www.habr.com