ڈونلڈ ناتھ ایک کمپیوٹر سائنسدان ہے جو اپنی کتابوں کی درستگی کے بارے میں اتنا خیال رکھتا ہے کہ وہ تجویز کرتا ہے۔ ایک ہیکس ڈالر ($2,56, 0x$1,00) کسی بھی "خرابی" کے لیے، جہاں غلطی کی تعریف کسی بھی ایسی چیز کے طور پر کی جاتی ہے جو "تکنیکی، تاریخی، نوع نگاری، یا سیاسی طور پر غلط ہو۔" میں واقعتا Knuth سے چیک حاصل کرنا چاہتا تھا، اس لیے میں نے اس کے بڑے کام میں غلطیاں تلاش کرنے کا فیصلہ کیا۔ "پروگرامنگ کا فن" (TAOCP)۔ ہم تین کو ڈھونڈنے میں کامیاب ہو گئے۔ اپنے لفظ کے مطابق، نٹ نے ایک چیک بھیجا۔ 0x$3,00.

جیسا کہ آپ دیکھ سکتے ہیں، یہ ایک حقیقی چیک نہیں ہے۔ نتھ اصلی چیک بھیجتا تھا، لیکن 2008 میں اس کی وجہ سے روک دیا گیا۔ بڑے پیمانے پر دھوکہ دہی. اب وہ "ڈپازٹ کے ذاتی سرٹیفکیٹ" بھیجتا ہے۔ بینک آف سان سیرف (BoSS)۔ اس کا کہنا ہے کہ اگر ضروری ہو تو وہ حقیقی رقم بھیجنے کے لیے تیار ہے، لیکن ایسا لگتا ہے کہ یہ بہت زیادہ پریشانی ہے۔

مجھے دو ٹائپ کی غلطیاں اور ایک تاریخی غلطی ملی۔ میں ان کی فہرست میں کمی کو کم کرنے کی ترتیب میں دوں گا۔

ٹائپنگ نمبر 1

پہلی ٹائپو "چھانٹنا اور تلاش" کی تیسری جلد کے صفحہ 392 پر ہے، نیچے سے آٹھویں سطر: "ناکام تلاش کے بعد، بعض اوقات (کبھی کبھی) یہ ضروری ہوتا ہے کہ اس ٹیبل میں نیا ریکارڈ درج کیا جائے۔ K; جو طریقہ ایسا کرتا ہے اسے سرچ اینڈ انسرٹ الگورتھم کہتے ہیں۔ اس کے بجائے غلطی یہ ہے۔ کچھ دیر ہونا چاہئے کبھی کبھی.

بلاشبہ ایسی غلطی حیران کن نہیں ہے۔ صرف اس مضمون میں کچھ غلطیاں ضرور ہوں گی (ان کو تلاش کرنے پر کوئی انعام نہیں)۔ واقعی حیران کن بات یہ ہے کہ اس پر اتنے عرصے تک کسی کا دھیان نہیں گیا۔ صفحہ 392 ریاضی کے حصے میں گہرائی میں دفن نہیں ہے، یہ ہے۔ پہلا صفحہ باب 6 "تلاش"! ممکنہ طور پر کتاب کے سب سے زیادہ پڑھے جانے والے حصوں میں سے ایک۔ نظریہ میں، سب سے کم ٹائپ کی غلطیاں ہونی چاہئیں، لیکن نہیں۔

ویسے، اگر آپ نے کبھی TAOCP پڑھنے کے بارے میں سوچا ہے، تو اسے آزمائیں۔ بہت سے لوگ کہیں گے کہ یہ ہے۔ ڈائریکٹری، براہ راست پڑھنے کا ارادہ نہیں ہے، لیکن یہ سچ نہیں ہے۔ مصنف کا ایک واضح نقطہ نظر اور ایک مخصوص اسلوب ہے۔ صرف ایک چیز جو پڑھنے کی صلاحیت میں رکاوٹ ہے وہ ہے ریاضی کی پیچیدگی۔ تاہم، اس کا ایک آسان حل ہے: اس وقت تک پڑھیں جب تک کہ آپ ریاضی میں نہ آئیں جو آپ کو سمجھ نہیں آتا، اسے چھوڑ دیں، اور اگلے حصے پر جائیں جسے آپ سمجھ سکتے ہیں۔ اس طرح پڑھتے ہوئے، مجھے کم از کم 80% کتاب یاد آتی ہے، لیکن باقی 20% بہت اچھی ہے!

یہ بھی کہا جاتا ہے کہ TAOCP غیر متعلقہپرانا ہے یا بصورت دیگر "حقیقی پروگرامنگ" پر لاگو نہیں ہوتا ہے۔ یہ بھی درست نہیں ہے۔ مثال کے طور پر، تعارف کے بعد پہلا حصہ غیر ترتیب شدہ صف میں ایک عنصر کو تلاش کرنے پر غور کرتا ہے۔ سب سے آسان الگورتھم تمام پروگرامرز سے واقف ہے۔ صف کے شروع میں پوائنٹر شروع کریں، پھر لوپ میں درج ذیل کام کریں:

چیک کریں کہ آیا موجودہ عنصر مطلوبہ ہے۔ اگر ایسا ہے تو ہم اسے واپس کر دیتے ہیں۔ دوسری صورت میں
چیک کریں کہ آیا پوائنٹر صف کی حد سے باہر ہے۔ اگر ایسا ہے تو، ایک غلطی واپس کریں؛ دوسری صورت میں
زوم ان کریں اور جاری رکھیں۔

اب غور کریں: اس الگورتھم کو اوسطاً کتنے باؤنڈ چیک کی ضرورت ہوتی ہے؟ بدترین صورت میں، جہاں سرنی میں کوئی عنصر نہیں ہوتا ہے، فہرست میں موجود ہر عنصر کو ایک چیک کی ضرورت ہوگی، اور اوسطاً یہ کچھ ایسا ہوگا . ایک ہوشیار تلاش الگورتھم صرف ایک باؤنڈ چیک کے ساتھ دور ہو سکتا ہے۔ مطلوبہ عنصر کو صف کے آخر میں منسلک کریں، پھر صف کے شروع میں پوائنٹر شروع کریں اور لوپ میں درج ذیل کام کریں:

چیک کریں کہ آیا موجودہ عنصر مطلوبہ ہے۔ اگر ایسا ہے تو، ہم ایک جواب واپس کرتے ہیں اگر پوائنٹر صف کے اندر ہے، یا اگر یہ نہیں ہے تو ایک غلطی۔ ورنہ۔۔۔
زوم ان کریں اور جاری رکھیں۔

کسی نہ کسی طریقے سے، عنصر کے ملنے کی ضمانت دی جاتی ہے، اور جب ایسا ہوتا ہے تو باؤنڈ چیک صرف ایک بار کیا جاتا ہے۔ یہ ایک گہرا خیال ہے، لیکن یہ ایک نوسکھئیے پروگرامر کے لیے بھی کافی آسان ہے۔ میں شاید دوسروں سے کام کی مطابقت کے بارے میں بات نہیں کر سکتا، لیکن میں فوری طور پر اس حکمت کو ذاتی اور پیشہ ورانہ ضابطوں پر لاگو کرنے کے قابل ہو گیا۔ TAOCP کتاب ایسے جواہرات سے بھری ہوئی ہے (منصفانہ طور پر، وہاں بہت سی عجیب و غریب چیزیں بھی ہیں، جیسے بلبلے کی ترتیب).

"تلاش کرو، تلاش کرو
پھر ملیں گے
تلاش کریں، تلاش کریں۔
میں صرف ڈانس کرنا چاہتا تھا"
- لوتھر وینڈروس، "دی سرچ" (1980)

ٹائپنگ نمبر 2

دوسری ٹائپو والیم 4A، کمبینیٹریل الگورتھم، حصہ 1 میں ہے۔ صفحہ 60 مختلف کیسینو میں پرفارم کرنے کے لیے کامیڈین کو شیڈول کرنے میں شامل ایک مسئلے کی وضاحت کرتا ہے۔ کئی حقیقی زندگی کے مزاح نگاروں کو مثال کے طور پر پیش کیا جاتا ہے، جن میں للی ٹوملن، وئیرڈ ال ینکووِک، اور رابن ولیمز شامل ہیں، جو کتاب شائع ہونے کے وقت بھی زندہ تھے۔ Knuth ہمیشہ انڈیکس میں مکمل نام درج کرتا ہے، اس لیے ولیمز صفحہ 882 پر "ولیمز، رابن میکلورم" کے طور پر درج ہے۔ لیکن اس کا درمیانی نام "n" پر ختم ہوتا ہے نہ کہ "m"، یعنی McLaurin۔

میک لورین ان کی والدہ کا پہلا نام تھا۔ وہ مسیسیپی کے 34ویں گورنر اینسلم جوزف میک لارین کی نواسی تھیں۔ بظاہر اس کا دور حکومت کسی اچھی چیز کے لیے یاد نہیں تھا۔ کتاب سے "مسیسیپی: تاریخ":

"مکلورین انتظامیہ کے دوران سب سے اہم واقعہ 1898 کے موسم بہار میں امریکہ کا سپین کے خلاف اعلان جنگ تھا... بدقسمتی سے، جنگ نے کچھ سرکاری اہلکاروں کو رشوت خوری میں ملوث ہونے کا موقع فراہم کیا ہو گا۔ میک لورین پر مختلف قابل اعتراض طریقوں کا الزام لگایا گیا تھا، بشمول اقربا پروری اور معافی کے اختیارات کا ضرورت سے زیادہ استعمال۔ تحمل مزاجی کی تحریک کے دوران، ناقدین نے گورنر پر شرابی ہونے کا الزام لگایا، جس کا انہوں نے کھلے عام اعتراف کیا۔

تاریخی غلطی

غور کریں روایتی ضرب الگورتھم اسکول کے نصاب سے۔ اس کے لیے کتنے سنگل ہندسوں کی ضربیں درکار ہیں؟ فرض کریں کہ آپ ضرب لگاتے ہیں۔ - ہندسوں کا نمبر پر -بٹ . پہلے پہلے ہندسے کو ضرب دیں۔ ہر ہندسے کے لیے ایک ایک کر کے۔ پھر دوسرے ہندسے کو ضرب دیں۔ ہر ہندسے کے لیے ایک ایک کرکے اور اسی طرح جب تک آپ تمام نمبروں کو نہیں دیکھتے . اس طرح روایتی ضرب کی ضرورت ہے۔ ابتدائی ضربیں خاص طور پر، دو نمبروں کو بذریعہ ضرب درجات کی ضرورت ہے واحد ہندسے کی ضربیں

یہ بری بات ہے، لیکن سوویت ریاضی دان اناتولی الیکسیویچ کراٹسوبا کے تیار کردہ طریقہ کار کو استعمال کرتے ہوئے اس عمل کو بہتر بنانا ممکن ہے۔ آئیے اس کا بہانہ کریں۔ и - دو ہندسوں کے اعشاریہ نمبر؛ یعنی نمبرز ہیں۔ , , , اس طرح کہ и (اس الگورتھم کو بڑی تعداد میں عام کرنے کے لیے کچھ ہیرا پھیری کی ضرورت ہوتی ہے؛ اگرچہ یہ زیادہ مشکل نہیں ہے، تاکہ تفصیلات میں غلطیاں نہ ہوں، میں ایک سادہ سی مثال پر قائم رہوں گا)۔ پھر , , . binomials کو ضرب دینے سے ملتا ہے۔ . اس وقت ہمارے پاس موجود ہے۔ واحد ہندسہ ضرب: , , , . اب شامل کریں اور گھٹائیں . کچھ دوبارہ ترتیب دینے کے بعد، جسے میں قارئین کے لیے ایک مشق کے طور پر چھوڑ دوں گا، یہ نکلا۔ - صرف تین واحد ہندسوں کی ضربیں! (کچھ مستقل گتانک ہیں، لیکن ان کا حساب صرف ہندسوں کو جوڑ کر اور شفٹ کر کے لگایا جا سکتا ہے)۔

ثبوت مت مانگو مگر۔۔۔ کراتسوبا الگورتھم (اوپر کی مثال سے بار بار عام کیا گیا) کے ساتھ روایتی ضرب کے طریقہ پر بہتر ہوتا ہے۔ آپریشن سے پہلے . براہ کرم نوٹ کریں کہ یہ الگورتھم میں حقیقی بہتری ہے، ذہنی حسابات کے لیے اصلاح نہیں۔ درحقیقت، الگورتھم ذہنی ریاضی کے لیے موزوں نہیں ہے، کیوں کہ اسے دوبارہ چلنے والی کارروائیوں کے لیے بڑے اخراجات کی ضرورت ہوتی ہے۔ اس کے علاوہ، اثر اس وقت تک خود کو مکمل طور پر ظاہر نہیں کرے گا جب تک کہ تعداد کافی زیادہ نہ ہو جائے (خوش قسمتی سے، Karatsuba کے الگورتھم کو اس سے بھی تیز تر طریقوں سے بدل دیا گیا ہے: مارچ 2019 میں، ایک الگورتھم شائع کیا گیا تھا جس کے لیے صرف n لاگ n ضرب سرعت صرف ناقابل تصور بڑی تعداد پر لاگو ہوتی ہے)۔

یہ الگورتھم جلد 295، نیم عددی الگورتھم کے صفحہ XNUMX پر بیان کیا گیا ہے۔ وہاں Knuth لکھتے ہیں: "یہ دلچسپ ہے کہ یہ خیال صرف میں دریافت کیا گیا تھا 1962 سال، جب کراتسوبا کے الگورتھم کو بیان کرنے والا ایک مضمون شائع ہوا تھا۔ لیکن! 1995 میں، Karatsuba نے ایک مقالہ "Computational Complexity" شائع کیا، جس میں کئی باتیں بتائی گئی ہیں: 1) 1956 کے آس پاس، کولموگوروف نے تجویز کیا کہ ضرب اس سے کم میں نہیں کی جا سکتی۔ قدم 2) میں 1960 سال کاراتسوبا نے اس سیمینار میں شرکت کی جہاں کولموگوروف نے اپنا مفروضہ n² پیش کیا۔ 3) "بالکل ایک ہفتے میں،" کراتسوبا نے "تقسیم کرو اور فتح کرو" الگورتھم تیار کیا۔ 4) 1962 میں کولموگوروف نے ایک مضمون لکھا اور شائع کیا۔ کراتسوبا کی جانب سے الگورتھم کی وضاحت کے ساتھ۔ "مجھے اس مضمون کے دوبارہ شائع ہونے کے بعد ہی پتہ چلا۔"

تو غلطی یہ ہے کہ بجائے 1962 وضاحت کرنا ضروری ہے 1960 سال بس۔

تجزیہ

غلطیاں تلاش کرنے کے لیے خاص مہارت کی ضرورت نہیں تھی۔

پہلی غلطی ممکنہ حد تک معمولی تھی اور نسبتاً نظر آنے والی جگہ پر تھی (باب کا آغاز)۔ کوئی بیوقوف اسے مل جاتا۔ میں صرف وہ بیوقوف نکلا۔
دوسری ٹائپو تلاش کرنے کے لیے قسمت اور تندہی کی ضرورت ہے، لیکن مہارت نہیں۔ "ولیمز" کا اشاریہ جلد کے آخری صفحہ پر ہے، جو کتاب کا کافی نمایاں حصہ ہے۔ میں صرف انڈیکس کو پلٹ رہا تھا (یہ اتنا قابل رحم نہیں ہے جتنا یہ لگتا ہے، کیونکہ نتھ کے انڈیکس میں ایسٹر کے انڈے چھپے ہوئے ہیں۔ مثال کے طور پر، عربی اور عبرانی میں اندراجات ہیں، دونوں صفحہ 66 کی طرف اشارہ کرتے ہیں۔ لیکن اس صفحہ کا ذکر نہیں ہے۔ یا تو زبانیں؛ اس کے بجائے اس سے مراد "زبانیں جو دائیں سے بائیں پڑھی جاتی ہیں")۔ اور دوسرے نام نے میری توجہ مبذول کر لی۔ چونکہ میں عام طور پر ویکیپیڈیا پڑھتا ہوں، اس لیے میں نے رابن ولیمز کو چیک کیا اور ایک تضاد دیکھا۔
کاش میں کہہ سکتا کہ میں نے تاریخی غلطی تلاش کرنے کے لیے سنجیدہ تحقیق کی ہے، لیکن واقعی میں نے صرف دیکھا Karatsuba کے الگورتھم کے بارے میں ویکیپیڈیا کا صفحہ. پہلی ہی سطریں کہتی ہیں: "کراتسوبا الگورتھم ایک تیز ضرب الگورتھم ہے۔ 1960 میں Anatoly Karatsuba نے دریافت کیا اور 1962 میں شائع کیا۔" اس کے بعد صرف دو اور دو کا اضافہ کرنا رہ گیا تھا۔

مستقبل میں میں ایک اور اہم بگ تلاش کرنا چاہوں گا، خاص طور پر نتھ کے کوڈ میں۔ میں بنیادی الگورتھم کی پہلی جلد میں بھی ایک بگ تلاش کرنا چاہوں گا۔ شاید مجھے یہ مل جاتا، لیکن کسی وجہ سے مقامی لائبریری میں صرف جلدیں 2، 3 اور 4A ہیں۔

مالی حقائق:

مجموعی طور پر، TAOCP میں میری شراکت صرف تین حروف پر مشتمل ہے: ایک اضافہ s، متبادل m پر n и 2 پر 0. $2,56 پر، یہ کچھ خوبصورت نفع بخش علامتیں ہیں۔ اگر آپ کو اس قسم کی رقم ادا کی جاتی ہے، تو 1000 الفاظ کا ایک مضمون (اوسطاً چار حروف) آپ کو دس گرانڈ کمائے گا۔
تین ہیکسا ڈیسیمل ڈالرز کے ساتھ، میں، 29 دیگر شہریوں کے ساتھ، سان سیرف بینک کے امیر ترین ڈپازٹرز کی فہرست میں 69ویں نمبر پر ہوں (1 مئی 2019 تک)۔

Knuth سے چیک کے بارے میں دیگر بات چیت

Knuth سے چیک کیسے حاصل کریں۔
نتھ کی کتابوں میں غلطیاں تلاش کرنے کے لیے عمومی سفارشات۔ زیادہ تر وہ تکنیکی خرابیوں کی فکر کرتے ہیں، جو میرے پاس نہیں ہے۔ وہاں ایک تجویز ہے جسے میں نے سنجیدگی سے لیا:
اس وقت تک انتظار کرنا بہتر ہے جب تک کہ آپ جمع کرانے کے لیے غلطیوں کا ایک سیٹ جمع نہ کر لیں۔ کئی حقیقی لیکن بہت قیمتی غلطیوں کو یکجا کرکے، آپ اس امکان کو بڑھاتے ہیں کہ ان میں سے کسی ایک کو دراصل غلطی یا مشورہ سمجھا جائے گا۔ اگر آپ ایک وقت میں ایک غلطیاں جمع کراتے ہیں، تو ہر ایک کو انفرادی طور پر مسترد کیا جا سکتا ہے۔
میں صرف بکواس کی غلطیاں نہیں بھیجنا چاہتا تھا، لیکن مشورہ لیا اور صرف اس وقت خط بھیجا جب مجھے ایک تاریخی غلطی ملی جو کافی سنگین معلوم ہوتی تھی۔
آشوتوش مہرا کا چیک
آشوتوش مہرا BoSS میں 0x$207.f0 کی مجموعی مالیت کے ساتھ San Serriff میں تیسرے امیر ترین سرمایہ کار ہیں۔
اصلی TeX کوڈ میں کچھ غیر فعال کیڑے چیک کریں۔
متفرق: #1 #2 #3 #4 #5 #6