डोनाल्ड नुथ एक कंप्यूटर वैज्ञानिक है जो अपनी सुझाई गई पुस्तकों की सटीकता की बहुत परवाह करता है एक हेक्स डॉलर ($2,56, 0x$1,00) पाई गई किसी भी "त्रुटि" के लिए, जहां त्रुटि को ऐसी किसी भी चीज़ के रूप में परिभाषित किया जाता है जो "तकनीकी रूप से, ऐतिहासिक रूप से, टाइपोग्राफ़िक रूप से, या राजनीतिक रूप से गलत है।" मैं वास्तव में नथ से एक चेक प्राप्त करना चाहता था, इसलिए मैंने उसकी महान कृति में त्रुटियों को देखने का निर्णय लिया "प्रोग्रामिंग की कला" (टीएओसीपी)। हम तीन ढूंढने में कामयाब रहे। अपने वचन के अनुसार, नॉट ने एक चेक भेजा 0x$3,00.

जैसा कि आप देख सकते हैं, यह वास्तविक जाँच नहीं है। नथ वास्तविक चेक भेजता था, लेकिन 2008 में बंद हो गया बड़े पैमाने पर धोखाधड़ी. अब वह "जमा के व्यक्तिगत प्रमाणपत्र" भेजता है बैंक ऑफ सैन सेरिफ़ (मालिक)। वह कहता है कि यदि आवश्यक हो तो वह वास्तविक धन भेजने को तैयार है, लेकिन ऐसा लगता है कि यह बहुत अधिक परेशानी भरा है।

मुझे दो टाइपो त्रुटियाँ और एक ऐतिहासिक त्रुटि मिली। मैं उन्हें घटती तुच्छता के क्रम में सूचीबद्ध करूंगा।

टाइपो #1

पहला टाइपो तीसरे खंड "सॉर्टिंग एंड सर्च" के पृष्ठ 392 पर है, नीचे से आठवीं पंक्ति: "असफल खोज के बाद, कभी-कभी (कभी-कभी) युक्त तालिका में एक नया रिकॉर्ड दर्ज करना वांछनीय होता है K; ऐसा करने वाली विधि को खोज और सम्मिलित एल्गोरिथ्म कहा जाता है। गलती यह है कि इसके बजाय कुछ समय होना ही चाहिए कभी कभी.

बेशक, ऐसी गलती कोई आश्चर्य की बात नहीं है। अकेले इस लेख में कुछ टाइप त्रुटियां होनी तय हैं (उन्हें ढूंढने के लिए कोई पुरस्कार नहीं है)। वास्तव में आश्चर्य की बात यह है कि इतने लंबे समय तक इस पर किसी का ध्यान नहीं गया। पृष्ठ 392 गणित अनुभाग में गहराई से छिपा नहीं है, यह है सबसे पहला पृष्ठ अध्याय 6 "खोज"! संभवतः पुस्तक के सर्वाधिक पढ़े जाने वाले अनुभागों में से एक। सिद्धांत रूप में, सबसे कम टाइपिंग त्रुटियां होनी चाहिए, लेकिन नहीं।

वैसे, यदि आपने कभी TAOCP पढ़ने के बारे में सोचा है, तो इसे आज़माएँ। कई लोग कहेंगे कि यह है निर्देशिका, सीधे पढ़ने के लिए अभिप्रेत नहीं है, लेकिन यह सच नहीं है। लेखक का दृष्टिकोण स्पष्ट और विशिष्ट शैली है। एकमात्र चीज़ जो पठनीयता में बाधक है वह है गणित की जटिलता। हालाँकि, इसका एक सरल समाधान है: जब तक आपको गणित समझ में न आए तब तक पढ़ें, इसे छोड़ दें, और अगले भाग पर जाएँ जिसे आप समझ सकते हैं। इस तरह पढ़ते हुए, मुझे किताब का कम से कम 80% हिस्सा याद आ गया, लेकिन बाकी 20% बहुत बढ़िया है!

यह भी कहा जाता है कि TAOCP अप्रासंगिक, पुराना है या अन्यथा "वास्तविक प्रोग्रामिंग" पर लागू नहीं है। ये भी सच नहीं है. उदाहरण के लिए, परिचय के बाद पहला खंड एक अवर्गीकृत सरणी में एक तत्व खोजने पर विचार करता है। सबसे सरल एल्गोरिदम सभी प्रोग्रामर से परिचित है। सरणी की शुरुआत में पॉइंटर प्रारंभ करें, फिर लूप में निम्न कार्य करें:

1. जांचें कि क्या वर्तमान तत्व वांछित है। यदि हां, तो हम इसे वापस कर देते हैं; अन्यथा
2. जांचें कि क्या सूचक सरणी सीमा के बाहर है। यदि ऐसा है, तो एक त्रुटि लौटाएँ; अन्यथा
3. ज़ूम इन करें और जारी रखें।

अब विचार करें: इस एल्गोरिदम को औसतन कितनी सीमा जांच की आवश्यकता होती है? सबसे खराब स्थिति में, जहां सरणी में कोई तत्व नहीं है, सूची में प्रत्येक तत्व को एक जांच की आवश्यकता होगी, और औसतन यह कुछ इस तरह होगा . एक बेहतर खोज एल्गोरिदम केवल एक सीमा जांच से दूर हो सकता है। वांछित तत्व को सरणी के अंत में संलग्न करें, फिर सरणी की शुरुआत में पॉइंटर शुरू करें और लूप में निम्नलिखित कार्य करें:

1. जांचें कि क्या वर्तमान तत्व वांछित है। यदि ऐसा है, तो यदि सूचक सरणी के भीतर है तो हम एक प्रतिक्रिया लौटाते हैं, या यदि नहीं है तो एक त्रुटि लौटाते हैं। अन्यथा
2. ज़ूम इन करें और जारी रखें।

किसी भी तरह, तत्व मिलने की गारंटी है, और ऐसा होने पर सीमा जांच केवल एक बार की जाती है। यह एक गहरा विचार है, लेकिन नौसिखिए प्रोग्रामर के लिए भी यह काफी सरल है। मैं शायद दूसरों के लिए काम की प्रासंगिकता के बारे में बात नहीं कर सकता, लेकिन मैं तुरंत इस ज्ञान को व्यक्तिगत और व्यावसायिक कोड दोनों पर लागू करने में सक्षम था। टीएओसीपी पुस्तक ऐसे रत्नों से भरी है (सच कहें तो, इसमें बहुत सी अजीब चीजें भी हैं, जैसे कि बुलबुले की तरह).

"खोजें, खोजें
बहुत लंबा
खोजो, खोजो
मैं बस नृत्य करना चाहता था"
- लूथर वैंड्रॉस, "द सर्च" (1980)

टाइपो #2

दूसरा टाइपो वॉल्यूम 4ए, कॉम्बिनेटोरियल एल्गोरिदम, भाग 1 में है। पृष्ठ 60 विभिन्न कैसीनो में प्रदर्शन करने के लिए कॉमेडियन को शेड्यूल करने से जुड़ी एक समस्या का वर्णन करता है। कई वास्तविक जीवन के हास्य कलाकारों को उदाहरण के रूप में उद्धृत किया गया है, जिनमें लिली टॉमलिन, वेर्ड अल यांकोविक और रॉबिन विलियम्स शामिल हैं, जो पुस्तक प्रकाशित होने के समय भी जीवित थे। नथ हमेशा सूचकांक में पूरा नाम सूचीबद्ध करता है, इसलिए विलियम्स को पृष्ठ 882 पर "विलियम्स, रॉबिन मैकलोरिम" के रूप में सूचीबद्ध किया गया है। लेकिन उनका मध्य नाम "n" से ख़त्म होता है न कि "m" से, यानी मैकलॉरिन।

मैकलॉरिन उनकी मां का पहला नाम था। वह मिसिसिपी के 34वें गवर्नर एंसलम जोसेफ मैकलॉरिन की परपोती थीं। जाहिर तौर पर उनके शासनकाल को किसी भी अच्छे काम के लिए याद नहीं किया गया। किताब से "मिसिसिपी: इतिहास":

“मैकलॉरिन प्रशासन के दौरान सबसे महत्वपूर्ण घटना 1898 के वसंत में संयुक्त राज्य अमेरिका द्वारा स्पेन पर युद्ध की घोषणा थी... दुर्भाग्य से, युद्ध ने कुछ सरकारी अधिकारियों को रिश्वतखोरी में शामिल होने का अवसर प्रदान किया होगा। मैकलॉरिन पर भाई-भतीजावाद और क्षमा शक्तियों के अत्यधिक उपयोग सहित विभिन्न संदिग्ध प्रथाओं का आरोप लगाया गया था। संयम आंदोलन के दौरान, आलोचकों ने गवर्नर पर शराबी होने का आरोप लगाया, जिसे उन्होंने सार्वजनिक रूप से स्वीकार किया।

ऐतिहासिक त्रुटि

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

यह बुरा है, लेकिन सोवियत गणितज्ञ अनातोली अलेक्सेविच करात्सुबा द्वारा विकसित विधि का उपयोग करके प्रक्रिया को अनुकूलित करना संभव है। चलिए ऐसा दिखावा करते हैं и  - दो अंकों की दशमलव संख्या; अर्थात् संख्याएँ हैं , , , ऐसा है कि и (इस एल्गोरिदम को बड़ी संख्या में सामान्यीकृत करने के लिए कुछ हेरफेर की आवश्यकता होती है; हालांकि यह बहुत मुश्किल नहीं है, विवरण में गलतियाँ न करने के लिए, बेहतर होगा कि मैं एक सरल उदाहरण पर ही निर्भर रहूँ)। तब , , . द्विपदों को गुणा करने पर प्राप्त होता है . फिलहाल हमारे पास अभी भी है एकल-अंकीय गुणन: , , , . अब जोड़ते और घटाते हैं . कुछ पुनर्व्यवस्थाओं के बाद, जिसे मैं पाठक के लिए एक अभ्यास के रूप में छोड़ दूँगा, यह स्पष्ट हो जाता है  - केवल तीन एकल-अंकीय गुणन! (कुछ स्थिर गुणांक हैं, लेकिन उनकी गणना केवल अंकों को जोड़कर और स्थानांतरित करके की जा सकती है)।

सबूत मत मांगो, लेकिन करात्सुबा एल्गोरिथ्म (उपरोक्त उदाहरण से पुनरावर्ती रूप से सामान्यीकृत) पारंपरिक गुणन विधि में सुधार करता है संचालन पहले . कृपया ध्यान दें कि यह एल्गोरिथम में वास्तविक सुधार है, मानसिक गणनाओं के लिए अनुकूलन नहीं। दरअसल, एल्गोरिदम मानसिक अंकगणित के लिए उपयुक्त नहीं है, क्योंकि इसमें पुनरावर्ती संचालन के लिए बड़ी ओवरहेड लागत की आवश्यकता होती है। इसके अलावा, प्रभाव तब तक पूरी तरह से प्रकट नहीं होगा जब तक कि संख्याएं काफी बड़ी न हो जाएं (सौभाग्य से, करात्सुबा के एल्गोरिदम को और भी तेज तरीकों से बदल दिया गया है: मार्च 2019 में, एक एल्गोरिदम प्रकाशित किया गया था जिसके लिए केवल आवश्यकता होती है) एन लॉग एन गुणा; त्वरण केवल अकल्पनीय रूप से बड़ी संख्याओं पर लागू होता है)।

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

तो त्रुटि यह है कि इसके बजाय 1962 निर्दिष्ट किया जाना चाहिए 1960 वर्ष। बस इतना ही।

के विश्लेषण

त्रुटियाँ ढूँढ़ने के लिए विशेष कौशल की आवश्यकता नहीं होती।

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

भविष्य में मैं एक और अधिक महत्वपूर्ण बग ढूंढना चाहूँगा, विशेषकर नथ के कोड में। मैं मौलिक एल्गोरिदम के पहले खंड में एक बग भी ढूंढना चाहूंगा। शायद मुझे यह मिल गया होता, लेकिन किसी कारण से स्थानीय पुस्तकालय में केवल खंड 2, 3 और 4ए हैं।

वित्तीय तथ्य:

• कुल मिलाकर, टीएओसीपी में मेरे योगदान में केवल तीन अक्षर शामिल हैं: एक अतिरिक्त 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