डोनाल्ड नुथ एक कंप्यूटर वैज्ञानिक हैं, जो अपनी पुस्तकों की शुद्धता के बारे में इतनी परवाह करते हैं कि वह किसी भी "त्रुटि" के लिए एक हेक्स डॉलर ($ 2.56, 0x $ 1.00) प्रदान करते हैं, जहां सब कुछ जो "तकनीकी रूप से, ऐतिहासिक रूप से, टाइपोग्राफी, एक त्रुटि माना जाता है।" या राजनीतिक रूप से गलत है। ” मैं वास्तव में नॉट से चेक प्राप्त करना चाहता था, इसलिए मैंने उनके उत्कृष्ट कार्य "द आर्ट ऑफ़ प्रोग्रामिंग" (TAOCP) में त्रुटियों की तलाश करने का निर्णय लिया। मैं तीन खोजने में कामयाब रहा। इस शब्द के लिए सही है, नॉट ने 0x $ 3.00 के लिए एक चेक भेजा।



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

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

टाइपो नंबर 1

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

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

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

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

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

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

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

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

“खोजो, खोजो
इतना लंबा
खोज, खोज
मैं सिर्फ डांस करना चाहता था। ”
- लूथर वैंड्रॉस, सर्च (1980)

टाइपो नंबर 2

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

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

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

ऐतिहासिक भूल

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

यह बुरा है, लेकिन आप सोवियत गणितज्ञ अनातोली अलेक्सेविच कारत्सुबा द्वारा विकसित विधि का उपयोग करके प्रक्रिया को अनुकूलित कर सकते हैं। मान लिया कि $$$x$ और $$$य$ - दोहरे अंकों की दशमलव संख्या; यानी नंबर होते हैं $$$एक$ । $$$ब$ । $$$सी$ । $$$ड$ ऐसा है $$$x = (ab) _ {10}$ और $$$y = (cd) _ {10}$ (बड़ी संख्या में इस एल्गोरिथ्म के सामान्यीकरण के लिए कुछ हेरफेर की आवश्यकता होती है; हालांकि यह बहुत मुश्किल नहीं है, लेकिन विवरण में गलत नहीं होने के लिए, मैं एक सरल उदाहरण के लिए बेहतर हूं)। तो $$$x = 10a + b$ । $$$y = 10c + d$ । $$$xy = (10a + b) (10c + d)$ । द्विपद का गुणन देता है $$$xy = 100ac + 10ad + 10bc + bd$ । फिलहाल, हम अभी भी $$$n ^ 2 = 4$ एकल बिट गुणन: $$$एसी$ । $$$विज्ञापन$ । $$$ई.पू$ । $$$bd$ । अब जोड़ें और घटाएं $$$10ac + 10bc$ । कुछ क्रमपरिवर्तन के बाद, जिसे मैं पाठक के लिए एक अभ्यास के रूप में छोड़ूंगा, यह पता चला है $$$xy = 110ac + 11bd + 10 (a - b) (d - c)$ - केवल तीन एक अंक गुणा! (कुछ निरंतर गुणांक हैं, लेकिन उन्हें केवल अंकों को जोड़ने और स्थानांतरित करके गणना की जा सकती है)।

सबूत के लिए मत पूछो, लेकिन Karatsuba एल्गोरिथ्म (उपरोक्त उदाहरण से सामान्य रूप से सामान्यीकृत) से गुणा करने की पारंपरिक विधि में सुधार होता है $$$O (n ^ 2)$ पहले संचालन $$$O (n ^ {(lg 3)})$ । कृपया ध्यान दें कि यह एल्गोरिथ्म में एक वास्तविक सुधार है, मानसिक गणना के लिए अनुकूलन नहीं है। दरअसल, एल्गोरिथ्म दिमाग में गणना करने के लिए उपयुक्त नहीं है, क्योंकि इसे पुनरावर्ती संचालन के लिए एक बड़े ओवरहेड की आवश्यकता होती है। इसके अलावा, प्रभाव पूरी तरह से स्पष्ट नहीं होगा जब तक कि संख्या पर्याप्त रूप से बड़ी नहीं हो जाती (सौभाग्य से, करतसुबा एल्गोरिदम के बजाय, यहां तक ​​कि तेज तरीके भी आए: मार्च 2019 में, एक एल्गोरिथ्म प्रकाशित किया गया था कि केवल एन लॉग एन गुणन की आवश्यकता है; त्वरण केवल अकल्पनीय रूप से बड़े पर लागू होता है; संख्या)।

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

इस प्रकार, गलती यह है कि 1962 के बजाय 1960 का संकेत दिया जाना चाहिए। वह सब है।

के विश्लेषण

त्रुटियों की खोज के लिए बहुत कौशल की आवश्यकता नहीं थी।

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

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

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

• कुल मिलाकर, TAOCP में मेरे योगदान में केवल तीन वर्ण हैं: एक जोड़ने वाला s , n की जगह m और 2 को 0 के साथ। $ 2.56 की कीमत, ये बहुत ही आकर्षक प्रतीक हैं; यदि आपको उस तरह के पैसे का भुगतान किया गया था, तो 1000 शब्दों का एक लेख (औसतन, चार वर्ण प्रत्येक) आपको दस टुकड़े लाएगा।
  
• तीन हेक्साडेसिमल डॉलर के साथ, मैं, 29 अन्य नागरिकों के साथ, बैंक ऑफ सैन सेरिफ़ (1 मई, 2019 तक) के सबसे अमीर जमाकर्ताओं की सूची में 69 वां स्थान साझा करता हूं।

Knut जाँच के अन्य चर्चाएँ

• नॉट से चेक कैसे प्राप्त करें
  
  नुट की किताबों में कीड़े खोजने के लिए सामान्य दिशानिर्देश। ज्यादातर तकनीकी त्रुटियां जो मेरे पास नहीं हैं। एक सुझाव है जिसे मैंने गंभीरता से लिया है:
  
  

  जब तक आप भेजने के लिए त्रुटियों का एक समूह एकत्र नहीं करते तब तक इंतजार करना बेहतर है। कई वास्तविक, लेकिन बहुत मूल्यवान त्रुटियों के संयोजन से, आप इस संभावना को बढ़ा देंगे कि उनमें से एक को वास्तव में त्रुटि या सलाह के रूप में माना जाएगा। यदि आप एक समय में त्रुटियों को भेजते हैं, तो प्रत्येक को व्यक्तिगत रूप से अस्वीकार कर दिया जा सकता है।

  
  मैं बकवास टाइप्स नहीं भेजना चाहता था, लेकिन मैंने सलाह मानी और केवल एक पत्र भेजा जब मुझे एक ऐतिहासिक त्रुटि मिली जो काफी गंभीर लग रही थी।
  
• आशुतोष मेहरा की जाँच
  
  आशुतोष मेहरा, BoSSS में 0x $ 207, f0 के शानदार भाग्य के साथ सैन सेरिफ़ के लिए तीसरे सबसे अमीर योगदानकर्ता हैं।
  
• वास्तविक TeX कोड में कुछ गैर-कार्यात्मक त्रुटियों के लिए जाँच करें
  
• विविध: # 1 # 2 # 3 # 4 # 5 # 6