డోనాల్డ్ నత్ అతను సూచించే తన పుస్తకాల ఖచ్చితత్వం గురించి చాలా శ్రద్ధ వహించే ఒక కంప్యూటర్ శాస్త్రవేత్త ఒక హెక్స్ డాలర్ కనుగొనబడిన ఏదైనా "లోపం" కోసం ($2,56, 0x$1,00) లోపం "సాంకేతికంగా, చారిత్రకంగా, టైపోగ్రాఫికల్‌గా లేదా రాజకీయంగా తప్పు" అని నిర్వచించబడుతుంది. నేను నిజంగా Knuth నుండి చెక్ పొందాలనుకుంటున్నాను, కాబట్టి నేను అతని గొప్ప పనిలో లోపాలను చూడాలని నిర్ణయించుకున్నాను "ది ఆర్ట్ ఆఫ్ ప్రోగ్రామింగ్" (TAOCP). మేము ముగ్గురిని కనుగొనగలిగాము. తన మాటను నిజం చేస్తూ, నట్ చెక్ పంపాడు 0x$3,00.

మీరు గమనిస్తే, ఇది నిజమైన చెక్ కాదు. Knuth నిజమైన చెక్కులను పంపేవాడు, కానీ కారణంగా 2008లో ఆగిపోయింది ప్రబలమైన మోసం. అతను ఇప్పుడు "డిపాజిట్ యొక్క వ్యక్తిగత ధృవపత్రాలను" పంపుతాడు బ్యాంక్ ఆఫ్ శాన్ సెరిఫ్ (BoSS). అవసరమైతే నిజమైన డబ్బు పంపడానికి సిద్ధంగా ఉన్నానని, అయితే ఇది చాలా అవాంతరంగా ఉన్నట్లు అనిపిస్తుంది.

నేను రెండు అక్షరదోషాలు మరియు ఒక చారిత్రక దోషాన్ని కనుగొన్నాను. ట్రివియాలిటీని తగ్గించే క్రమంలో నేను వాటిని జాబితా చేస్తాను.

అక్షర దోషం #1

మొదటి అక్షర దోషం "సార్టింగ్ మరియు సెర్చ్" యొక్క మూడవ సంపుటంలోని 392వ పేజీలో ఉంది, దిగువ నుండి ఎనిమిదవ పంక్తి: "విఫలమైన శోధన తర్వాత, కొన్నిసార్లు (కొన్నిసార్లు) కలిగి ఉన్న పట్టికలో కొత్త రికార్డ్‌ను నమోదు చేయడం మంచిది K; దీన్ని చేసే పద్ధతిని శోధన మరియు ఇన్సర్ట్ అల్గోరిథం అంటారు. దానికి బదులు పొరపాటు కొన్నిసార్లు ఉండాలి కొన్నిసార్లు.

వాస్తవానికి, అలాంటి పొరపాటు ఆశ్చర్యం కలిగించదు. ఈ వ్యాసంలో మాత్రమే కొన్ని అక్షరదోషాలు ఉన్నాయి (వాటిని కనుగొన్నందుకు రివార్డ్‌లు లేవు). అసలు ఆశ్చర్యం ఏంటంటే.. ఇంత కాలం అది ఎవరికీ తెలియకుండా పోయింది. పేజీ 392 గణిత విభాగంలో లోతుగా పాతిపెట్టబడలేదు, అది మొదటి పేజీ అధ్యాయం XNUMX "శోధన"! బహుశా పుస్తకంలోని అత్యధికంగా చదివే విభాగాలలో ఒకటి. సిద్ధాంతంలో, అతి తక్కువ అక్షరదోషాలు ఉండాలి, కానీ లేవు.

అయితే, మీరు ఎప్పుడైనా TAOCP చదవడం గురించి ఆలోచించినట్లయితే, ఒకసారి ప్రయత్నించండి. ఇది అని చాలామంది చెబుతారు డైరెక్టరీ, నేరుగా చదవడానికి ఉద్దేశించబడలేదు, కానీ ఇది నిజం కాదు. రచయితకు స్పష్టమైన దృక్కోణం మరియు విలక్షణమైన శైలి ఉంది. చదవడానికి ఆటంకం కలిగించే ఏకైక విషయం గణితం యొక్క సంక్లిష్టత. అయితే, ఒక సాధారణ పరిష్కారం ఉంది: మీకు అర్థం కాని గణితానికి వచ్చే వరకు చదవండి, దానిని దాటవేయండి మరియు మీరు అర్థం చేసుకోగలిగే తదుపరి విభాగానికి వెళ్లండి. ఈ విధంగా చదవడం వల్ల, నేను కనీసం 80% పుస్తకం మిస్ అయ్యాను, కానీ మిగిలిన 20% చాలా బాగుంది!

ఇది TAOCP అని కూడా చెప్పబడింది అప్రస్తుతం, పాతది లేదా "నిజమైన ప్రోగ్రామింగ్"కి వర్తించదు. ఇది కూడా నిజం కాదు. ఉదాహరణకు, పరిచయం తర్వాత మొదటి విభాగం క్రమబద్ధీకరించని శ్రేణిలో ఒక మూలకాన్ని కనుగొనడాన్ని చూస్తుంది. సరళమైన అల్గోరిథం అన్ని ప్రోగ్రామర్‌లకు సుపరిచితం. శ్రేణి ప్రారంభంలో పాయింటర్‌ను ప్రారంభించండి, ఆపై క్రింది వాటిని లూప్‌లో చేయండి:

1. ప్రస్తుత మూలకం కావలసినది కాదా అని తనిఖీ చేయండి. అలా అయితే, మేము దానిని తిరిగి ఇస్తాము; లేకుంటే
2. పాయింటర్ శ్రేణి సరిహద్దు వెలుపల ఉందో లేదో తనిఖీ చేయండి. అలా అయితే, లోపాన్ని తిరిగి ఇవ్వండి; లేకుంటే
3. జూమ్ ఇన్ చేసి కొనసాగించండి.

ఇప్పుడు పరిగణించండి: ఈ అల్గారిథమ్‌కు సగటున ఎన్ని హద్దుల తనిఖీలు అవసరం? చెత్త సందర్భంలో, శ్రేణి మూలకాన్ని కలిగి ఉండకపోతే, జాబితాలోని ప్రతి మూలకానికి ఒక చెక్ అవసరం మరియు సగటున ఇది ఇలా ఉంటుంది . ఒక తెలివైన శోధన అల్గారిథమ్ కేవలం ఒక హద్దుల తనిఖీతో బయటపడవచ్చు. శ్రేణి చివర కావలసిన మూలకాన్ని జోడించి, ఆపై శ్రేణి ప్రారంభంలో పాయింటర్‌ను ప్రారంభించి, క్రింది వాటిని లూప్‌లో చేయండి:

1. ప్రస్తుత మూలకం కావలసినది కాదా అని తనిఖీ చేయండి. అలా అయితే, పాయింటర్ శ్రేణిలో ఉంటే మేము ప్రతిస్పందనను అందిస్తాము లేదా అది లేనట్లయితే లోపం ఏర్పడుతుంది. లేకపోతే
2. జూమ్ ఇన్ చేసి కొనసాగించండి.

ఒక మార్గం లేదా మరొకటి, మూలకం కనుగొనబడుతుందని హామీ ఇవ్వబడుతుంది మరియు ఇది జరిగినప్పుడు సరిహద్దుల తనిఖీ ఒకసారి మాత్రమే నిర్వహించబడుతుంది. ఇది లోతైన ఆలోచన, కానీ అనుభవం లేని ప్రోగ్రామర్‌కు కూడా ఇది చాలా సులభం. నేను బహుశా ఇతరులతో పని యొక్క ఔచిత్యం గురించి మాట్లాడలేను, కానీ నేను వెంటనే వ్యక్తిగత మరియు వృత్తిపరమైన కోడ్ రెండింటికీ ఈ జ్ఞానాన్ని వర్తింపజేయగలిగాను. TAOCP పుస్తకం అటువంటి రత్నాలతో నిండి ఉంది (నిజంగా చెప్పాలంటే, అందులో చాలా వింత విషయాలు కూడా ఉన్నాయి. బబుల్ విధమైన).

"శోధించండి, శోధించండి
చాలా దూరం
శోధించు, శోధించు
నేను డాన్స్ చేయాలనుకున్నాను"
- లూథర్ వాండ్రోస్, "ది సెర్చ్" (1980)

అక్షర దోషం #2

రెండవ అక్షర దోషం వాల్యూమ్ 4A, కాంబినేటోరియల్ అల్గారిథమ్స్, పార్ట్ 1. పేజీ 60 వివిధ కాసినోలలో హాస్యనటులు ప్రదర్శనను షెడ్యూల్ చేయడంలో ఉన్న సమస్యను వివరిస్తుంది. అనేకమంది నిజ-జీవిత హాస్యనటులు ఉదాహరణగా పేర్కొనబడ్డారు, వీరిలో లిల్లీ టామ్లిన్, విర్డ్ అల్ యాంకోవిక్ మరియు పుస్తకం ప్రచురించబడినప్పుడు ఇంకా జీవించి ఉన్న రాబిన్ విలియమ్స్ ఉన్నారు. Knuth ఎల్లప్పుడూ సూచికలో పూర్తి పేర్లను జాబితా చేస్తుంది, కాబట్టి విలియమ్స్ పేజీ 882లో "విలియమ్స్, రాబిన్ మెక్‌లోరిమ్"గా జాబితా చేయబడ్డాడు. కానీ అతని మధ్య పేరు "n" తో ముగుస్తుంది మరియు "m" కాదు, అంటే మెక్‌లౌరిన్.

మెక్‌లౌరిన్ అతని తల్లి మొదటి పేరు. ఆమె మిస్సిస్సిప్పి యొక్క 34వ గవర్నర్ అన్సెల్మ్ జోసెఫ్ మెక్‌లౌరిన్ యొక్క మనవరాలు. అతని పాలన, స్పష్టంగా, ఏదైనా మంచి కోసం గుర్తుంచుకోబడలేదు. పుస్తకం నుండి "మిసిసిపీ: చరిత్ర":

"మెక్‌లౌరిన్ పరిపాలనలో అత్యంత ముఖ్యమైన సంఘటన 1898 వసంతకాలంలో స్పెయిన్‌పై యునైటెడ్ స్టేట్స్ యుద్ధం ప్రకటించడం... దురదృష్టవశాత్తు, యుద్ధం కొంతమంది ప్రభుత్వ అధికారులకు లంచం తీసుకునే అవకాశాన్ని కల్పించి ఉండవచ్చు. బంధుప్రీతి మరియు క్షమాపణ అధికారాలను అధికంగా ఉపయోగించడంతో సహా అనేక సందేహాస్పద పద్ధతులకు మెక్‌లౌరిన్ ఆరోపణలు ఎదుర్కొన్నారు. నిగ్రహ ఉద్యమం సమయంలో, విమర్శకులు గవర్నర్‌ను తాగుబోతు అని ఆరోపించారు, దానిని అతను బహిరంగంగా అంగీకరించాడు.

చారిత్రక తప్పిదం

పరిగణించండి సాంప్రదాయ గుణకారం అల్గోరిథం పాఠశాల పాఠ్యాంశాల నుండి. దీనికి ఎన్ని ఒకే అంకెల గుణకారాలు అవసరం? మీరు గుణించారని అనుకుందాం -అంకెల సంఖ్య న -బిట్ . మొదట మొదటి అంకెను గుణించండి ప్రతి అంకెకు ఒక్కొక్కటిగా. అప్పుడు రెండవ అంకెను గుణించండి ప్రతి అంకెకు మీరు అన్ని సంఖ్యల ద్వారా వెళ్ళే వరకు ఒక్కొక్కటిగా మరియు అలా . అందువలన సంప్రదాయ గుణకారం అవసరం ఆదిమ గుణకారాలు. ముఖ్యంగా, రెండు సంఖ్యలను గుణించడం ర్యాంకులు అవసరం ఒకే-అంకెల గుణకారాలు.

ఇది చెడ్డది, కానీ సోవియట్ గణిత శాస్త్రజ్ఞుడు అనటోలీ అలెక్సీవిచ్ కరాట్సుబా అభివృద్ధి చేసిన పద్ధతిని ఉపయోగించి ప్రక్రియను ఆప్టిమైజ్ చేయడం సాధ్యపడుతుంది. అలా నటిద్దాం и  - రెండు అంకెల దశాంశ సంఖ్యలు; అంటే సంఖ్యలు ఉన్నాయి , , , అలాంటి и (ఈ అల్గోరిథంను పెద్ద సంఖ్యలకు సాధారణీకరించడానికి కొంత తారుమారు అవసరం; ఇది చాలా కష్టం కానప్పటికీ, వివరాలలో తప్పులు చేయకుండా ఉండటానికి, నేను ఒక సాధారణ ఉదాహరణకి కట్టుబడి ఉంటాను). అప్పుడు , , . ద్విపదలను గుణించడం ఇస్తుంది . ప్రస్తుతానికి మనకు ఇంకా ఉంది ఒకే అంకెల గుణకారం: , , , . ఇప్పుడు జోడించి తీసివేద్దాం . కొన్ని పునర్వ్యవస్థీకరణల తరువాత, నేను పాఠకుడికి వ్యాయామంగా వదిలివేస్తాను, అది మారుతుంది  - కేవలం మూడు ఒకే అంకెల గుణకారాలు! (కొన్ని స్థిరమైన గుణకాలు ఉన్నాయి, కానీ అవి అంకెలను జోడించడం మరియు మార్చడం ద్వారా మాత్రమే లెక్కించబడతాయి).

రుజువు అడగవద్దు, కానీ కరాట్సుబా అల్గోరిథం (పై ఉదాహరణ నుండి పునరావృతంగా సాధారణీకరించబడింది) సంప్రదాయ గుణకార పద్ధతిని మెరుగుపరుస్తుంది ముందు కార్యకలాపాలు . ఇది అల్గారిథమ్‌కి నిజమైన మెరుగుదల అని దయచేసి గమనించండి, మానసిక గణనల కోసం ఆప్టిమైజేషన్ కాదు. వాస్తవానికి, అల్గారిథమ్ మానసిక అంకగణితానికి తగినది కాదు, ఎందుకంటే పునరావృత కార్యకలాపాల కోసం దీనికి పెద్ద ఖర్చులు అవసరం. అదనంగా, సంఖ్యలు తగినంతగా పెరిగే వరకు ప్రభావం పూర్తిగా కనిపించదు (అదృష్టవశాత్తూ, కరాట్‌సుబా యొక్క అల్గోరిథం మరింత వేగవంతమైన పద్ధతుల ద్వారా భర్తీ చేయబడింది: మార్చి 2019లో, ఒక అల్గోరిథం ప్రచురించబడింది, దీనికి మాత్రమే అవసరం n లాగ్ n గుణకారాలు; త్వరణం ఊహించలేనంత పెద్ద సంఖ్యలకు మాత్రమే వర్తిస్తుంది).

ఈ అల్గోరిథం వాల్యూమ్ 295, సెమీ-న్యూమరికల్ అల్గారిథమ్స్ యొక్క XNUMXవ పేజీలో వివరించబడింది. అక్కడ నత్ ఇలా వ్రాశాడు: “ఈ ఆలోచన కేవలం లో మాత్రమే కనుగొనబడిందనేది ఆసక్తికరమైన విషయం 1962 సంవత్సరం," కరాట్‌సుబా యొక్క అల్గారిథమ్‌ను వివరించే కథనం ప్రచురించబడినప్పుడు. కానీ! 1995లో, కరాట్‌సుబా "కంప్యూటేషనల్ కాంప్లెక్సిటీ" అనే పేపర్‌ను ప్రచురించింది, ఇందులో అనేక విషయాలు ఉన్నాయి: 1) 1956లో, కోల్మోగోరోవ్ గుణకారం కంటే తక్కువ సమయంలో చేయలేమని సూచించాడు. దశలు; 2) లో 1960 సంవత్సరం కరట్సుబా సెమినార్‌కు హాజరయ్యాడు, అక్కడ కోల్మోగోరోవ్ తన పరికల్పన n²ను సమర్పించాడు. 3) "సరిగ్గా ఒక వారంలో," కరాట్సుబా "డివైడ్ అండ్ కాంక్వెర్" అల్గోరిథంను అభివృద్ధి చేసింది; 4) 1962లో కోల్మోగోరోవ్ ఒక కథనాన్ని వ్రాసి ప్రచురించాడు కరాట్సుబా తరపున అల్గోరిథం యొక్క వివరణతో. "ఈ కథనం తిరిగి ప్రచురించబడిన తర్వాత మాత్రమే నేను దాని గురించి తెలుసుకున్నాను."

కాబట్టి లోపం బదులుగా ఉంది 1962 తప్పనిసరిగా పేర్కొనాలి 1960 సంవత్సరం. అంతే.

Анализ

లోపాలను కనుగొనడంలో ప్రత్యేక నైపుణ్యం అవసరం లేదు.

1. మొదటి లోపం సాధ్యమైనంత చిన్నవిషయం మరియు సాపేక్షంగా కనిపించే ప్రదేశంలో ఉంది (అధ్యాయం ప్రారంభం). ఏ మూర్ఖుడైనా దాన్ని కనుగొని ఉండేవాడు; నేను ఆ ఇడియట్‌గా మారిపోయాను.
2. రెండవ అక్షర దోషాన్ని కనుగొనడానికి అదృష్టం మరియు శ్రద్ధ అవసరం, కానీ నైపుణ్యం కాదు. "విలియమ్స్" కోసం సూచిక వాల్యూమ్ యొక్క చివరి పేజీలో ఉంది, ఇది పుస్తకంలో చాలా ముఖ్యమైన భాగం. నేను ఇప్పుడే ఇండెక్స్‌ని తిప్పుతున్నాను (ఇది ధ్వనించేంత దయనీయంగా లేదు, ఎందుకంటే క్నూత్ యొక్క సూచికలలో ఈస్టర్ గుడ్లు దాగి ఉన్నాయి. ఉదాహరణకు, అరబిక్ మరియు హీబ్రూలో ఎంట్రీలు ఉన్నాయి, రెండూ పేజీ 66ని సూచిస్తాయి. కానీ ఆ పేజీ పేర్కొనలేదు ఏదైనా భాషలు; బదులుగా ఇది "కుడి నుండి ఎడమకు చదివే భాషలను" సూచిస్తుంది). మరియు రెండవ పేరు నా దృష్టిని ఆకర్షించింది. నేను సాధారణంగా వికీపీడియా చదివాను కాబట్టి, నేను రాబిన్ విలియమ్స్‌ని తనిఖీ చేసాను మరియు వ్యత్యాసాన్ని గమనించాను.
3. నేను చారిత్రక లోపాన్ని కనుగొనడానికి తీవ్రమైన పరిశోధన చేశానని చెప్పాలనుకుంటున్నాను, కానీ నిజంగా నేను చూశాను Karatsuba యొక్క అల్గోరిథం గురించి వికీపీడియా పేజీ. మొదటి పంక్తులు ఇలా చెబుతున్నాయి: “కరాట్సుబా అల్గోరిథం వేగవంతమైన గుణకార అల్గోరిథం. 1960లో అనటోలీ కరాట్సుబాచే కనుగొనబడింది మరియు 1962లో ప్రచురించబడింది." ఆ తర్వాత ఇద్దర్నీ, ఇద్దరినీ చేర్చడమే మిగిలింది.

భవిష్యత్తులో నేను మరింత ముఖ్యమైన బగ్‌ను కనుగొనాలనుకుంటున్నాను, ముఖ్యంగా క్నత్ కోడ్‌లో. నేను ఫండమెంటల్ అల్గారిథమ్‌ల మొదటి వాల్యూమ్‌లో బగ్‌ను కూడా కనుగొనాలనుకుంటున్నాను. బహుశా నేను దానిని కనుగొన్నాను, కానీ కొన్ని కారణాల వల్ల స్థానిక లైబ్రరీలో 2, 3 మరియు 4A వాల్యూమ్‌లు మాత్రమే ఉన్నాయి.

ఆర్థిక వాస్తవాలు:

• మొత్తంగా, TAOCPకి నా సహకారం మూడు అక్షరాలను మాత్రమే కలిగి ఉంటుంది: ఒక అదనంగా s, భర్తీ m న n и 2 న 0. $2,56 వద్ద, ఇవి కొన్ని అందమైన లాభదాయక చిహ్నాలు; మీకు ఆ రకమైన డబ్బు చెల్లించినట్లయితే, 1000 పదాల కథనం (సగటున నాలుగు అక్షరాలు) మీకు పది గ్రాండ్‌లను సంపాదిస్తుంది.
• మూడు హెక్సాడెసిమల్ డాలర్లతో, నేను, 29 మంది ఇతర పౌరులతో పాటు, శాన్ సెరిఫ్ బ్యాంక్ (మే 69, 1 నాటికి) అత్యంత ధనవంతులైన డిపాజిటర్ల జాబితాలో 2019వ స్థానంలో ఉన్నాం.

Knuth నుండి చెక్కుల గురించి ఇతర చర్చలు

• Knuth నుండి చెక్ ఎలా పొందాలి

  Knuth పుస్తకాలలో లోపాలను కనుగొనడానికి సాధారణ సిఫార్సులు. చాలా వరకు అవి సాంకేతిక లోపాలకు సంబంధించినవి, అవి నా దగ్గర లేవు. నేను తీవ్రంగా పరిగణించిన ఒక సూచన ఉంది:

  మీరు సమర్పించడానికి లోపాల సమితిని సేకరించే వరకు వేచి ఉండటం ఉత్తమం. అనేక నిజమైన కానీ చాలా విలువైన లోపాలను కలపడం ద్వారా, వాటిలో ఒకటి నిజంగా తప్పుగా లేదా సలహాగా పరిగణించబడే సంభావ్యతను మీరు పెంచుతారు. మీరు ఒక్కోసారి లోపాలను సమర్పిస్తే, ఒక్కొక్కటి ఒక్కొక్కటిగా తిరస్కరించబడవచ్చు.

  నేను కేవలం అర్ధంలేని అక్షరదోషాలు పంపకూడదనుకున్నాను, కానీ తగినంత తీవ్రమైనదిగా అనిపించిన చారిత్రక లోపం కనిపించినప్పుడు మాత్రమే సలహా తీసుకొని లేఖ పంపాను.

• అశుతోష్ మెహ్రా చెక్కులు

  BoSSలో 0x$207.f0 నికర విలువతో శాన్ సెరిఫ్‌లో అశుతోష్ మెహ్రా మూడవ అత్యంత ధనవంతుడు.

• నిజమైన TeX కోడ్‌లో కొన్ని నాన్-ఫంక్షనల్ బగ్‌ల కోసం తనిఖీ చేయండి
• ఇతరాలు: #1 #2 #3 #4 #5 #6

మూలం: www.habr.com