কারাতসুবা গুণন (Karatsuba Multiplication)

ধরুন আপনাকে ১,০০০ ডিজিট বা অঙ্কের দুটি সংখ্যা গুণ করতে হবে — যেমনটা আপনার ব্রাউজারের RSA এনক্রিপশন কি (key) তৈরির সময় হয়ে থাকে। আমরা স্কুলে যে সাধারণ পদ্ধতিতে গুণ করা শিখি (long multiplication), তাতে প্রায় ১০ লক্ষ (১,০০০,০০০) একক অঙ্কের গুণ করতে হবে। এটি বেশ ধীরগতিসম্পন্ন এবং ১০,০০০ ডিজিটের সংখ্যার ক্ষেত্রে এটি ১০ কোটি পর্যন্ত পৌঁছাতে পারে।

১৯৬০ সালে, ২৩ বছর বয়সী একজন গণিতবিদ আনাতলি কারাতসুবা একটি বিশেষ কৌশল খুঁজে পান যা এই সময়কে নাটকীয়ভাবে কমিয়ে দেয়। মূল ধারণাটি হলো: প্রতিটি বড় সংখ্যাকে দুই অর্ধে ভাগ করা এবং ৪টি গুণের পরিবর্তে মাত্র ৩টি গুণ করা। প্রথমে মনে হতে পারে এটি খুব সামান্য পরিবর্তন। কিন্তু যখন এটি বারবার রিকার্সিভলি প্রয়োগ করা হয়, তখন এটি \(O(n^2)\) এর পরিবর্তে \(O(n^{1.585})\) জটিলতা তৈরি করে। বড় সংখ্যার ক্ষেত্রে এই পার্থক্যটা বিশাল!

পদ্ধতিটি কীভাবে কাজ করে?

ধরা যাক আপনার কাছে দুটি n-ডিজিটের সংখ্যা x এবং y আছে। এদের ঠিক মাঝখানে দুই ভাগে ভাগ করুন:

x = a \(\times\) \(10^{n/2}\) + b, এবং y = c \(\times\) \(10^{n/2}\) + d, যেখানে a এবং c হলো বাম দিকের বড় অংশ, আর b এবং d হলো ডান দিকের ছোট অংশ।

তাহলে: x \(\times\) y = ac \(\times\) \(10^n\) + (ad + bc) \(\times\) \(10^{n/2}\) + bd

সাধারণ পদ্ধতিতে আমাদের চারটি গুণফল বের করতে হতো: ac, ad, bc এবং bd।

কৌশল: একটি গুণ বাঁচানো

লক্ষ্য করুন যে: (a+b)(c+d) = ac + ad + bc + bd।

সুতরাং: ad + bc = (a+b)(c+d) − ac − bd

তার মানে আমাদের মাত্র তিনটি গুণফল দরকার: \(P_1 = ac\), \(P_2 = bd\) এবং \(P_3 = (a+b)(c+d)\)। এরপর যোগ-বিয়োগের মাধ্যমেই আমরা ad + bc এর মান পেয়ে যাচ্ছি। চূড়ান্ত উত্তরটি হবে: \(P_1 \times 10^n + (P_3 - P_1 - P_2) \times 10^{n/2} + P_2\)।

এখানে যোগ এবং শিফটিংয়ের কাজগুলো খুবই দ্রুত (\(O(n)\)) করা যায়, তাই গুণের সংখ্যা কমানোই আসল বিজয়।

কেন একটি গুণ বাঁচানো এত গুরুত্বপূর্ণ?

মাস্টার থিওরেম অনুযায়ী রিকারেন্স হলো: \(T(n) = 3T(n/2) + O(n)\)। যেহেতু a=3 এবং b=2, তাই এর জটিলতা দাঁড়ায় \(O(n^{1.585})\)। অন্যদিকে সাধারণ পদ্ধতিতে ৪টি রিকার্সিভ কল দিলে এটি হতো \(O(n^2)\)।

আধুনিক বিশ্বের সবচেয়ে দ্রুত গুণন অ্যালগরিদমগুলো (যেমন: Schönhage-Strassen বা Harvey-Hoeven) আরও উন্নত পদ্ধতি ব্যবহার করে একে প্রায় লিনিয়ার পর্যায়ে নিয়ে গেছে, কিন্তু কারাতসুবা ছিল প্রথম অ্যালগরিদম যা প্রমাণ করেছিল যে গুণ করার জন্য \(O(n^2)\) এর চেয়েও ভালো পথ রয়েছে।