Schönhage–Strassen algorithm
Schönhage-Strassen الگورتھم بڑے انٹیجرز کے لیے ایک غیر علامتی طور پر تیز ضرب الگورتھم ہے، جسے آرنلڈ Schönhage اور والکر Strassen نے 1971 میں شائع کیا تھا۔ یہ انٹیجرز ماڈیولو 2n + 1 پر تیز رفتار فورئیر ٹرانسفارم (ایف ایف ٹی) کو بار بار لاگو کرکے کام کرتا ہے۔ الگورتھم کا استعمال کرتے ہوئے دو ہندسوں کے نمبروں کو ضرب دینے کے لیے رن ٹائم بٹ کی پیچیدگی بڑے اشارے میں ہے۔ Schönhage-Strassen الگورتھم غیر علامتی طور پر تیز ترین ضرب کا طریقہ تھا جو 1971 سے 2007 تک جانا جاتا تھا۔ یہ کراتسوبا اور ٹوم کک ضرب جیسے پرانے طریقوں کے مقابلے میں غیر علامتی طور پر تیز ہے، اور عملی طور پر تقریبا 10,000 سے 100,000 اعشاریہ ہندسوں سے زیادہ تعداد کے لیے ان سے بہتر کارکردگی کا مظاہرہ کرنا شروع کر دیتا ہے۔ 2007 میں، مارٹن فیورر نے تیز تر ایسمپٹوٹک پیچیدگی کے ساتھ ایک الگورتھم شائع کیا۔ 2019 میں، ڈیوڈ ہاروی اور جورس وین ڈیر ہووین نے مظاہرہ کیا کہ کثیر ہندسوں کے ضرب میں نظریاتی پیچیدگی ہوتی ہے۔ تاہم، ان کے الگورتھم میں مستقل عوامل ہوتے ہیں جو اسے کسی بھی قابل فہم عملی مسئلے کے لیے ناممکن طور پر سست بناتے ہیں (دیکھیں کہکشاں الگورتھم)۔ Schönhage-Strassen الگورتھم کی ایپلی کیشنز میں ان کی اپنی خاطر کیے گئے بڑے حسابات شامل ہیں جیسے کہ گریٹ انٹرنیٹ مرسین پرائم سرچ اور اس کے تخمینے، نیز عملی ایپلی کیشنز جیسے کہ کرونکر متبادل کے ذریعے لینسٹرا ایلیپٹک وکر فیکٹرائزیشن، جو کثیر الجہتی ضرب کو انٹیجر ضرب میں کم کرتی ہے۔ تفصیل بیس B میں موجود ہر عدد کو کثیر الجہتی کے طور پر لکھا جا سکتا ہے: مزید برآں، دو اعداد کے ضرب کو دو کثیر الجہتی کے ضرب کے طور پر سمجھا جا سکتا ہے: کیونکہ، کے لیے:، ہمارے پاس ایک ارتقاء ہے۔ ایف ایف ٹی (فاسٹ فورئیر ٹرانسفارم) کا استعمال کرتے ہوئے، جو کہ کنولیوشن رول کے ساتھ این ٹی ٹی کے بجائے اصل ورژن میں استعمال ہوتا ہے ؛ ہمیں ملتا ہے۔ یعنی ؛، فورئیر اسپیس میں متعلقہ گتانک کہاں ہے۔ اسے اس طرح بھی لکھا جا سکتا ہے: fft (a * b) = fft (a) ● fft (b)۔ فورئیر ٹرانسفارم کے تحت لکیریٹی کی وجہ سے ہمارے پاس ایک جیسے کوفیشنٹس ہیں، اور کیونکہ یہ کثیر الجہتی صرف ایک منفرد اصطلاح فی کوفیشنٹ پر مشتمل ہیں: اور کنولیوشن رول: ہم نے ایف ایف ٹی کے ذریعے اپنے کنولیوشن کے مسئلے کو پروڈکٹ کے مسئلے تک کم کر دیا ہے۔ آئی ایف ایف ٹی (کثیر الجہتی انٹرپولیشن) تلاش کرنے سے، ہر ایک کے لیے مطلوبہ گتانک حاصل ہوتے ہیں۔ الگورتھم تقسیم اور فتح کی حکمت عملی کا استعمال کرتا ہے، تاکہ مسئلے کو ذیلی مسائل میں تقسیم کیا جا سکے۔ ماڈ این کے تحت ارتقاء، جہاں اور شونہیج-اسٹراسن الگورتھم میں۔ لیٹ کرنے سے: اور، n-th جڑ کہاں ہے ایک یہ دیکھتا ہے: اس کا مطلب ہے، کوئی وزن استعمال کر سکتا ہے، اور پھر بعد کے ساتھ ضرب کر سکتا ہے۔ وزن کا استعمال کرنے کے بجائے ؛ کوئی بھی، تکرار کے پہلے مرحلے میں (کب)، حساب لگا سکتا ہے: عام ایف ایف ٹی میں، جو پیچیدہ نمبروں پر چلتا ہے، کوئی استعمال کرے گا: تاہم، ایف ایف ٹی کو شونہیج-اسٹراسن میں این ٹی ٹی (نمبر تھیوریٹک ٹرانسفارمیشن) کے طور پر بھی استعمال کیا جا سکتا ہے۔ اس کا مطلب یہ ہے کہ ہمیں ایک محدود فیلڈ (مثال کے طور پر) میں اعداد پیدا کرنے والے کا استعمال کرنا ہوگا۔ ایک محدود میدان کے تحت اتحاد کی جڑ، ایک ایسا عنصر ہے جو یا۔ مثال کے طور پر، جہاں ایک پرائم ہے، دیتا ہے۔ اس پر اندر اور اندر توجہ دیں۔ ان کینڈیڈیٹس کے لیے، اس کے محدود میدان کے تحت، اور اس لیے جس طرح ہم چاہتے ہیں اس طرح کام کریں۔ وہی ایف ایف ٹی الگورتھم اب بھی استعمال کیے جا سکتے ہیں، حالانکہ، جب تک کہ کسی محدود فیلڈ کے اتحاد کی جڑ ہو۔ ایف ایف ٹی/این ٹی ٹی ٹرانسفارم تلاش کرنے کے لیے، ہم درج ذیل کام کرتے ہیں: پہلا پروڈکٹ ہر ایک کے لیے حصہ دیتا ہے۔ دوسرا حصہ، موڈ کی وجہ سے دیتا ہے۔ الٹا کرنے کے لیے: یا اس پر منحصر ہے کہ آیا fft کوئی نارملائز ڈیٹا استعمال کرتا ہے یا نہیں۔ ایف ایف ٹی ڈیٹا کو ایک مخصوص رینج میں معمول پر لانے کے لیے، جہاں موڈ، جہاں ماڈیولر ملٹی پلیکیٹو انورس کا استعمال کرتے ہوئے پایا جاتا ہے، اس سے ضرب دیں۔ نفاذ کی تفصیلات کیوں N = 2 + 1 ماڈ N میں Schönhage-Strassen الگورتھم میں۔ کسی کو اسے بائنری ٹری کے طور پر سوچنا چاہیے، جہاں کسی کی قدر ہوتی ہے۔ اجازت دے کر، ہر ایک کے لیے سب کچھ تلاش کیا جا سکتا ہے: کوئی بھی تمام جوڑوں کو M مختلف گروپوں میں گروپ کر سکتا ہے۔ ارتقاء کے ذریعے جوڑوں کو گروپ کرنے کا استعمال، الگورتھم میں ایک کلاسیکی مسئلہ ہے۔ مثال کے طور پر: فرض کریں کہ k کل آمدنی ہے اور یہ انسان کی آمدنی اور عورت کی آمدنی ہے۔ کنولیوشن کا استعمال کرتے ہوئے، مطلوبہ کل آمدنی کی بنیاد پر گروپوں میں تقسیم کیا جا سکتا ہے۔ اس بات کو ذہن میں رکھتے ہوئے، ذیلی کاموں کے ہر گروپ کے لیے گہرائی میں گروپ بنانے میں ہماری مدد کریں ؛ ٹری میں نوٹ کریں کہ، کچھ ایل کے لیے۔ یہ فرمیٹ نمبر ہے۔ موڈ کرتے وقت، ہمارے پاس کچھ ہوتا ہے جسے فرمیٹ رنگ کہتے ہیں۔ چونکہ کچھ فرمیٹ نمبرز فرمیٹ پرائمز ہوتے ہیں، اس لیے بعض صورتوں میں حساب سے بچا جا سکتا ہے۔ دیگر N ہیں جو استعمال کیے جا سکتے ہیں، یقینا، اسی پرائم نمبر کے فوائد کے ساتھ۔ اجازت دے کر، بائنری نمبر میں بٹس کے ساتھ زیادہ سے زیادہ نمبر حاصل کریں۔ ایک مرسین نمبر ہے، جو بعض صورتوں میں مرسین پرائم ہوتا ہے۔ یہ فرمیٹ نمبر کے خلاف ایک قدرتی امیدوار ہے دوسرے این کی تلاش میں مختلف کے خلاف کئی موڈ حساب کتاب کرنا، جب انٹیجر پروڈکٹ کو حل کرنے کی بات آتی ہے تو مددگار ثابت ہوسکتا ہے۔ چینی ریمائنڈر تھیوریم کا استعمال کرتے ہوئے، چھوٹی مختلف اقسام میں تقسیم ہونے کے بعد، ضرب کا جواب مل سکتا ہے۔ فرمیٹ نمبر اور مرسین نمبر صرف دو قسم کے نمبر ہیں، جسے عمومی فرمیٹ مرسین نمبر (جی ایس ایم) کہا جاتا ہے۔ فارمولے کے ساتھ: اس فارمولے میں ؛ ایک فرمیٹ نمبر ہے، اور یہ ایک مرسین نمبر ہے۔ اس فارمولے کو مساوات کے سیٹ تیار کرنے کے لیے استعمال کیا جا سکتا ہے، جسے سی آر ٹی (چینی بقیہ تھیوریم) میں استعمال کیا جا سکتا ہے:، جہاں ایک ایسا نمبر ہے جس میں ایک جگہ موجود ہے، یہ فرض کرتے ہوئے کہ ؛ مزید برآں، جہاں ایک عنصر ہے جو عناصر کو چکور انداز میں پیدا کرتا ہے۔ اگر، کہاں، پھر۔ کسی مخصوص این کے لیے کے کا انتخاب کیسے کریں کارکردگی کا حساب لگا کر بٹ سائز کو مناسب (بٹس کو تقسیم کرنے کے لیے گروپوں کی تعداد) تلاش کرنے میں مندرجہ ذیل فارمولے سے مدد ملتی ہے: بٹ سائز (جس میں استعمال ہوتا ہے) سب سے بیرونی سطح پر ہوتا ہے۔ بٹس کے گروپ دیتا ہے، جہاں۔ اس کے ذریعے اور اس کے ذریعے سب سے چھوٹا پایا جاتا ہے، جیسے کہ اگر کوئی 50 فیصد سے زیادہ کارکردگی کا فرض کرتا ہے، اور باقی فارمولوں کے مقابلے میں بہت چھوٹا ہے۔ اس کا مطلب یہ ہے کہ: جب کوئی چیز بہت موثر ہوتی ہے ؛ سڈوکوڈ کے ذریعے اوپر سے جڑی ہوئی ہوتی ہے یا اس سے اوپر سے جڑی ہوئی ہوتی ہے۔ مندرجہ ذیل الوگیتھم، معیاری ماڈیولر شونہیج-اسٹراسن ملٹیپلیکیشن الگورتھم (کچھ اصلاح کے ساتھ)، ٹی 3 ایم یو ایل = ٹوم-کک ضرب ایس ایم یو ایل = شونہیج-اسٹراسن ضرب تشخیص = ایف ایف ٹی/آئی ایف ایف ٹی کے ذریعے جائزہ میں پایا جاتا ہے۔ مزید مطالعہ محرک تفصیلات کے لیے، کوئی بھی کتاب پرائم نمبرز: اے کمپیوٹیشنل پرسپکٹو پڑھ سکتا ہے۔ یہ متغیر شونہیج کے اصل طریقہ سے کسی حد تک مختلف ہے کیونکہ یہ منفی چکور کنولیوشن کو زیادہ موثر طریقے سے انجام دینے کے لیے مجرد وزن والی تبدیلی کا استحصال کرتا ہے۔ تفصیلی معلومات کا ایک اور ذریعہ نوتھ کا دی آرٹ آف کمپیوٹر پروگرامنگ ہے۔ اصلاح یہ سیکشن بہت سی اہم عملی اصلاحات کی وضاحت کرتا ہے، جب Schönhage-Strassen کو لاگو کرتے ہیں۔ دوسرے ضرب الگورتھم کا استعمال، الگورتھم کے اندر، ایک مخصوص کٹ آف پوائنٹ کے نیچے، دوسرے ضرب الگورتھم کا استعمال کرنا زیادہ موثر ہے، جیسے کہ ٹوم کک ضرب۔ 2 چال کا مربع جڑ این ٹی ٹی (نمبر تھیوریٹک ٹرانسفارمیشن) اپراچ میں اقدار کا وزن کرتے وقت، خیال یہ ہے کہ محدود میدان میں ترتیب کے اتحاد کی جڑ کے طور پر استعمال کیا جائے (یہ مساوات کا حل ہے)۔ یہ انٹیجر ضرب کے وقت میں 10 فیصد بچانے کے لیے دکھایا گیا ہے۔ گرینلینڈ کی چال اجازت دے کر ؛ کوئی بھی اور کا حساب لگا سکتا ہے۔ سی آر ٹی (چینی ریمینڈر تھیوریم) کے ساتھ مل کر، ضرب کی صحیح اقدار تلاش کرنے کے لیے حوالہ جات کمپیوٹر ریاضی کے الگورتھم ضرب