കരത്സൂബാ അൽഗൊരിതം

ഇതൊരു അതിവേഗ ഗുണന അൽഗൊരിതമാണ്. അനറ്റോളി അലക്സീവിച്ച് കരത്സൂബ എന്ന റഷ്യൻ ഗണിതജ്ഞനാണിതിന്റെ ഉപജ്ഞാതാവ്. വിഭജിച്ച് കീഴടക്കുക എന്ന ഗണത്തിൽ വരുന്ന ഒരു അൽഗൊരിതമാണു കരത്സൂബാ അൽഗൊരിതം.

അൽഗരിതം

2 സംഖ്യകൾ x, y എന്നിവ തമ്മിൽ ഗുണിക്കണമെന്നിരിക്കട്ടേ. x എന്ന സംഖ്യയിൽ p q എന്ന അക്കങ്ങളും, y എന്ന സംഖ്യയിൽ, a b എന്ന അക്കങ്ങളും ഉണ്ട് എന്ന് ഇരിക്കട്ടേ.

ഈ സംഖ്യകളെ ചുവട്ടിൽ കൊടുത്തിരിക്കുന്നതു പോലെ രേഖപ്പെടുത്താം

x എന്നതിനെ 10(n/2) * p + q

y എന്നതിനെ 10(n/2) * a + b

(ഉദാഹരണമായിട്ട് 5678 * 1234 എന്ന ഗുണിതത്തിൽ, p എന്നത് 56 ഉം, q എന്നത് 78 ഉം, a എന്നത് 12 ഉം, b എന്നത് 34 ഉം ആയിട്ടെടുക്കാം. ഇതിനെ യഥാക്രമം 10(4/2) * 56 + 78, 10(4/2) * 12 + 34 എന്നും രേഖപ്പെടുത്താവുന്നതാണ്)

സംഖ്യകൾ x,y എന്നിവ തമ്മിൽ ഗുണിച്ചാൽ

   x * y   =  (10(n/2) * p + q) * (10(n/2) * a + b) 
           =  10(n) * pa + 10(n/2) * (qa+pb) + qb    

ഈ ഘട്ടത്തിൽ, 4 ഗുണിതങ്ങൾ നടത്തേണ്ടതുണ്ട്. p*a, q*a, q*b, p*b. കരത്സൂബ ഇതിലൊരു പ്രത്യേകത ദർശിച്ചു. 4 ഗുണിതത്തിനു പകരം 3 ഗുണിതം നടത്തി ശരിയായ ഉത്തരം കണ്ടെത്താമെന്നു അദ്ദേഹം നിരീക്ഷിച്ചു.  ചുവട്ടിൽ കൊടുത്തതു പോലെയാണത്.


  (qa+pb)   =  (p+q)(a+b) - pa - qb
            =  pa+qb+pb+qa - pa - qb 
            =  qa + pb    

അതായത്, 
x * y   =  10(n) * p*a + 10(n/2) * ((p+q)(a+b) - pa - qb) + q*b    

ഇതിലേ ഓരോ ഗുണിതങ്ങളും (മേൽ കൊടുത്ത വിശദീകരണത്തിലെ  p*a,(p+q)*(a+b),q*b എന്നിവ), റിക്കർസീവ് ആയി ചെയ്യാവുന്നതാണു. ഓരൊ റികർസീവ് സ്റ്റെപിലെയും ഗുണിതങ്ങൾ വീണ്ടും റിക്കർസീവായി ചെയ്യാവുന്നതാണ്  ഇവിടെ മുകളിൽ വിശദീകരിച്ചതു പോലെ ഓരോ റിക്കർസ്സിവ് സ്റ്റെപ്പിലെയും ഗുണിതങ്ങളുടെ എണ്ണം 4 ൽ നിന്നും 3 ആയി കുറച്ചു കൊണ്ട് വരുന്നു. ഇപ്രകാരം വളരെ വലിയ രണ്ട് സംഖ്യകൾ തമ്മിലുള്ള ഗുണിതം താരതമ്യേന കുറഞ്ഞ എണ്ണം പ്രാഥമിക ഗണിത ക്രിയകൾ വഴി കണക്ക് കൂട്ടാവുന്നതാണ്.

സങ്കീർണ്ണത
നിലവിൽ ഉള്ള സാധാരണ ഗുണിതത്തിൽ, രണ്ട് n അക്കങ്ങളുള്ള സംഖ്യകളുടെ സങ്കീർണ്ണത n2 ആകുമ്പോൾ കരത്സൂബ അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത 3nlg3 ആണ്.

അവലംബം
https://www.coursera.org/course/algo

വർഗ്ഗം:അൽഗൊരിതങ്ങൾ