ડોનાલ્ડ નુથ એક કોમ્પ્યુટર વૈજ્ઞાનિક છે જેઓ તેમના પુસ્તકોની ચોકસાઈ વિશે ખૂબ કાળજી રાખે છે જે તેઓ સૂચવે છે એક હેક્સ ડોલર ($2,56, 0x$1,00) કોઈપણ "ભૂલ" માટે, જ્યાં ભૂલને "તકનીકી, ઐતિહાસિક, ટાઇપોગ્રાફિકલી અથવા રાજકીય રીતે ખોટી" તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. હું ખરેખર નુથ પાસેથી ચેક મેળવવા માંગતો હતો, તેથી મેં તેના મેગ્નમ ઓપસમાં ભૂલો શોધવાનું નક્કી કર્યું "પ્રોગ્રામિંગની કળા" (TAOCP). અમે ત્રણ શોધવામાં સફળ થયા. તેની વાત સાચી, નુટે ચેક મોકલ્યો 0x$3,00.

જેમ તમે જોઈ શકો છો, આ વાસ્તવિક ચેક નથી. નુથ વાસ્તવિક ચેક મોકલતો હતો, પરંતુ 2008 માં તેને કારણે બંધ થઈ ગયો પ્રચંડ છેતરપિંડી. તે હવે "થાપણના વ્યક્તિગત પ્રમાણપત્રો" મોકલે છે બેંક ઓફ સાન સેરિફ (BoSS). તે કહે છે કે જો જરૂરી હોય તો તે વાસ્તવિક નાણાં મોકલવા માટે તૈયાર છે, પરંતુ એવું લાગે છે કે તે ખૂબ જ મુશ્કેલી છે.

મને બે ટાઇપો અને એક ઐતિહાસિક ભૂલ મળી. હું તેમને તુચ્છતા ઘટાડવાના ક્રમમાં સૂચિબદ્ધ કરીશ.

ટાઈપો #1

પ્રથમ ટાઈપો "સૉર્ટિંગ એન્ડ સર્ચ" ના ત્રીજા ગ્રંથના પૃષ્ઠ 392 પર છે, નીચેથી આઠમી લાઇન: "અસફળ શોધ પછી, કેટલીકવાર (ક્યારેક) કોષ્ટકમાં નવો રેકોર્ડ દાખલ કરવો ઇચ્છનીય છે K; જે પદ્ધતિ આ કરે છે તેને શોધ અને દાખલ અલ્ગોરિધમ કહેવામાં આવે છે. ભૂલ એ છે કે તેના બદલે ક્યારેક હોવું જોઈએ ક્યારેક.

અલબત્ત, આવી ભૂલ આશ્ચર્યજનક નથી. એકલા આ લેખમાં થોડીક લખાણ ભૂલો હોઈ શકે છે (તેમને શોધવા માટે કોઈ પુરસ્કાર નથી). ખરેખર નવાઈની વાત એ છે કે આટલા લાંબા સમય સુધી તે કોઈનું ધ્યાન ગયું ન હતું. પૃષ્ઠ 392 ગણિત વિભાગમાં ઊંડે દફનાવવામાં આવ્યું નથી, તે છે ખૂબ જ પ્રથમ પૃષ્ઠ પ્રકરણ 6 "શોધ"! સંભવતઃ પુસ્તકના સૌથી વધુ વાંચેલા વિભાગોમાંનું એક. સૈદ્ધાંતિક રીતે, ત્યાં સૌથી ઓછી લખાણ ભૂલો હોવી જોઈએ, પરંતુ ના.

બાય ધ વે, જો તમે ક્યારેય TAOCP વાંચવાનું વિચાર્યું હોય, તો તેને અજમાવી જુઓ. ઘણા કહેશે કે આ છે ડિરેક્ટરી, સીધા વાંચન માટે બનાવાયેલ નથી, પરંતુ આ સાચું નથી. લેખક સ્પષ્ટ દૃષ્ટિકોણ અને વિશિષ્ટ શૈલી ધરાવે છે. એકમાત્ર વસ્તુ જે વાંચનક્ષમતાને અવરોધે છે તે ગણિતની જટિલતા છે. જો કે, ત્યાં એક સરળ ઉપાય છે: જ્યાં સુધી તમે ગણિતમાં ન આવો ત્યાં સુધી વાંચો, તમે સમજી શકતા નથી, તેને છોડી દો અને તમે સમજી શકો તે પછીના વિભાગ પર જાઓ. આ રીતે વાંચતા, હું ઓછામાં ઓછા 80% પુસ્તક ચૂકી ગયો, પરંતુ અન્ય 20% મહાન છે!

એવું પણ કહેવાય છે કે TAOCP અપ્રસ્તુત, જૂનું છે અથવા અન્યથા "વાસ્તવિક પ્રોગ્રામિંગ" પર લાગુ પડતું નથી. આ પણ સાચું નથી. ઉદાહરણ તરીકે, પરિચય પછીનો પહેલો વિભાગ ક્રમાંકિત એરેમાં તત્વ શોધવાનું જુએ છે. સરળ અલ્ગોરિધમ બધા પ્રોગ્રામરો માટે પરિચિત છે. એરેની શરૂઆતમાં પોઇન્ટર શરૂ કરો, પછી લૂપમાં નીચેના કરો:

1. વર્તમાન તત્વ ઇચ્છિત છે કે કેમ તે તપાસો. જો એમ હોય, તો અમે તેને પરત કરીએ છીએ; અન્યથા
2. તપાસો કે શું નિર્દેશક એરેની સીમાની બહાર છે. જો એમ હોય, તો ભૂલ પરત કરો; અન્યથા
3. ઝૂમ ઇન કરો અને ચાલુ રાખો.

હવે ધ્યાનમાં લો: આ અલ્ગોરિધમને સરેરાશ કેટલા બાઉન્ડ ચેકની જરૂર છે? સૌથી ખરાબ કિસ્સામાં, જ્યાં એરેમાં કોઈ તત્વ નથી હોતું, સૂચિમાંના દરેક ઘટકને એક ચેકની જરૂર પડશે, અને સરેરાશ તે કંઈક આના જેવું હશે . એક સ્માર્ટ શોધ અલ્ગોરિધમ માત્ર એક બાઉન્ડ ચેકથી દૂર થઈ શકે છે. એરેના અંતમાં ઇચ્છિત તત્વ જોડો, પછી એરેની શરૂઆતમાં પોઇન્ટર શરૂ કરો અને લૂપમાં નીચેના કરો:

1. વર્તમાન તત્વ ઇચ્છિત છે કે કેમ તે તપાસો. જો એમ હોય તો, જો પોઇન્ટર એરેની અંદર હોય તો અમે પ્રતિસાદ પરત કરીએ છીએ, અથવા જો તે ન હોય તો ભૂલ. અન્યથા
2. ઝૂમ ઇન કરો અને ચાલુ રાખો.

એક રીતે અથવા બીજી રીતે, તત્વ શોધવાની ખાતરી આપવામાં આવે છે, અને જ્યારે આવું થાય ત્યારે જ બાઉન્ડ્સ ચેક કરવામાં આવે છે. આ એક ઊંડો વિચાર છે, પરંતુ શિખાઉ પ્રોગ્રામર માટે પણ તે પૂરતું સરળ છે. હું કદાચ અન્ય લોકો સાથે કામની સુસંગતતા વિશે વાત કરી શકતો નથી, પરંતુ હું તરત જ વ્યક્તિગત અને વ્યાવસાયિક કોડ બંનેમાં આ શાણપણ લાગુ કરવામાં સક્ષમ હતો. TAOCP પુસ્તક આવા રત્નોથી ભરેલું છે (વાજબી રીતે, ત્યાં ઘણી વિચિત્ર વસ્તુઓ પણ છે, જેમ કે બબલ સૉર્ટ).

"શોધો, શોધો
ઘણુ લાંબુ
શોધો, શોધો
મારે ફક્ત ડાન્સ કરવો હતો"
- લ્યુથર વેન્ડ્રોસ, "ધ સર્ચ" (1980)

ટાઈપો #2

બીજી ટાઈપો વોલ્યુમ 4A, કોમ્બીનેટોરિયલ એલ્ગોરિધમ્સ, ભાગ 1 માં છે. પૃષ્ઠ 60 વિવિધ કેસિનોમાં પ્રદર્શન કરવા માટે હાસ્ય કલાકારોને સુનિશ્ચિત કરતી સમસ્યાનું વર્ણન કરે છે. કેટલાક વાસ્તવિક જીવનના હાસ્ય કલાકારોને ઉદાહરણો તરીકે ટાંકવામાં આવ્યા છે, જેમાં લિલી ટોમલિન, વિર્ડ અલ યાન્કોવિક અને રોબિન વિલિયમ્સનો સમાવેશ થાય છે, જેઓ પુસ્તક પ્રકાશિત થયું ત્યારે પણ જીવિત હતા. નુથ હંમેશા અનુક્રમણિકામાં સંપૂર્ણ નામોની યાદી આપે છે, તેથી વિલિયમ્સને પૃષ્ઠ 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. હું ઈચ્છું છું કે હું કહી શકું કે મેં ઐતિહાસિક ભૂલ શોધવા માટે ગંભીર સંશોધન કર્યું છે, પરંતુ ખરેખર મેં હમણાં જ જોયું કરાત્સુબાના અલ્ગોરિધમ વિશે વિકિપીડિયા પૃષ્ઠ. પ્રથમ પંક્તિઓ કહે છે: “કરાતસુબા અલ્ગોરિધમ એ ઝડપી ગુણાકાર અલ્ગોરિધમ છે. એનાટોલી કરાત્સુબા દ્વારા 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