log(n) সময়ে ফিবোনাচ্চি নির্ণয়(Matrix Exponentiation)

ফিবোনাচ্চি সিরিজ সম্পর্কে নিশ্চয়ই জানেন! তবুও আমি অল্প কিছু কথায় পরিচয় করিয়ে দিচ্ছি। ত্রয়োদ্বশ শতাব্দী তে বিখ্যাত ইতালীয় গণিতবীদ ফিবোনাচ্চি খরগোশের বংশবৃদ্ধি পর্যবেক্ষণ করতে গিয়ে একটি সিরিজ দেখতে পান। সিরিজটি হচ্ছে ০ ১ ১ ২ ৩ ৫ ৮ ১৩ ২১ .... মানে প্রথম দুইটি ছাড়া বাকি সংখ্যা গুলো পূর্বের দুইটি সংখ্যার যোগফল। 

এখন যদি বলা হয় n একটি পূর্ণ সংখ্যা এবং n তম ফিবোনাচ্চি সংখ্যাটি কত? খুব সহজ! সিরিজটি ভালো করে খেয়াল করলে দেখা যাবে এটি ডায়নামিক প্রোগ্রামিং দিয়ে খুব সহজেই সমাধান করা সম্ভব!
যেহেতু, 
f[0] = 0;
f[1] = 1;
সুতরাং যদি n ১ এর থেকে বড় হয় তাহলে,
f[n] = f[n-1] + f[n-2];
একটি অ্যারে নিয়ে খুব সহজেই সমাধান বের করে ফেলা যাচ্ছে। কোড দেখার আগেই আশা করছি নিজেই কোড লিখে ফেলতে পারবেন। 

int fibnacci(int n) {   int fib[n+1];   fib[0] = 0;   fib[1] = 1;   for (int i = 2;i <= n;i++) {     fib[i] = fib[i-1] + fib[i-2];   }   return fib[n]; }

এখন একটু অন্যভাবে সমাধানের চেষ্টা করি। আশা করছি ম্যাট্রিক্স কীভাবে গুণ করতে হয় তা জানেন। আইডেনটিটি ম্যাট্রিক্স হচ্ছে এমন একটি ম্যাট্রিক্স যার সাথে অন্য কোন ম্যাট্রিক্স গুণ করলে ঐ ম্যাট্রিক্সের কোন পরিবর্তন হয় না। যেমন ২ x ২ ম্যাট্রিক্সের জন্য আইডেনটিটি ম্যাট্রিক্স হচ্ছে,
১ ০
০ ১
যদি বিষয় টি নতুন হয়ে থাকে তাহলে ভেবে দেখুন যোগ করার সময় n এর সাথে কোন সংখ্যা যোগ করলে n এর ভ্যালু পরিবর্তন হবে না? ০ অবশ্যই। তাহলে এখানে ০ হচ্ছে আইডেনটিটি সংখ্যা। একই ভাবে n এর সাথে কোন সংখ্যা গুণ করলে n এর ভ্যালু পরিবর্তন হবে না? এখন সংখ্যাটি ১ অবশ্যই। আশাকরছি বুঝতে পেরেছেন। আমরা ২ x ২ আরেকটি ম্যাট্রিক্সকে আইডেনটিটি ম্যাট্রিক্সের সাথে গুণ করে দেখি,
৪ ৫    ১ ০    (৪ x ১)+(৫ x ০)  (৪ x ০)+(৫ x ১)     ৪ ৫
      X       =                                                    =    
৬ ৭    ০ ১    (৬ x ১)+(৭ x ০)  (৬ x ০)+(৭ x ১)     ৬ ৭

ধরি, ফিবোনাচ্চি সিরিজের প্রথম সংখ্যা a = 0 এবং দ্বিতীয় সংখ্যা b = 1। তাহলে ফিবোনাচ্চি সিরিজের base ম্যাট্রিক্স বের করে ফেলি!!!
a+b   b              ১  ১
                 =      
b       a              ১  ০
এখন base ম্যাট্রিক্স কে আইডেনটিটি ম্যাট্রিক্স দিয়ে গুণ করলে,
১   ০              ১  ১                  ১  ১
            X                    =        
০   ১              ১  ০                  ১  ০
ফিবোনাচ্চি সিরিজের শূণ্য, ১ম এবং ২য় পদ পেয়ে গেলাম।
১   ১              ১  ১                  ২  ১
            X                    =        
১   ০              ১  ০                  ১  ১
ফিবোনাচ্চি সিরিজের ১ম, ২য় এবং ৩য় পদ পেয়ে গেলাম।
২   ১              ১  ১                  ৩  ২
            X                    =        
১   ১              ১  ০                  ২  ১
ফিবোনাচ্চি সিরিজের ২য়, ৩য় এবং ৪র্থ  পদ পেয়ে গেলাম।
৩   ২              ১  ১                  ৫  ৩
            X                    =        
২    ১              ১  ০                  ৩  ২
ফিবোনাচ্চি সিরিজের ৩য়, ৪র্থ এবং ৫ম পদ পেয়ে গেলাম।

যদি n তম ফিবোনাচ্চি সংখ্যা বের করতে চাই তাহলে, ম্যাট্রিক্স গুণ করে বের করতে পারি। একটি বিষয় উল্লেখ করা দরকার, ১০০ তম ফিবোনাচ্চি সংখ্যাও কিন্তু অনেক বড়, তাই এখন ১০০০৭ দিয়ে মোড করে উত্তর বের করব। নিচে কোড দেওয়া হল। কোডে আইডেনটিটি ম্যাট্রিক্স ব্যবহার করব না, তাহলে ১টি ধাপ কমে যাবে।

int base[2][2];
int fib[2][2];

// initialize to base and fib
// ১ ১
// ১ ০
base[0][0] = fib[0][0] = 1;

base[0][1] = fib[0][1] = 1;

base[1][0] = fib[1][0] = 1;

base[1][1] = fib[1][1] = 0;

int mod = 1e4 + 7; int base[2][2]; int fib[2][2]; int find_nth_fib(int n) {   while (n--) {     int temp[2][2];     for (int i = 0;i < 2;i++) {       for (int j = 0;j < 2;j++) {         int el = 0;         for (int k = 0;k < 2;k++) {           el = (el + base[i][k] * fib[k][j]) % mod;         }         temp[i][j] = el;       }     }     for (int i = 0;i < 2;i++) {       for (int j = 0;j < 2;j++) {         fib[i][j] = temp[i][j];       }     }   }   return fib[1][1]; } int main() {   int n;   cin >> n;   // 1 1   // 1 0   base[0][0] = 1;   base[0][1] = 1;   base[1][0] = 1;   base[1][1] = 0;   // 1 1   // 1 0   fib[0][0] = 1;   fib[0][1] = 1;   fib[1][0] = 1;   fib[1][1] = 0;   cout << find_nth_fib(n) << '\n';   return 0; }

হয়ত ভাবছেন, লাভ কী হল? এখন ত সময় লাগবে O(dim^3 * n) যা ডিপি দিয়ে করার থেকে অনেক বেশি। ঠিক তাই, তবে এখানে কিন্তু dim = 2 মানে dim x dim = ২ x ২ ম্যাট্রিক্স ব্যবহার করছি যা কমপ্লেক্সিটি O(1) ই ধরা যায়। কারণ O(n) এবং O(1) সমান যেখানে n 10 এর থেকে ছোট বা সমান। তাহলে কমপ্লেক্সিটি কিন্তু O(n) ই হচ্ছে। এরপরেও হয়ত ভাবতে পারেন, কিন্তু লাভ কী হল? কমপ্লেক্সিটি ত আগেরটাই রয়ে গেল আর ডিপির কোড অনেক সহজ ছিলো। 

এখনই আসলে মূল বিষয়ে আসছি, একটু খেয়াল করলে দেখবেন আমরা আগের টিউটোরিয়ালে পাওয়ার নির্ণয় শিখেছিলাম, সামনে যাওয়ার আগে পূর্বের টিউটোরিয়াল টি ক্লিয়ার করা জরুরী। যদি, না পড়ে থাকেন। প্রথমে O(n) সময়ে এবং পরে O(log(n)) সময়ে। কারন, ৮ টি ২ কে এক এক করে গুণ করার চেয়ে ৪টি ২ কে এক এক করে গুণ করে গুণফল কে আবার গুণফল দিয়ে গুণ করলেই উত্তর পেয়ে যাই। এভাবে অর্ধেক করে করে log(n) সময়েই পাওয়ার বের করা যায়। তবে n বিজোর হলে গুণফল কে base দ্বারা গুণ করে base এ রেখে দিব। এইখানেও একইভাবে ম্যাট্রিক্স গুণ করে log(n) সময়ে আমরা n তম ফিবোনাচ্চি সংখ্যা বের করে ফেলতে পারব। n সমান ১০^১৮ হলেও সমস্যা নেই। কারণ সর্বোচ্চ ৬৪ টি ধাপেই কাজ শেষ হয়ে যাবে। ৫ তম ফিবোনাচ্চি সংখ্যা বের করে দেখতে পারি।

৫ বিজোর, এখন ৫-১ এবং
base = base      X       fib
            ১ ১                 ১ ১                      ২ ১
        =               X                      =          
            ১ ০                 ১ ০                      ১ ১
৪ জোর, এখন ৪/২ এবং
fib    = fib         X       fib
            ১ ১                  ১ ১                      ২ ১
         =              X                      =          
            ১ ০                  ১ ০                      ১ ১
২ জোর, এখন ২/২ এবং
fib    = fib         X       fib
            ২ ১                  ২ ১                      ৫ ৩
         =              X                      =          
            ১ ১                  ১ ১                      ৩ ২
১ বিজোর, এখন ১-১ এবং
base    =  base         X       fib
               ২ ১                      ৫ ৩                      ১৩ ৮
           =                  X                      =          
               ১ ১                      ৩ ২                      ৮   ৫

void multiply(int a[][2], int b[][2], int mod) {   int temp[2][2];   for (int i = 0;i < 2;i++) {     for (int j = 0;j < 2;j++) {       temp[i][j] = 0;       for (int k = 0;k < 2;k++) {         temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % mod;       }     }   }   // put result in a means, put it base/fib   // cause a and fib/base matrix contains same address now   for (int i = 0;i < 2;i++) {     for (int j = 0;j < 2;j++) {       a[i][j] = temp[i][j];     }   } } int find_nth_fib(int n) {   int mod = 1e4 + 7;   int base[2][2];   int fib[2][2];   // initialize fib and base   // 1 1   // 1 0   for (int i = 0;i < 2;i++) {     for (int j = 0;j < 2;j++) {       if (i<1 || j<1) {         fib[i][j] = 1;         base[i][j] = 1;       } else {         fib[i][j] = 0;         base[i][j] = 0;       }     }   }   while (n) {     if (n%2) {       // if n is odd then rise fib = fib * base       multiply(fib, base, mod);       n--;     } else {       // if n is even then rise base = base * base       multiply(base, base, mod);       n /= 2;     }   }   return fib[1][1]; }

n ছোট তাই আসলে ধাপ যে কমেছে তা তেমন বুঝা যাচ্ছে না। তবে n সমান ২১৪৭৪৮৩৬৪৭ হলে সর্বোচ্চ ৩২ ধাপেই হয়ে যাবে!!! 

প্র্যাক্টিস প্রবলেমঃ 
Modular Fibonacci
Yet Another Number Sequence
Power of Matrix

এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১
টিউটোরিয়াল ২
টিউটোরিয়াল ৩