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

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
Jump to navigation Jump to search

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

അൽഗരിതം[തിരുത്തുക]

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

"https://ml.wikipedia.org/w/index.php?title=കരത്സൂബാ_അൽഗൊരിതം&oldid=2362016" എന്ന താളിൽനിന്നു ശേഖരിച്ചത്