Sobol sequence
سوبول کے ترتیبات (جسے ایل پی ٹی او ترتیبات یا بیس 2 میں (ٹی، ایس) ترتیبات بھی کہا جاتا ہے) نیم بے ترتیب کم تفریق کے ترتیبات کی ایک مثال ہیں۔ انہیں سب سے پہلے 1967 میں روسی ریاضی دان الیا ایم سوبول نے متعارف کرایا تھا۔ یہ ترتیبات یونٹ کے وقفے کی یکے بعد دیگرے باریک یکساں پارٹیشنز بنانے کے لیے دو کی بنیاد کا استعمال کرتے ہیں اور پھر ہر جہت میں نقاط کو دوبارہ ترتیب دیتے ہیں۔ ایس-جہتی اکائی ہائپر کیوب میں اچھی تقسیم آئی ایس = [0,1] ایس-جہتی اکائی ہائپر کیوب ہے، اور ایف آئی ایس پر ایک حقیقی انٹیگریبل فنکشن ہے۔ سوبول 'کا اصل محرک اس میں ایک ترتیب xn کی تعمیر کرنا تھا تاکہ کنورجنس جتنی جلدی ممکن ہو سکے۔ یہ کم و بیش واضح ہے کہ رقم کے انٹیگرل کی طرف یکجا ہونے کے لیے، پوائنٹس xn کو بھرنا چاہیے سوراخوں کو کم کرنا ہے۔ ایک اور اچھی خاصیت یہ ہوگی کہ اس کے نچلے جہتی چہرے پر xn کے تخمینے بھی بہت کم سوراخ چھوڑتے ہیں۔ لہذا Is کا یکساں بھرنا اہل نہیں ہے کیونکہ نچلے طول و عرض میں بہت سے پوائنٹس ایک ہی جگہ پر ہوں گے، لہذا انٹیگرل تخمینے کے لیے بیکار ہے۔ ان اچھی تقسیموں کو بیس b میں (t، m، s)-نیٹ اور (t، s)-سیکوینسز کہا جاتا ہے۔ انہیں متعارف کرانے کے لیے، پہلے بیس b میں ایک ابتدائی s-وقفے کی وضاحت کریں جو کہ Is کے ذیلی سیٹ کی شکل ہے جہاں aj اور dj غیر منفی عدد ہیں، اور {1,., s} میں تمام j کے لیے۔ 2 انٹیجرز کو دیکھتے ہوئے، بیس b میں a (t، m، s)-نیٹ bm پوائنٹس کی ایک ترتیب xn ہے جو کہ ہائپر والیوم λ (P) = bt−m کے بیس b میں تمام ابتدائی وقفہ P کے لیے ہے۔ ایک غیر منفی عدد t کو دیکھتے ہوئے، بیس b میں a (t، s)-تسلسل پوائنٹس xn کی ایک لامحدود ترتیب ہے جیسے کہ تمام انٹیجرز کے لیے، ترتیب بیس b میں a (t، m، s)-نیٹ ہے۔ اپنے مضمون میں، سوبول نے Πτ-meshes اور LPτ ترتیبات کو بیان کیا، جو بالترتیب بیس 2 میں (t، m، s)-nets اور (t، s)-ترتیبات ہیں۔ بیس بی (جسے نیڈریٹر سیکوینس بھی کہا جاتا ہے) میں اصطلاحات (ٹی، ایم، ایس)-نیٹ اور (ٹی، ایس)-سیکوینس 1988 میں ہیرالڈ نیڈریٹر نے تیار کیے تھے۔ 'سوبول' ترتیب کی اصطلاح انگریزی بولنے والے آخری اخبارات میں ہالٹن، فیور اور دیگر کم تفرقہ کے ترتیب کے مقابلے میں متعارف کرائی گئی تھی۔ ایک تیز الگورتھم ایک زیادہ موثر گرے کوڈ کے نفاذ کی تجویز انتونوف اور سلیف نے پیش کی تھی۔ جہاں تک سوبول نمبروں کی نسل کا تعلق ہے، انہیں واضح طور پر n-th پوائنٹ ڈرا کی تعمیر کے لیے n کے بجائے گرے کوڈ کے استعمال سے مدد ملتی ہے۔ فرض کریں کہ ہم نے پہلے ہی تمام سوبول کی ترتیب n−1 تک تیار کر لی ہے اور تمام مطلوبہ جہتوں کے لیے xn−1, j اقدار کو میموری میں رکھا ہے۔ چونکہ گرے کوڈ G (n) سابقہ G (n−1) سے صرف ایک سے مختلف ہے، جیسے کہ k-th، بٹ (جو کہ n−1 کا سب سے دائیں طرف کا صفر بٹ ہے)، اس لیے جو کچھ کرنے کی ضرورت ہے وہ ہر جہت کے لیے ایک واحد XOR آپریشن ہے تاکہ تمام xn−1 کو xn تک پھیلایا جا سکے، یعنی۔ اضافی یکسانیت کی خصوصیات سوبول نے اضافی یکسانیت کے حالات متعارف کروائے جنہیں پراپرٹی اے اور اے کے نام سے جانا جاتا ہے۔ تعریف ایک کم تفریق کی ترتیب کو پراپرٹی اے کو مطمئن کرنے کے لیے کہا جاتا ہے اگر لمبائی 2 ڈی کی ڈی جہتی ترتیب کے کسی بھی بائنری حصے (من مانی ذیلی سیٹ نہیں) کے لیے ہر 2 ڈی ہائپر کیوب میں بالکل ایک ڈرا ہوتا ہے جس کا نتیجہ یونٹ ہائپر کیوب کو اس کی ہر لمبائی کی توسیع کے ساتھ نصف میں تقسیم کرنے کے نتیجے میں ہوتا ہے۔ تعریف ایک کم تفریق کی ترتیب کو پراپرٹی اے کو مطمئن کرنے کے لیے کہا جاتا ہے اگر لمبائی 4 ڈی کی ڈی جہتی ترتیب کے کسی بھی بائنری حصے (کوئی من مانی ذیلی سیٹ نہیں) کے لیے ہر 4 ڈی ہائپر کیوب میں بالکل ایک ڈرا ہوتا ہے جس کا نتیجہ یونٹ ہائپر کیوب کو اس کی ہر لمبائی کی توسیع کے ساتھ چار مساوی حصوں میں تقسیم کرنے کے نتیجے میں ہوتا ہے۔ ایسے ریاضیاتی حالات ہیں جو خصوصیات A اور A 'کی ضمانت دیتے ہیں۔ نظریہ ڈی جہتی سوبول 'ترتیب میں خاصیت اے آئی ایف ایف ہوتی ہے جہاں وی ڈی ڈی × ڈی بائنری میٹرکس ہے جس کی تعریف وی کے، جے، ایم کے ساتھ کی گئی ہے جو سمت نمبر وی کے، جے = (0. وی کے، جے، 1 وی کے، جے، 2.) 2 کے بائنری پوائنٹ کے بعد ایم-ویں ہندسے کی نشاندہی کرتا ہے۔ نظریہ ڈی جہتی سوبول 'ترتیب میں خاصیت اے' آئی ایف ایف ہوتی ہے جہاں اڈ 2 ڈی × 2 ڈی بائنری میٹرکس ہے جس کی تعریف وی کے، جے، ایم کے ساتھ کی گئی ہے جو سمت نمبر وی کے، جے = (0. وی کے، جے، 1 وی کے، جے، 2) 2 کے بائنری پوائنٹ کے بعد ایم-ویں ہندسے کی نشاندہی کرتا ہے۔ خصوصیات A اور A 'کے لیے ٹیسٹ آزاد ہیں۔ اس طرح سوبول کی ترتیب کی تعمیر ممکن ہے جو A اور A دونوں خصوصیات کو مطمئن کرے یا ان میں سے صرف ایک کو۔ سوبول 'نمبروں کی ابتدا سوبول' ترتیب کی تعمیر کے لیے، سمت نمبروں کے ایک سیٹ vi، j کو منتخب کرنے کی ضرورت ہے۔ ابتدائی سمت کے اعداد کے انتخاب میں کچھ آزادی ہے۔ لہذا، منتخب جہتوں کے لیے سوبول ترتیب کے مختلف احساسات حاصل کرنا ممکن ہے۔ ابتدائی اعداد کا ناقص انتخاب جب حساب کے لیے استعمال کیا جائے تو سوبول کے ترتیبات کی کارکردگی کو کافی حد تک کم کر سکتا ہے۔ بلاشبہ ابتدائی اعداد کے لیے سب سے آسان انتخاب یہ ہے کہ صرف ایل-واں بائیں طرف کا بٹ سیٹ ہو، اور دیگر تمام بٹس صفر ہوں، یعنی۔ mk، j = 1 تمام k اور j کے لیے۔ اس شروعات کو عام طور پر یونٹ شروعات کہا جاتا ہے۔ تاہم، اس طرح کی ترتیب پراپرٹی اے اور اے کے لیے ٹیسٹ میں ناکام ہو جاتی ہے یہاں تک کہ کم طول و عرض کے لیے بھی اور اس لیے یہ شروعات خراب ہے۔ نفاذ اور دستیابی مختلف جہتوں کے لیے اچھے ابتدائی نمبر کئی مصنفین فراہم کرتے ہیں۔ مثال کے طور پر، سوبول '51 تک کے طول و عرض کے لیے ابتدائی نمبر فراہم کرتا ہے۔ ابتدائی اعداد کا ایک ہی سیٹ بریٹلی اور فاکس استعمال کرتے ہیں۔ اعلی طول و عرض کے لیے ابتدائی نمبر جو اور کوو پر دستیاب ہیں۔ پیٹر جیکل اپنی کتاب "مونٹی کارلو میتھڈز ان فنانس" میں طول و عرض 32 تک کے ابتدائی نمبر فراہم کرتے ہیں۔ دیگر نفاذ سافٹ ویئر کے عددی ترکیبوں کے مجموعے میں سی، فورٹرن 77، یا فورٹرن 90 معمولات کے طور پر دستیاب ہیں۔ جو اور کوو ابتدائی نمبروں پر مبنی 1111 طول و عرض تک کا ایک مفت/اوپن سورس نفاذ، سی میں دستیاب ہے، اور پائیتھن اور جولیا میں 21201 طول و عرض تک۔ سی + +، فورٹرن 90، میٹ لیب، اور ازگر کے لیے 1111 طول و عرض تک کا ایک مختلف مفت/اوپن سورس نفاذ دستیاب ہے۔ آخر میں، تجارتی سوبول 'سیکوینس جنریٹر دستیاب ہیں، مثال کے طور پر، این اے جی لائبریری۔ ایک ورژن برٹش-روسی آف شور ڈویلپمنٹ ایجنسی (BRODA) سے دستیاب ہے۔ ایم اے ٹی ایل اے بی میں اس کے شماریاتی ٹول باکس کے حصے کے طور پر ایک نفاذ بھی شامل ہے۔ یہ بھی دیکھیں کہ کم تفریق کے سلسلے نیم مونٹے کارلو طریقہ نوٹ حوالہ جات بیرونی لنکس ACM کے جمع کردہ الگورتھم (الگورتھم 647، 659، اور 738 دیکھیں۔) سوبول 'سیکوینس جنریٹر پروگرامنگ کوڈز کا مجموعہ فری ویئر سی + + جنریٹر آف سوبول' سیکوینس کم تفریق سیکوینس سیکوینس اور سیریز