Schönhage–Strassen algorithm
স্কনহেজ-স্ট্রাসেন অ্যালগরিদম হল বড় পূর্ণসংখ্যার জন্য একটি অ্যাসিম্পটোটিক্যালি দ্রুত গুণন অ্যালগরিদম, যা 1971 সালে আর্নল্ড স্কনহেজ এবং ভলকার স্ট্রাসেন দ্বারা প্রকাশিত হয়েছিল। এটি পূর্ণসংখ্যা মডুলো 2n + 1-এর উপর দ্রুত ফুরিয়ার রূপান্তর (এফ. এফ. টি) পুনরাবৃত্তভাবে প্রয়োগ করে কাজ করে। অ্যালগরিদম ব্যবহার করে দুই অঙ্কের সংখ্যাকে গুণ করার জন্য রান-টাইম বিট জটিলতা বড় স্বরলিপিতে রয়েছে। Schönhage-Strassen অ্যালগরিদম 1971 থেকে 2007 সাল পর্যন্ত পরিচিত অ্যাসিম্পটোটিকভাবে দ্রুততম গুণন পদ্ধতি ছিল। এটি কারাটসুবা এবং টুম-কুক গুণনের মতো পুরানো পদ্ধতির তুলনায় অ্যাসিম্পটোটিকভাবে দ্রুত এবং প্রায় 10,000 থেকে 100,000 দশমিক সংখ্যার বাইরে সংখ্যার জন্য অনুশীলনে তাদের ছাড়িয়ে যেতে শুরু করে। 2007 সালে, মার্টিন ফুরার দ্রুত অ্যাসিম্পটোটিক জটিলতা সহ একটি অ্যালগরিদম প্রকাশ করেন। 2019 সালে, ডেভিড হার্ভে এবং জোরিস ভ্যান ডার হোভেন প্রদর্শন করেছিলেন যে বহু-অঙ্কের গুণনের তাত্ত্বিক জটিলতা রয়েছে; তবে, তাদের অ্যালগরিদমের ধ্রুবক কারণ রয়েছে যা এটিকে যে কোনও কল্পনাযোগ্য ব্যবহারিক সমস্যার জন্য অসম্ভবভাবে ধীর করে তোলে (গ্যালাকটিক অ্যালগরিদম দেখুন)। Schönhage-Strassen অ্যালগরিদমের প্রয়োগগুলির মধ্যে রয়েছে তাদের নিজস্ব স্বার্থে করা বড় গণনা যেমন গ্রেট ইন্টারনেট মার্সেন প্রাইম সার্চ এবং এর আনুমানিক, পাশাপাশি ক্রোনেকার প্রতিস্থাপনের মাধ্যমে লেনস্ট্রা উপবৃত্তাকার বক্ররেখা ফ্যাক্টরাইজেশনের মতো ব্যবহারিক প্রয়োগ, যা বহুপদী গুণকে পূর্ণসংখ্যা গুণনে হ্রাস করে। বি-এর ভিত্তির প্রতিটি সংখ্যাকে বহুপদী হিসাবে লেখা যেতে পারেঃ উপরন্তু, দুটি সংখ্যার গুণনকে দুটি বহুপদীর গুণফল হিসাবে বিবেচনা করা যেতে পারেঃ কারণ, এর জন্যঃ, আমাদের একটি কনভোলিউশন রয়েছে। এফ. এফ. টি (ফাস্ট ফুরিয়ার ট্রান্সফর্ম) ব্যবহার করে, যা এন. টি. টি-র পরিবর্তে মূল সংস্করণে ব্যবহৃত হয়, কনভোলিউশন নিয়ম সহ; আমরা পাই। অর্থাৎ;, ফুরিয়ার স্পেসে সংশ্লিষ্ট সহগ কোথায়। এটিকে এইভাবেও লেখা যেতে পারেঃ fft (a * b) = fft (a) ● fft (b)। ফুরিয়ার রূপান্তরের অধীনে রৈখিকতার কারণে আমাদের একই সহগ রয়েছে এবং কারণ এই বহুপদগুলি প্রতি সহগ প্রতি শুধুমাত্র একটি অনন্য শব্দ নিয়ে গঠিতঃ এবং কনভোলিউশন নিয়মঃ আমরা এফ. এফ. টি-র মাধ্যমে আমাদের কনভোলিউশন সমস্যাকে পণ্য সমস্যায় পরিণত করেছি। আই. এফ. এফ. টি (পলিনোমিয়াল ইন্টারপোলেশন) খুঁজে বের করলে, প্রত্যেকটির জন্য কাঙ্ক্ষিত সহগ পাওয়া যায়। অ্যালগরিদম সমস্যাকে উপ-সমস্যায় ভাগ করার জন্য বিভাজন এবং জয় কৌশল ব্যবহার করে। মোড এন-এর অধীনে কনভোলিউশন, যেখানে এবং স্কোনহাজ-স্ট্রাসেন অ্যালগরিদমে। n-তম মূলটি কোথায় দেখতে পাবেঃ এবং। অর্থাৎ, কেউ ওজন ব্যবহার করতে পারে, এবং তারপর পরে দিয়ে গুণ করতে পারে। ওজন ব্যবহার করার পরিবর্তে; পুনরাবৃত্তির প্রথম ধাপে (কখন), গণনা করা যেতে পারেঃ সাধারণ এফ. এফ. টি-তে, যা জটিল সংখ্যার উপর কাজ করে, কেউ ব্যবহার করবেঃ তবে, এফ. এফ. টি-কে স্কনহেজ-স্ট্রাসেনে এন. টি. টি (সংখ্যা তাত্ত্বিক রূপান্তর) হিসাবেও ব্যবহার করা যেতে পারে। এর মানে হল যে আমাদের একটি সীমাবদ্ধ ক্ষেত্রে (উদাহরণস্বরূপ) সংখ্যা তৈরি করতে হবে। একটি সীমাবদ্ধ ক্ষেত্রের অধীনে ঐক্যের মূল হল এমন একটি উপাদান যা বা। উদাহরণস্বরূপ, যেখানে একটি মৌলিক সংখ্যা, দেয়। এটি ভিতরে এবং ভিতরে লক্ষ্য করুন। এই ক্যান্ডিয়াডেটগুলির জন্য, তার সীমাবদ্ধ ক্ষেত্রের অধীনে, এবং তাই আমরা যেভাবে চাই সেভাবে কাজ করুন। একই এফ. এফ. টি অ্যালগরিদম এখনও ব্যবহার করা যেতে পারে, যদিও, যতক্ষণ না একটি সীমাবদ্ধ ক্ষেত্রের ঐক্যের মূল থাকে। এফ. এফ. টি/এন. টি. টি রূপান্তর খুঁজে বের করার জন্য, আমরা নিম্নলিখিতগুলি করিঃ প্রথম পণ্যটি প্রত্যেকটির জন্য অবদান দেয়। দ্বিতীয়টি মোডের কারণে অবদান দেয়। বিপরীতটি করার জন্যঃ অথবা এফ. এফ. টি ব্যবহার করলে ডেটা স্বাভাবিক করা যায় কি না তার উপর নির্ভর করে। এফ. এফ. টি তথ্যকে একটি নির্দিষ্ট পরিসরে স্বাভাবিক করার জন্য একটিকে গুণ করুন, যেখানে মড, যেখানে মডুলার মাল্টিপ্লিকেটিভ ইনভার্স ব্যবহার করা হয়। বাস্তবায়নের বিশদ বিবরণ কেন এন = 2 + 1 মড এন-এ স্কনহেজ-স্ট্রাসেন অ্যালগরিদম-এ। এটিকে একটি বাইনারি ট্রি হিসাবে ভাবা উচিত, যেখানে একজনের মান রয়েছে। অনুমতি দিয়ে, প্রত্যেকের জন্য একজন সব খুঁজে পেতে পারেঃ একজন সমস্ত জোড়াকে এম বিভিন্ন গ্রুপে গোষ্ঠীভুক্ত করতে পারে। কনভোলিউশনের মাধ্যমে জোড়াগুলিকে গোষ্ঠীভুক্ত করা, অ্যালগরিদমের একটি ধ্রুপদী সমস্যা। উদাহরণস্বরূপঃ ধরা যাক মোট আয় এবং পুরুষের আয় এবং মহিলার আয়; কনভোলিউশন ব্যবহার করে, কাঙ্ক্ষিত মোট আয়ের উপর ভিত্তি করে গোষ্ঠীতে গোষ্ঠীভুক্ত করা যেতে পারে। এই বিষয়টি মাথায় রেখে, গভীরভাবে সাবটাস্কের প্রতিটি গ্রুপের জন্য আমাদের গোষ্ঠীতে গোষ্ঠীভুক্ত করতে সহায়তা করুন; গাছে লক্ষ্য করুন যে, কিছু এল-এর জন্য এটি ফার্মাট সংখ্যা। মোড করার সময়, আমাদের কাছে ফার্মাট রিং নামে কিছু থাকে। যেহেতু কিছু ফার্মাট সংখ্যা ফার্মাট মৌলিক সংখ্যা, তাই কিছু ক্ষেত্রে গণনা এড়ানো যেতে পারে। অন্যান্য এন রয়েছে যা অবশ্যই একই মৌলিক সংখ্যার সুবিধার সাথে ব্যবহার করা যেতে পারে। ধরা যাক, বিট সহ একটি বাইনারি সংখ্যায় সর্বাধিক সংখ্যা থাকে। এটি একটি মার্সেন সংখ্যা, যা কিছু ক্ষেত্রে একটি মার্সেন মৌলিক সংখ্যা। এটি ফার্মাট সংখ্যার বিপরীতে একটি স্বাভাবিক প্রার্থী অন্য এন-এর সন্ধানে বিভিন্নের বিরুদ্ধে বেশ কয়েকটি মোড গণনা করা, পূর্ণসংখ্যা পণ্য সমাধানের ক্ষেত্রে সহায়ক হতে পারে। চীনা অবশিষ্টাংশ উপপাদ্য ব্যবহার করে, বিভিন্ন ধরনের ছোট ছোট ভাগে বিভক্ত হওয়ার পর, গুণনের উত্তর পাওয়া যায় ফার্মাট সংখ্যা এবং মার্সেন সংখ্যা হল মাত্র দুই ধরনের সংখ্যা, যা সাধারণীকৃত ফার্মাট মার্সেন সংখ্যা (জিএসএম) নামে পরিচিত; সূত্র সহঃ এই সূত্রে; একটি ফার্মাট সংখ্যা, এবং এটি একটি মার্সেন সংখ্যা। এই সূত্রটি সমীকরণের সেট তৈরি করতে ব্যবহার করা যেতে পারে, যা সি. আর. টি (চীনা অবশিষ্ট উপপাদ্য)-তে ব্যবহার করা যেতে পারেঃ, যেখানে এমন একটি সংখ্যা রয়েছে যেখানে একটি অবস্থান রয়েছে, ধরে নেওয়া হয়। যদি, কোথায়, তাহলে। একটি নির্দিষ্ট এন-এর জন্য কীভাবে কে বেছে নেওয়া যায় নিম্নলিখিত সূত্রটি একজনকে সহায়তা করে, দক্ষতা গণনা করে প্রদত্ত বিট আকারের একটি সঠিক (বিটগুলিকে বিভক্ত করার জন্য গোষ্ঠীর সংখ্যা) খুঁজে বের করতেঃ বাইরের স্তরে বিট আকার (যেটিতে ব্যবহৃত হয়)। বিটের গ্রুপ দেয়, যেখানে। যদি কেউ 50 শতাংশের উপরে দক্ষতা ধরে নেয় এবং বাকি সূত্রের তুলনায় খুব ছোট হয়, তাহলে এর মাধ্যমে এবং তার সন্ধান পাওয়া যায়। এর অর্থঃ যখন কোনও কিছু খুব কার্যকর হয়; সিউডোকোড দ্বারা উপরে বা অ্যাসিম্পটোটিক্যালি দ্বারা উপরে আবদ্ধ থাকে, তখন স্ট্যান্ডার্ড মডুলার স্কোনহেজ-স্ট্রাসেন মাল্টিপ্লিকেশন অ্যালগরিদম (কিছু অপ্টিমাইজেশান সহ) টি3এমইউএল = টুম-কুক গুণন এসএমইউএল = স্কোনহেজ-স্ট্রাসেন গুণন মূল্যায়ন = এফএফটি/আইএফএফটি-এর মাধ্যমে পর্যালোচনায় পাওয়া যায়। এই বৈকল্পিকটি স্কোনহেজের মূল পদ্ধতির থেকে কিছুটা আলাদা যে এটি আরও দক্ষতার সাথে নেতিবাচক চক্রাকার কনভোলিউশন সম্পাদনের জন্য পৃথক ওজনযুক্ত রূপান্তরকে কাজে লাগায়। বিস্তারিত তথ্যের আরেকটি উৎস হল ক্নুথের দ্য আর্ট অফ কম্পিউটার প্রোগ্রামিং। অপ্টিমাইজেশান এই বিভাগটি স্কোনহাজ-স্ট্রাসেন বাস্তবায়নের সময় বেশ কয়েকটি গুরুত্বপূর্ণ ব্যবহারিক অপ্টিমাইজেশান ব্যাখ্যা করে। অ্যালগরিদমের অভ্যন্তরে অন্যান্য গুণন অ্যালগরিদমের ব্যবহার একটি নির্দিষ্ট কাটঅফ পয়েন্টের নিচে, অন্যান্য গুণন অ্যালগরিদম ব্যবহার করা আরও কার্যকর, যেমন টুম-কুক গুণন। 2 কৌশলের বর্গমূল ধারণাটি হল এন. টি. টি-তে (সংখ্যা তাত্ত্বিক রূপান্তর) মান ওজন করার সময় সসীম ক্ষেত্রে ক্রমের ঐক্যের মূল হিসাবে ব্যবহার করা (এটি সমীকরণের একটি সমাধান)। এটি পূর্ণসংখ্যা গুণনের সময় 10 শতাংশ সাশ্রয় করতে দেখা গেছে। গ্র্যানলান্ডের কৌশল; কেউ গণনা করতে পারে এবং। গুণনের সঠিক মান খুঁজে বের করতে সি. আর. টি (চীনা অবশিষ্ট উপপাদ্য)-এর সংমিশ্রণে তথ্যসূত্র কম্পিউটার গাণিতিক অ্যালগরিদম গুণ