डोनाल्ड नुथ तो एक संगणक शास्त्रज्ञ आहे जो त्याने सुचवलेल्या पुस्तकांच्या अचूकतेबद्दल खूप काळजी घेतो एक हेक्स डॉलर ($2,56, 0x$1,00) आढळलेल्या कोणत्याही "त्रुटी" साठी, जेथे त्रुटी "तांत्रिक, ऐतिहासिक, टायपोग्राफिक किंवा राजकीयदृष्ट्या चुकीची" अशी कोणतीही गोष्ट म्हणून परिभाषित केली जाते. मला खरोखर नुथकडून चेक मिळवायचा होता, म्हणून मी त्याच्या मॅग्नम ओपसमधील त्रुटी शोधण्याचा निर्णय घेतला "प्रोग्रामिंगची कला" (TAOCP). आम्ही तिघांना शोधण्यात यशस्वी झालो. त्याच्या शब्दावर खरे, नटने चेक पाठवला 0x$3,00.

तुम्ही बघू शकता, ही खरी तपासणी नाही. नुथ वास्तविक धनादेश पाठवत असत, परंतु 2008 मध्ये थांबले सर्रास फसवणूक. तो आता "ठेवीचे वैयक्तिक प्रमाणपत्र" पाठवतो बँक ऑफ सॅन सेरिफ (बॉस). तो म्हणतो की तो आवश्यक असल्यास वास्तविक पैसे पाठवण्यास तयार आहे, परंतु असे दिसते की ते खूप त्रासदायक आहे.

मला दोन टायपोज आणि एक ऐतिहासिक त्रुटी आढळली. क्षुल्लकता कमी करण्याच्या क्रमाने मी त्यांची यादी करेन.

टायपो #1

पहिला टायपो “सॉर्टिंग अँड सर्च” च्या तिसऱ्या खंडाच्या पृष्ठ 392 वर आहे, तळापासून आठवी ओळ: “अयशस्वी शोधानंतर, कधीकधी (कधी कधी) टेबलमध्ये नवीन रेकॉर्ड प्रविष्ट करणे इष्ट असते K; हे करणारी पद्धत शोध आणि घाला अल्गोरिदम म्हणतात. त्याऐवजी चूक आहे कधीतरी असावे कधी कधी.

अर्थात, अशी चूक आश्चर्यकारक नाही. एकट्या या लेखात काही टायपोज असतील (ते शोधण्यासाठी कोणतेही बक्षिसे नाहीत). आश्चर्याची गोष्ट म्हणजे इतके दिवस याकडे कोणाचेच लक्ष गेले नाही. पृष्ठ 392 हे गणित विभागात खोलवर दडलेले नाही, ते आहे अगदी पहिले पान अध्याय XNUMX "शोध"! कदाचित पुस्तकाच्या सर्वाधिक वाचल्या गेलेल्या विभागांपैकी एक. सिद्धांतानुसार, सर्वात कमी टायपोज असावेत, परंतु नाही.

तसे, तुम्ही कधी TAOCP वाचण्याचा विचार केला असेल, तर ते वापरून पहा. असे अनेकजण म्हणतील निर्देशिका, थेट वाचनासाठी हेतू नाही, परंतु हे खरे नाही. लेखकाकडे स्पष्ट दृष्टिकोन आणि एक विशिष्ट शैली आहे. वाचनीयतेमध्ये अडथळा आणणारी एकमेव गोष्ट म्हणजे गणिताची गुंतागुंत. तथापि, एक सोपा उपाय आहे: जोपर्यंत तुम्हाला गणित येत नाही तोपर्यंत वाचा, ते वगळा आणि तुम्हाला समजू शकणार्‍या पुढील विभागात जा. अशा प्रकारे वाचताना, मला किमान 80% पुस्तक चुकते, परंतु इतर 20% छान आहे!

असेही म्हटले आहे की TAOCP असंबद्ध, जुने आहे किंवा अन्यथा "वास्तविक प्रोग्रामिंग" ला लागू होत नाही. हे देखील खरे नाही. उदाहरणार्थ, परिचयानंतरचा पहिला विभाग क्रमबद्ध न केलेल्या अॅरेमध्ये घटक शोधण्याचा विचार करतो. सर्वात सोपा अल्गोरिदम सर्व प्रोग्रामरना परिचित आहे. अॅरेच्या सुरुवातीला पॉइंटर सुरू करा, नंतर लूपमध्ये पुढील गोष्टी करा:

1. वर्तमान घटक इच्छित आहे का ते तपासा. तसे असल्यास, आम्ही ते परत करतो; अन्यथा
2. पॉइंटर अ‍ॅरे सीमेच्या बाहेर आहे का ते तपासा. तसे असल्यास, त्रुटी परत करा; अन्यथा
3. झूम वाढवा आणि सुरू ठेवा.

आता विचार करा: या अल्गोरिदमला सरासरी किती बाउंड चेक आवश्यक आहेत? सर्वात वाईट परिस्थितीत, जेथे अॅरेमध्ये घटक नसतात, सूचीतील प्रत्येक घटकाला एक तपासणी आवश्यक असेल आणि सरासरी ते असे काहीतरी असेल . एक हुशार शोध अल्गोरिदम फक्त एक सीमा तपासणीसह दूर होऊ शकतो. अॅरेच्या शेवटी इच्छित घटक संलग्न करा, नंतर अॅरेच्या सुरूवातीस पॉइंटर सुरू करा आणि लूपमध्ये पुढील गोष्टी करा:

1. वर्तमान घटक इच्छित आहे का ते तपासा. तसे असल्यास, पॉइंटर अ‍ॅरेमध्ये असल्यास आम्ही प्रतिसाद देतो किंवा नसल्यास त्रुटी देतो. नाहीतर
2. झूम वाढवा आणि सुरू ठेवा.

एक मार्ग किंवा दुसरा, घटक सापडण्याची हमी दिली जाते आणि जेव्हा हे घडते तेव्हाच सीमा तपासणी केली जाते. ही एक सखोल कल्पना आहे, परंतु अगदी नवशिक्या प्रोग्रामरसाठीही हे सोपे आहे. मी कदाचित इतरांशी कामाच्या प्रासंगिकतेबद्दल बोलू शकत नाही, परंतु मी हे शहाणपण वैयक्तिक आणि व्यावसायिक दोन्ही कोडमध्ये लागू करू शकलो. टीएओसीपी पुस्तक अशा रत्नांनी भरलेले आहे (न्यायपूर्वक सांगायचे तर, तेथे बर्याच विचित्र गोष्टी देखील आहेत, जसे की बबल क्रमवारी).

"शोधा, शोधा
इतके लांब
शोधा, शोधा
मला फक्त नाचायचे होते"
- ल्यूथर वॅन्डरॉस, "द सर्च" (1980)

टायपो #2

दुसरी टायपो व्हॉल्यूम 4A, कॉम्बिनेटोरियल अल्गोरिदम, भाग 1 मध्ये आहे. पृष्ठ 60 विविध कॅसिनोमध्ये कॉमेडियन्सचे कार्यक्रम शेड्यूल करण्याच्या समस्येचे वर्णन करते. लिली टॉमलिन, वियर्ड अल यांकोविक आणि रॉबिन विल्यम्स यांच्यासह अनेक वास्तविक जीवनातील विनोदी कलाकार उदाहरणे म्हणून उद्धृत केले जातात, जे पुस्तक प्रकाशित झाले तेव्हाही जिवंत होते. नुथ नेहमी इंडेक्समध्ये संपूर्ण नावांची यादी करतो, म्हणून विल्यम्सला पृष्ठ 882 वर "विलियम्स, रॉबिन मॅक्लॉरिम" म्हणून सूचीबद्ध केले आहे. पण त्याचे मधले नाव “n” ने संपते आणि “m” नाही, म्हणजेच मॅक्लॉरिन.

मॅक्लॉरिन हे त्याच्या आईचे पहिले नाव होते. मिसिसिपीचे ३४ वे गव्हर्नर अँसेल्म जोसेफ मॅकलॉरिन यांची ती पणतू होती. त्याच्या कारकिर्दीला, वरवर पाहता, कोणत्याही चांगल्यासाठी लक्षात ठेवले गेले नाही. पुस्तकातून "मिसिसिपी: इतिहास":

“मॅकलॉरिन प्रशासनादरम्यानची सर्वात महत्त्वाची घटना म्हणजे 1898 च्या वसंत ऋतूमध्ये युनायटेड स्टेट्सने स्पेनवर केलेली युद्धाची घोषणा... दुर्दैवाने, युद्धामुळे काही सरकारी अधिकाऱ्यांना लाचखोरी करण्याची संधी मिळाली असावी. मॅक्लॉरिनवर विविध शंकास्पद पद्धतींचा आरोप होता, ज्यात नेपोटिझम आणि माफी अधिकारांचा अतिवापर यांचा समावेश होता. संयम आंदोलनादरम्यान, समीक्षकांनी राज्यपालांवर मद्यपी असल्याचा आरोप केला, ज्याची त्यांनी जाहीरपणे कबुली दिली.

ऐतिहासिक चूक

विचार करा पारंपारिक गुणाकार अल्गोरिदम शालेय अभ्यासक्रमातून. त्यासाठी किती एकल-अंकी गुणाकार आवश्यक आहेत? समजा तुम्ही गुणाकार करा - अंकी संख्या वर -बिट . प्रथम पहिल्या अंकाचा गुणाकार करा प्रत्येक अंकासाठी एक एक करून. नंतर दुसरा अंक गुणाकार करा प्रत्येक अंकासाठी जोपर्यंत तुम्ही सर्व आकड्यांमधून जात नाही तोपर्यंत एक एक आणि असेच . अशा प्रकारे पारंपारिक गुणाकार आवश्यक आहे आदिम गुणाकार. विशेषतः, दोन संख्यांनी गुणाकार करणे रँक आवश्यक आहे एकल-अंकी गुणाकार.

हे वाईट आहे, परंतु सोव्हिएत गणितज्ञ अनातोली अलेक्सेविच करात्सुबा यांनी विकसित केलेल्या पद्धतीचा वापर करून प्रक्रिया ऑप्टिमाइझ करणे शक्य आहे. चला ते ढोंग करूया и  - दोन-अंकी दशांश संख्या; म्हणजे, संख्या आहेत , , , असे की и (हे अल्गोरिदम मोठ्या संख्येवर सामान्य करण्यासाठी काही फेरफार आवश्यक आहे; जरी ते फार कठीण नसले तरी, तपशील चुकीचा होऊ नये म्हणून, मी एका साध्या उदाहरणावर चिकटून राहीन). मग , , . द्विपदी गुणाकार देते . या क्षणी आमच्याकडे अजूनही आहे एकल-अंकी गुणाकार: , , , . आता बेरीज आणि वजाबाकी करू . काही पुनर्रचना केल्यानंतर, जे मी वाचकांसाठी एक व्यायाम म्हणून सोडेन, ते बाहेर वळते  - फक्त तीन एकल-अंकी गुणाकार! (काही स्थिर गुणांक आहेत, परंतु ते फक्त अंक जोडून आणि हलवून मोजले जाऊ शकतात).

पुरावा मागू नका, पण करात्सुबा अल्गोरिदम (वरील उदाहरणावरून वारंवार सामान्यीकृत) पारंपारिक गुणाकार पद्धतीवर सुधारते आधी ऑपरेशन्स . कृपया लक्षात घ्या की ही अल्गोरिदमची वास्तविक सुधारणा आहे, मानसिक गणनांसाठी ऑप्टिमायझेशन नाही. खरंच, अल्गोरिदम मानसिक अंकगणितासाठी योग्य नाही, कारण त्याला आवर्ती ऑपरेशन्ससाठी मोठ्या ओव्हरहेड खर्चाची आवश्यकता असते. शिवाय, जोपर्यंत संख्या पुरेशी मोठी होत नाही तोपर्यंत प्रभाव पूर्णपणे प्रकट होणार नाही (सुदैवाने, करत्सुबाचे अल्गोरिदम आणखी वेगवान पद्धतींनी बदलले गेले आहे: मार्च 2019 मध्ये, एक अल्गोरिदम प्रकाशित झाला ज्यासाठी फक्त n लॉग n गुणाकार; प्रवेग केवळ अकल्पनीय मोठ्या संख्येवर लागू होतो).

या अल्गोरिदमचे वर्णन खंड 295, अर्ध-संख्यात्मक अल्गोरिदमच्या पृष्ठ XNUMX वर केले आहे. तेथे नुथ लिहितात: “हे आश्चर्यकारक आहे की ही कल्पना फक्त मध्येच शोधली गेली 1962 वर्ष," जेव्हा करत्सुबाच्या अल्गोरिदमचे वर्णन करणारा लेख प्रकाशित झाला. परंतु! 1995 मध्ये, करात्सुबा यांनी "संगणकीय जटिलता" हा शोधनिबंध प्रकाशित केला, ज्यात अनेक गोष्टी सांगितल्या आहेत: 1) 1956 च्या आसपास, कोल्मोगोरोव्हने सुचवले की गुणाकार यापेक्षा कमी वेळात करता येत नाही. पायऱ्या 2) मध्ये 1960 वर्ष करात्सुबा सेमिनारमध्ये उपस्थित होते जेथे कोल्मोगोरोव्हने त्याचे गृहितक n² मांडले. 3) "बरोबर एका आठवड्यात," करात्सुबाने "विभाजित करा आणि जिंका" अल्गोरिदम विकसित केला; 4) 1962 मध्ये कोल्मोगोरोव्हने एक लेख लिहिला आणि प्रकाशित केला करत्सुबाच्या वतीने अल्गोरिदमच्या वर्णनासह. "मला हा लेख पुन्हा प्रकाशित झाल्यानंतरच कळला."

त्यामुळे त्रुटी त्याऐवजी आहे 1962 निर्दिष्ट करणे आवश्यक आहे 1960 वर्ष इतकंच.

अॅनालिझ

त्रुटी शोधण्यासाठी विशेष कौशल्याची आवश्यकता नाही.

1. पहिली त्रुटी शक्य तितकी क्षुल्लक होती आणि ती तुलनेने दृश्यमान ठिकाणी होती (अध्यायाची सुरुवात). कोणत्याही मूर्खाला ते सापडले असते; मी फक्त तो मूर्ख निघालो.
2. दुसरी टायपो शोधण्यासाठी नशीब आणि परिश्रम आवश्यक आहे, परंतु कौशल्य नाही. "विलियम्स" ची अनुक्रमणिका खंडाच्या उपांत्य पानावर आहे, जो पुस्तकाचा एक प्रमुख भाग आहे. मी फक्त अनुक्रमणिका उलगडत होतो (हे वाटते तितके दयनीय नाही, कारण नूथच्या निर्देशांकात इस्टर अंडी लपलेली आहेत. उदाहरणार्थ, अरबी आणि हिब्रूमध्ये नोंदी आहेत, दोन्ही पृष्ठ 66 कडे निर्देश करतात. परंतु त्या पृष्ठाचा उल्लेख नाही एकतर भाषा; त्याऐवजी ते "उजवीकडून डावीकडे वाचल्या जाणार्‍या भाषा" चा संदर्भ देते). आणि दुसऱ्या नावाने माझे लक्ष वेधून घेतले. मी सहसा विकिपीडिया वाचत असल्याने, मी रॉबिन विल्यम्स तपासले आणि एक विसंगती लक्षात आली.
3. मला असे म्हणायचे आहे की मी ऐतिहासिक त्रुटी शोधण्यासाठी गंभीर संशोधन केले आहे, परंतु खरोखर मी फक्त पाहिले करात्सुबाच्या अल्गोरिदमबद्दल विकिपीडिया पृष्ठ. पहिल्याच ओळी म्हणतात: “करात्सुबा अल्गोरिदम हा वेगवान गुणाकार अल्गोरिदम आहे. 1960 मध्ये अनातोली करात्सुबा यांनी शोधून काढले आणि 1962 मध्ये प्रकाशित केले. त्यानंतर दोन आणि दोन जोडायचे बाकी होते.

भविष्यात मला आणखी लक्षणीय बग शोधायचा आहे, विशेषत: नुथच्या कोडमध्ये. मला मूलभूत अल्गोरिदमच्या पहिल्या खंडात एक बग देखील शोधायचा आहे. कदाचित मला ते सापडले असते, परंतु काही कारणास्तव स्थानिक लायब्ररीमध्ये फक्त खंड 2, 3 आणि 4A आहेत.

आर्थिक तथ्ये:

• एकूण, TAOCP मध्ये माझ्या योगदानामध्ये फक्त तीन वर्ण आहेत: एक जोड s, बदली m वर n и 2 वर 0. $2,56 वर, ही काही आकर्षक चिन्हे आहेत; जर तुम्हाला अशा प्रकारचे पैसे दिले गेले तर, 1000 शब्दांचा (सरासरी चार वर्णांचा) लेख तुम्हाला दहा भव्य कमाई करेल.
• तीन हेक्साडेसिमल डॉलर्ससह, मी, इतर 29 नागरिकांसह, सॅन सेरिफ बँकेच्या सर्वात श्रीमंत ठेवीदारांच्या यादीत (69 मे 1 पर्यंत) 2019 व्या स्थानावर आहे.

नुथकडून चेकबद्दल इतर चर्चा

• नुथकडून चेक कसा मिळवायचा

  नुथच्या पुस्तकांमधील त्रुटी शोधण्यासाठी सामान्य शिफारसी. बहुतेक ते तांत्रिक त्रुटींशी संबंधित असतात, ज्या माझ्याकडे नाहीत. तेथे एक सूचना आहे जी मी गांभीर्याने घेतली:

  सबमिट करण्यासाठी तुम्ही त्रुटींचा संच गोळा करेपर्यंत प्रतीक्षा करणे चांगले. बर्‍याच वास्तविक परंतु अत्यंत मौल्यवान त्रुटी एकत्र करून, आपण त्यापैकी एक चूक किंवा सल्ला मानली जाण्याची शक्यता वाढवता. तुम्ही एकावेळी एरर सबमिट केल्यास, प्रत्येकाला वैयक्तिकरित्या नाकारले जाऊ शकते.

  मला फक्त निरर्थक टंकलेखन पाठवायचे नव्हते, परंतु मला एक ऐतिहासिक चूक आढळली जी पुरेशी गंभीर वाटली तेव्हाच सल्ला घेतला आणि पत्र पाठवले.

• आशुतोष मेहरा यांचे धनादेश

  BoSS मध्ये 0x$207.f0 एवढी प्रचंड निव्वळ संपत्ती असलेले आशुतोष मेहरा सॅन सेरिफमधील तिसरे सर्वात श्रीमंत गुंतवणूकदार आहेत.

• रिअल TeX कोडमध्ये काही गैर-कार्यक्षम बग तपासा
• मिश्रित: #1 #2 #3 #4 #5 #6

स्त्रोत: www.habr.com