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