Donald Knuth adalah seorang ilmuwan komputer yang sangat peduli tentang kebenaran buku-bukunya sehingga ia menawarkan satu dolar hex ($ 2,56, 0x $ 1,00) untuk setiap "kesalahan" yang ditemukan, di mana segala sesuatu yang "secara teknis, historis, tipografi, dianggap sebagai kesalahan." atau salah secara politis. " Saya benar-benar ingin mendapatkan cek dari Knut, jadi saya memutuskan untuk mencari kesalahan dalam karyanya yang luar biasa "The Art of Programming" (TAOCP). Saya berhasil menemukan tiga. Sesuai dengan kata itu, Knut mengirim cek untuk 0x $ 3,00 .



Seperti yang Anda lihat, ini bukan cek nyata. Knut dulu mengirim cek nyata, tetapi berhenti pada 2008 karena penipuan yang merajalela . Sekarang dia mengirim "sertifikat setoran pribadi" di Bank of San Serriff (BoSS). Dia bilang dia siap untuk mengirim uang nyata jika perlu, tetapi tampaknya terlalu merepotkan.

Saya menemukan dua kesalahan ketik dan satu kesalahan sejarah. Saya akan daftar mereka dalam mengurangi urutan hal-hal sepele.

Typo nomor 1

Kesalahan ketik pertama ada di halaman 392 dari volume ketiga "Sorting and Searching", baris kedelapan dari bawah: "Setelah pencarian gagal, kadang-kadang (kadang-kadang) disarankan untuk memasukkan catatan baru di tabel yang berisi K ; metode yang melakukan ini disebut algoritma pencarian dan masukkan. Kesalahannya adalah bahwa kadang - kadang bukan kadang - kadang .

Tentu saja, kesalahan seperti itu tidak mengejutkan. Hanya di artikel ini pasti ada beberapa kesalahan ketik (tidak ada hadiah untuk menemukannya). Apa yang benar-benar mengejutkan adalah bahwa hal itu tidak diperhatikan begitu lama. Halaman 392 tidak terkubur jauh di dalam bagian dengan matematika, ini adalah halaman pertama dari bab keenam dari "Pencarian"! Mungkin salah satu bagian buku yang paling banyak dibaca. Secara teori, seharusnya ada kesalahan ketik paling sedikit, tetapi tidak.

Omong-omong, jika Anda pernah berpikir untuk membaca TAOCP, cobalah. Banyak yang akan mengatakan bahwa ini adalah panduan yang tidak dimaksudkan untuk membaca langsung, tetapi ini tidak benar. Penulis memiliki sudut pandang yang jelas dan gaya yang khas. Satu-satunya hal yang mencegah keterbacaan adalah kompleksitas matematika. Namun, ada solusi sederhana: baca sampai Anda mendapatkan matematika yang tidak Anda mengerti, lewati dan buka bagian selanjutnya yang bisa Anda pahami. Membaca dengan cara ini, saya kehilangan setidaknya 80% dari buku ini, tetapi 20% sisanya bagus!

Mereka juga mengatakan bahwa TAOCP tidak relevan , ketinggalan jaman, atau tidak berlaku untuk "pemrograman nyata." Ini juga tidak benar. Misalnya, di bagian pertama setelah pendahuluan, pencarian elemen dalam array yang tidak disortir dipertimbangkan. Algoritma paling sederhana sudah tidak asing lagi untuk semua programmer. Jalankan pointer di awal array, lalu lakukan hal berikut dalam satu lingkaran:

1. Periksa apakah item saat ini diinginkan. Jika demikian, kembalikan; jika tidak
   
2. Periksa apakah pointer berada di luar array. Jika demikian, kembalikan kesalahan; jika tidak
   
3. Tambah penunjuk dan lanjutkan.

Sekarang pertimbangkan: berapa banyak pemeriksaan perbatasan yang dibutuhkan algoritma ini, rata-rata? Dalam kasus terburuk, ketika array tidak mengandung elemen, untuk setiap elemen dalam daftar satu pemeriksaan diperlukan, dan rata-rata akan menjadi seperti $$$N / 2$. Algoritme pencarian yang lebih cerdas dapat dilakukan hanya dengan satu pemeriksaan perbatasan. Pasang elemen yang diinginkan ke ujung array, kemudian jalankan pointer di awal array dan ikuti langkah-langkah ini dalam satu lingkaran:

1. Periksa apakah item saat ini diinginkan. Jika demikian, kami mengembalikan jawabannya jika pointer ada di dalam array, atau kesalahan jika tidak. Jika tidak
   
2. Tambah penunjuk dan lanjutkan.

Dengan satu atau lain cara, elemen dijamin akan ditemukan, dan pemeriksaan perbatasan dilakukan hanya sekali, ketika ini terjadi. Ini adalah ide yang mendalam, tetapi cukup sederhana bahkan untuk programmer pemula. Mungkin, saya tidak dapat berbicara tentang relevansi pekerjaan untuk orang lain, tetapi saya segera dapat menerapkan kebijaksanaan ini dalam kode pribadi dan profesional. Buku TAOCP penuh dengan mutiara seperti itu (sebenarnya, ada banyak hal aneh, seperti bubble sorting ).

"Cari, cari
Sangat lama
Cari, cari
Saya hanya ingin menari. "
- Luther Wandross, Search (1980)

Mengetik nomor 2

Kesalahan ketik kedua ada di Volume 4A, Algoritma Kombinatorial, Bagian 1. Di halaman 60, kami menggambarkan tugas merencanakan pertunjukan komedian di berbagai kasino. Beberapa pelawak nyata dikutip sebagai contoh, termasuk Lily Tomlin, Strange Al Jankovic dan Robin Williams, yang masih hidup ketika buku itu keluar. Whip selalu memberikan nama lengkap dalam indeks , sehingga Williams disebut pada halaman 882 sebagai "Williams, Robin McLorim." Tetapi nama tengahnya berakhir dengan "n", dan bukan dengan "m", yaitu, McLoreen.

McLorin adalah nama gadis ibunya. Dia adalah cicit dari Anselmus Joseph McLorin, Gubernur Mississippi ke-34. Pemerintahannya, tampaknya, tidak diingat oleh hal-hal baik. Dari buku Mississippi: History :

"Peristiwa paling penting selama pemerintahan McLorin adalah Amerika Serikat menyatakan perang Spanyol pada musim semi 1898 ... Sayangnya, perang itu memungkinkan beberapa pejabat pemerintah melakukan praktik suap. McLorin telah dituduh melakukan berbagai praktik yang meragukan, termasuk nepotisme dan penggunaan kekuatan pengampunan yang berlebihan. Di era ketenangan, para kritikus menuduh gubernur mabuk, yang ia akui secara terbuka. ”

Kesalahan sejarah

Pertimbangkan algoritma multiplikasi tradisional dari kurikulum sekolah. Berapa yang dibutuhkan operasi multiplikasi satu-bit? Misalkan Anda bertambah banyak $$$m$nomor-bit $$$x$pada $$$n$-bit $$$y$. Pertama, gandakan digit pertama $$$x$untuk setiap digit $$$y$bergiliran. Kemudian gandakan digit kedua $$$x$untuk setiap digit $$$y$bergiliran dan seterusnya sampai Anda melihat semua angka $$$x$. Jadi, perkalian tradisional membutuhkan $$$mn$perkalian primitif. Secara khusus, perkalian dua angka dengan $$$n$membutuhkan debit $$$n ^ 2$multiplikasi bit tunggal.

Ini buruk, tetapi Anda dapat mengoptimalkan proses menggunakan metode yang dikembangkan oleh ahli matematika Soviet, Anatoly Alekseevich Karatsuba. Asumsikan itu $$$x$dan $$$y$- angka desimal dua digit; yaitu ada angka $$$a$, $$$b$, $$$c$, $$$d$sedemikian rupa $$$x = (ab) _ {10}$dan $$$y = (cd) _ {10}$(generalisasi dari algoritma ini ke sejumlah besar membutuhkan manipulasi tertentu; walaupun ini tidak terlalu sulit, tetapi agar tidak salah dalam detailnya, saya lebih baik tetap berpegang pada contoh sederhana). Lalu $$$x = 10a + b$, $$$y = 10c + d$, $$$xy = (10a + b) (10c + d)$. Multiplikasi binomial memberi $$$xy = 100ac + 10ad + 10bc + bd$. Saat ini, kami masih $$$n ^ 2 = 4$perkalian bit tunggal: $$$ac$, $$$ad$, $$$bc$, $$$bd$. Sekarang tambahkan dan kurangi $$$10ac + 10bc$. Setelah beberapa permutasi, yang akan saya tinggalkan sebagai latihan untuk pembaca, ternyata $$$xy = 110ac + 11bd + 10 (a - b) (d - c)$- hanya tiga perkalian satu digit! (Ada beberapa koefisien konstan, tetapi mereka hanya dapat dihitung dengan menambahkan dan menggeser digit).

Jangan meminta bukti, tetapi algoritma Karatsuba (digeneralisasi secara rekursif dari contoh di atas) meningkatkan metode perkalian tradisional dengan $$$O (n ^ 2)$operasi sebelumnya $$$O (n ^ {(lg 3)})$. Harap dicatat bahwa ini adalah peningkatan nyata dalam algoritma, bukan optimasi untuk perhitungan mental. Memang, algoritma ini tidak cocok untuk menghitung dalam pikiran, karena membutuhkan overhead yang besar untuk operasi rekursif. Selain itu, efeknya tidak akan sepenuhnya terlihat sampai jumlahnya menjadi cukup besar (untungnya, alih-alih algoritma Karatsuba, bahkan metode yang lebih cepat datang: pada bulan Maret 2019, sebuah algoritma diterbitkan yang hanya membutuhkan n penggandaan n penggandaan; akselerasi hanya berlaku untuk besar yang tak terbayangkan angka).

Algoritma ini dijelaskan pada halaman 295 volume kedua, Algoritma Berasal. Di sana Knuth menulis: “Sangat aneh bahwa ide ini ditemukan hanya pada tahun 1962 ” ketika sebuah artikel diterbitkan yang menggambarkan algoritma Karatsuba. Tapi! Pada tahun 1995, Karatsuba menerbitkan sebuah artikel, "Complexity of Computing," yang mengatakan beberapa hal: 1) sekitar tahun 1956, Kolmogorov menyarankan bahwa multiplikasi tidak dapat dilakukan dalam waktu kurang dari $$$O (n ^ 2)$langkah-langkah; 2) pada tahun 1960 , Karatsuba menghadiri seminar di mana Kolmogorov mempresentasikan hipotesisnya n². 3) “Tepat dalam seminggu” Karatsuba mengembangkan algoritma “divide and conquer”; 4) pada tahun 1962, Kolmogorov menulis dan menerbitkan artikel atas nama Karatsuba dengan deskripsi algoritme. "Saya baru tahu tentang artikel ini setelah dicetak ulang."

Dengan demikian, kesalahannya adalah bahwa 1960 harus diindikasikan bukan 1962 . Itu saja.

Analisis

Pencarian kesalahan tidak membutuhkan banyak keterampilan.

1. Kesalahan pertama adalah yang biasa terjadi, dan berada di tempat yang relatif menonjol (awal bab ini). Setiap orang idiot akan menemukannya; Saya ternyata idiot itu.
   
2. Menemukan kesalahan ketik yang kedua membutuhkan keberuntungan dan ketekunan, tetapi bukan keterampilan. Indeks untuk "Williams" ada di halaman kedua dari belakang volume, bagian yang agak menonjol dari buku ini. Saya baru saja membalik-balik indeks (sepertinya tidak begitu menyedihkan karena telur Paskah tersembunyi di indeks Knuth. Misalnya, ada entri dalam bahasa Arab dan Ibrani, dan keduanya menunjuk ke halaman 66. Tetapi halaman ini tidak menyebutkan keduanya. bahasa; alih-alih, ini merujuk pada "bahasa yang dibaca dari kanan ke kiri"). Dan perhatian saya tertarik dengan nama tengahnya. Karena saya biasanya membaca Wikipedia, saya memeriksa Robin Williams dan melihat ada perbedaan.
   
3. Saya ingin mengatakan bahwa saya melakukan banyak penelitian untuk menemukan kesalahan historis, tetapi sebenarnya hanya melihat halaman Wikipedia tentang algoritma Karatsuba . Baris pertama mengatakan: “Algoritma Karatsuba adalah algoritma untuk perkalian cepat. Ditemukan oleh Anatoly Karatsuba pada tahun 1960 dan diterbitkan pada tahun 1962. " Setelah itu, hanya tersisa dua kali lipat dua.

Di masa depan, saya ingin menemukan kesalahan yang lebih signifikan, terutama dalam kode Knuth. Saya juga ingin menemukan bug di volume pertama, Fundamental Algorithms. Mungkin saya akan menemukannya, tetapi untuk beberapa alasan hanya ada volume 2, 3 dan 4A di perpustakaan setempat.

Fakta keuangan:

• Secara total, kontribusi saya ke TAOCP hanya terdiri dari tiga karakter: satu menambahkan s , mengganti m dengan n dan 2 dengan 0 . Harga $ 2,56, ini adalah simbol yang cukup menguntungkan; jika Anda dibayar uang sebanyak itu, maka artikel 1000 kata (rata-rata, masing-masing empat karakter) akan memberi Anda sepuluh buah.
  
• Dengan tiga dolar heksadesimal, saya, bersama dengan 29 warga lainnya, berbagi tempat ke-69 dalam daftar deposan terkaya di Bank of San Serriff (per 1 Mei 2019).

Diskusi lain tentang cek Knut

• Cara mendapatkan cek dari Knut
  
  Panduan umum untuk menemukan bug di buku-buku Knut. Sebagian besar kesalahan teknis yang tidak saya miliki. Ada satu saran yang saya anggap serius:
  
  

  Lebih baik menunggu sampai Anda mengumpulkan satu set kesalahan untuk dikirim. Dengan menggabungkan beberapa kesalahan nyata, tetapi tidak terlalu berharga, Anda akan meningkatkan kemungkinan salah satu dari mereka akan dianggap sebagai kesalahan atau saran. Jika Anda mengirim kesalahan satu per satu, setiap individu dapat ditolak.

  
  Saya tidak ingin mengirim kesalahan ketik yang tidak masuk akal, tetapi saya menuruti saran itu dan mengirim surat hanya ketika saya menemukan kesalahan historis yang tampak cukup serius.
  
• Cek Ashutosh Mehra
  
  Ashutosh Mehra adalah kontributor terkaya ketiga ke San Serriff dengan kekayaan kekalahan 0x $ 207, f0 di BoSS.
  
• Periksa beberapa kesalahan non-fungsional dalam kode TeX nyata
  
• Lain-lain: # 1 # 2 # 3 # 4 # 5 # 6