smcproject/ml-wiki-sentences huggingface dataset:
സംഖ്യകളെ അവയുടെ അക്കങ്ങളുപയോഗിച്ച് വിവരിക്കുന്നതിനു പകരം m i എന്ന പരസ്പരം സഹ-അഭാജ്യമായ N സംഖ്യകൾ കൊണ്ടു ഹരിച്ചാൽ കിട്ടുന്ന ശിഷ്ടങ്ങളായ x i എന്നിവ കൊണ്ട് സൂചിപ്പിക്കുന്നു.
ഈ സർവ്വസമതകളെ ഇപ്രകാരം എഴുതാം: x 1 ≡ x ( mod m 1 ) x 2 ≡ x ( mod m 2 ) ⋮ x N ≡ x ( mod m N ) .
{\displaystyle {\begin{aligned}x_{1} \equiv x{\pmod {m_{1}}}\\x_{2} \equiv x{\pmod {m_{2}}}\\ \,\,\,\vdots \\x_{N} \equiv x{\pmod {m_{N}}}\,.
x i എന്ന ശിഷ്ടങ്ങളുപയോഗിച്ച് x കണ്ടുപിടിക്കുകയാണ് ലക്ഷ്യം.
ഈ സമവാക്യങ്ങളെയെല്ലാം കൂട്ടിച്ചേർത്ത് m i എന്ന മാപാങ്കങ്ങളുടെ (moduli) ഗുണനഫലമായ M മാപാങ്കമായുള്ള ഒറ്റ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യമായി മാറ്റുക വഴി ഇത് സാധിക്കാം.
m i ഒഴികെയുള്ള മാപാങ്കങ്ങളുടെ ഗുണനഫലത്തെ M i എന്ന് വിളിക്കുക: M i = M m i .
{\displaystyle M_{i}={\frac {M}{m_{i}}}.
താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യമനുസരിക്കുന്ന (യഥാർത്ഥത്തിൽ N സമവാക്യങ്ങൾ) സംഖ്യകൾ കണ്ടുപിടിക്കുകയാണ് നിർദ്ധാരണത്തിലെ പ്രധാന പടി M i h i ≡ 1 ( mod m i ) .
{\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.
h i എന്ന സംഖ്യകളിൽ നിന്നും x കണ്ടുപിടിക്കാൻ ഈ സൂത്രവാക്യമുപയോഗിക്കാം x ≡ ( x 1 M 1 h 1 + x 2 M 2 h 2 + ⋯ + x N M N h N ) ( mod M ) .
{\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.
h i എന്ന സംഖ്യകൾ M i എന്നിവയുടെ ഗുണനവിപരീതങ്ങളായതിനാൽ മുൻപത്തെ ഭാഗത്ത് വിവരിച്ചതുപോലെ അവയെ യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.
സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീ
എല്ലാ ധന ഭിന്നകസംഖ്യകളെയും ഒരു അനന്ത ബൈനറി സർച്ച് ട്രീയുടെ രൂപത്തിൽ ക്രമീകരിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം.
ഈ ട്രീ സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീ എന്നറിയപ്പെടുന്നു.
1 എന്ന സംഖ്യയെ 1/1 എന്ന ഭിന്നസംഖ്യയുടെ രൂപത്തിൽ ട്രീയുടെ മൂലത്തിൽ (root) നിക്ഷേപിക്കാം.
a / b എന്ന മറ്റേത് സംഖ്യയുടെയും ട്രീയിലെ സ്ഥാനം നിർണ്ണയിക്കുന്നത് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൂലരൂപമുപയോഗിച്ച് ഉസാഘയായ gcd( a , b ) കണ്ടാണ്.
അൽഗൊരിതത്തിന്റെ മൂലരൂപത്തിൽ ശിഷ്ടം കാണുന്നതിനു പകരം വലിയ സംഖ്യയിൽ നിന്ന് ചെറുത് കുറയ്ക്കുകയും സംഖ്യകൾ തുല്യമാകുമ്പോൾ നിർത്തുകയുമാണല്ലോ ചെയ്യുന്നത്.
ആദ്യത്തെ സംഖ്യയിൽ നിന്ന് രണ്ടാമത്തേത് കുറയ്ക്കുകയാണെങ്കിൽ ട്രീയിലെ ഒരു ശീഷത്തിൽ നിന്ന് അതിന്റെ വലത്തെ പിൻഗാമിയിലേക്ക് (right child) നീങ്ങുന്നു, പകരം രണ്ടാമത്തെ സംഖ്യയിൽ നിന്ന് ആദ്യത്തേതാണ് കുറയ്ക്കുന്നതെങ്കിൽ ഇടത്തെ പിൻഗാമിയിലേക്കാണ് (left child) നീങ്ങുക.
മൂലത്തിൽ നിന്ന് തുടങ്ങി ഈ നിയമമനുസരിച്ച് നീങ്ങിയാൽ അൽഗൊരിതം അവസാനിക്കുമ്പോൾ എത്തുന്ന ശീർഷമാണ് ട്രീയിൽ a / b യുടെ സ്ഥാനം.
ഈ പഥത്തിന്റെ നീളവും ക്രമവും a / b അതിന്റെ ലഘൂകരിച്ച രൂപത്തിലാണോ സൂചിപ്പിച്ചിരിക്കുന്നത് എന്നതിനെ ആശ്രയിക്കുന്നില്ല.
അതിനാൽ ഓരോ ധനഭിന്നകസംഖ്യയുടെയും ട്രീയിലെ സ്ഥാനം അനന്യമാണെന്നു വരുന്നു.
സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീയുടെ ആദ്യത്തെ നാല് തലങ്ങൾ
ഉദാഹരണമായി, 3/4 ന്റെ ശീർഷത്തിലെത്താൻ ട്രീയുടെ മൂലത്തിൽ തുടങ്ങി ഇടത്തേക്ക് ഒരു തവണയും തുടർന്ന് വലത്തേക്ക് രണ്ടു തവണയും നീങ്ങുന്നു: gcd ( 3 , 4 ) ← = gcd ( 3 , 1 ) → = gcd ( 2 , 1 ) → = gcd ( 1 , 1 ) .
{\displaystyle {\begin{aligned} \gcd(3,4) \leftarrow \\={} \gcd(3,1) \rightarrow \\={} \gcd(2,1) \rightarrow \\={} \gcd(1,1).
ഭിന്നകസംഖ്യകളുടെ മറ്റൊരു ബൈനറി ട്രീ ആയ കാൽകിൻ-വിൽഫ് ട്രീയുമായും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് ബന്ധമുണ്ട്.
പഥം വിപരീതക്രമത്തിലാണ് നിർമ്മിക്കുന്നത് എന്നതാണ് വ്യത്യാസം: അതായത്, ട്രീയുടെ മൂലത്തിൽ നിന്ന് സംഖ്യയുടെ ശീർഷത്തിലേക്കുള്ള പഥത്തിനു പകരം സംഖ്യയുടെ ശീർഷത്തിൽ നിന്ന് ട്രീയുടെ മൂലത്തിലേക്ക് പോകുന്നു.
സതതഭിന്നം
സതതഭിന്നങ്ങളുമായും (continued fraction) യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് അടുത്ത ബന്ധമുണ്ട്.
അൽഗൊരിതത്തിലെ പടികളുടെ സമവാക്യങ്ങളെ ഇപ്രകാരവും എഴുതാം: a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N .
{\displaystyle {\begin{aligned}{\frac {a}{b}} =q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}} =q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}} =q_{2}+{\frac {r_{2}}{r_{1}}}\\ \,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}} =q_{k}+{\frac {r_{k}}{r_{k-1}}}\\ \,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}} =q_{N}\,.
ഓരോ സമവാക്യത്തിന്റെയും വലതുഭാഗത്തെ രണ്ടാമത്തെ പദം അടുത്ത സമവാക്യത്തിന്റെ ഇടതുഭാഗത്തിന്റെ വ്യുൽക്രമമാണ്.
അതിനാൽ ആദ്യത്തെ രണ്ട് സമവാക്യങ്ങളെയും ഈ വിധത്തിൽ കൂട്ടിച്ചേർക്കാം a b = q 0 + 1 q 1 + r 1 r 0 .
{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.
മൂന്നാമത്തെ സമവാക്യമുപയോഗിച്ച് ഛേദത്തിലെ r 1 / r 0 എന്ന പദത്തെ വികസിപ്പിക്കാം a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 .
{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.
ഓരോ പടിയിലെയും r k / r k −1 എന്ന ശിഷ്ടങ്ങളുടെ അനുപാതത്തെ ഇങ്ങനെ അടുത്ത സമവാക്യമുപയോഗിച്ച് വികസിപ്പിക്കാം.
അവസാനത്തെ സമവാക്യവും ഇങ്ങനെ ഉപയോഗിച്ചു കഴിയുമ്പോൾ ഒരു സതതഭിന്നം ലഭിക്കുന്നു a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] .
{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.
മുകളിൽ gcd(1071, 462) കണ്ടുപിടിച്ചപ്പോൾ q k എന്ന ഹരണഫലങ്ങളായി ലഭിച്ചത് 
2, 3, 7 എന്ന സംഖ്യകളായിരുന്നു.
അതിനാൽ 1071/462 എന്ന ഭിന്നസംഖ്യയെ സതതഭിന്നരൂപത്തിൽ ഇപ്രകാരം എഴുതാം 1071 462 = 2 + 1 3 + 1 7 = [ 2 ; 3 , 7 ] {\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}
ഇത് ശരിയാണെന്ന് നേരിട്ട് കണക്കുകൂട്ടിയാൽ കാണാൻ വിഷമമില്ല.
ഇപ്രകാരം ഏത് ഭിന്നകസംഖ്യയുടെയും സതതഭിന്നരൂപം യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.
ഫാക്റ്ററൈസേഷൻ അൽഗൊരിതങ്ങൾ
വലിയ സംഖ്യകളുടെ ഘടകക്രിയ ചെയ്യാനുപയോഗിക്കുന്ന ഫാക്റ്ററൈസേഷൻ അൽഗൊരിതങ്ങളിലെ ഒരു പ്രധാന പടിയാണ് ഉസാഘ കാണുന്നത്.
പൊളാർഡ്സ് റോ അൽഗൊരിതം , ഷോർ അൽഗൊരിതം , ഡിക്സൺ രീതി ലെൻസ്ട്ര എലിപ്റ്റിക് കർവ് ഫാക്റ്ററൈസേഷൻ എന്നിവയെല്ലാം ഇങ്ങനെ ഉസാഘ ആവശ്യമുള്ള അൽഗൊരിതങ്ങളാണ്.
ഇതിനായ ഉസാഘ കാണാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം.
സതതഭിന്ന ഫാക്റ്ററൈസേഷൻ രീതിയിൽ സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനും അൽഗൊരിതം സഹായിക്കുന്നു.
ഗണനപരമായ സങ്കീർണ്ണത gcd( x , y ) കണ്ടുപിടിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ എടുക്കുന്ന പടികളുടെ എണ്ണം.
ചുവപ്പും മഞ്ഞയും ബിന്ദുക്കൾ താരതമ്യേന കുറഞ്ഞ എണ്ണം പടികളിൽ ഉസാഘ കണ്ടുപിടിക്കാനാവുന്നത് സൂചിപ്പിക്കുന്നു, വയലറ്റും നീലയും ബിന്ദുക്കൾ സൂചിപ്പിക്കുന്ന സംഖ്യാജോടികൾക്ക് കൂടുതൽ പടികൾ ആവശ്യമാണ്.
ഏറ്റവും ഇരുണ്ട ഭാഗം y = Φx എന്ന രേഖയോടടുത്താണ് (ഇവിടെ Φ സുവർണ്ണാനുപാാതമാണ് ).
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ഗണനപരമായ സങ്കീർണ്ണത സമഗ്രമായി പഠിക്കപ്പെട്ടിട്ടുണ്ട്.
അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത കണ്ടുപിടിക്കാൻ അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണത്തെ ഒരു പടിയുടെ ഗണനപരമായ ചിലവ്വുകൊണ്ട് ഗുണിച്ചാൽ മതി.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കുറിച്ച് ഇത്തരത്തിലുള്ള ആദ്യത്തെ പഠനം നടത്തിയത് 1811-ൽ എ.എ.എൽ. റെയ്നോഡ് ആണ്, u , v എന്ന സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാൻ v പടികൾ മതിയെന്ന് കണ്ടുപിടിക്കുകയും പിന്നീട് ഈ സീമ v /2 + 2 ആയി മെച്ചപ്പെടുത്തുകയും ചെയ്തു.
എമിൽ ലെഷെർ 1837-ൽ അൽഗൊരിതം ഏറ്റവുമധികം പടികളെടൂക്കുന്ന അവസ്ഥയെക്കുറിച്ച് പഠിച്ചു.
അനുക്രമമായ ഫിബനാച്ചി ശ്രേണികളുടെ ഉസാഘ കണ്ടുപിടിക്കുമ്പോഴാണ് ഇത് സംഭവിക്കുന്നത്.
ഇതിനു ശേഷം 1841-ൽ പിയേർ ജോസെഫ് എറ്റിയെൻ ഫിങ്ക് പടികളുടെ എണ്ണം 2 log 2 v + 1 മതിയെന്നും അതിനാൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ഇൻപുട്ട് വലിപ്പത്തിന്റെ ബഹുപദമാണെന്നും (polynomial time) കണ്ടെത്തി.
ഫിങ്കിന്റെ അപഗ്രഥനം പരിഷ്കരിച്ച ഗബ്രിയേൽ ലാമേ ചെറിയ സംഖ്യയായ b യെ ദശാംശസമ്പ്രദായത്തിൽ എഴുതാനെടുക്കുന്ന അക്കങ്ങളുടെ എണ്ണമായ h ന്റെ അഞ്ചിരട്ടി പടികളേ അൽഗൊരിതത്തിൽ ആവശ്യം വരൂ എന്ന് തെളിയിച്ചു.
ഒരു സംഖ്യ എത്ര വലുതാണെങ്കിലും അതിനെ കമ്പ്യൂട്ടറിന്റെ മെമ്മറിയിൽ ഒറ്റ മഷീൻ വാക്കിൽ സൂക്ഷിക്കാം എന്ന് കരുതുകയാണെങ്കിൽ സംഖ്യകൾക്കു മേൽ ഹരണം, ശിഷ്ടം മുതലായ സംക്രിയകൾ നടത്താൻ എടുക്കുന്ന സമയം സ്ഥിരമാണ് (സംഖ്യയുടെ വലിപ്പത്തെ ആശ്രയിക്കുന്നില്ല).
ഈ കല്പനയെ uniform cost model എന്നാണ് അൽഗൊരിതങ്ങളുടെ ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിൽ വിളിക്കുന്നത്.
ഈ അനുമാനത്തിനു കീഴിൽ അൽഗൊരിതത്തിന്റെ ഓരോ പടിയും ചെയ്യാനെടുക്കുന്ന സമയം ഒരു സ്ഥിരാങ്കമാണെന്നും അതിനാൽ അൽഗൊരിതത്തിന്റെ ആകെ സങ്കീർണ്ണത O ( h ) ആണെന്നും വരുന്നു.
എന്നാൽ ഒരു മഷീൻ വാക്കിലൊതുങ്ങാത്ത വലിയ സംഖ്യകളുടെ കാര്യത്തിൽ ഈ കല്പന ശരിയാവില്ല.
വലിയ സംഖ്യകളുടെ ശിഷ്ടം കാണാനെടൂക്കുന്ന അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത O ( h 2 ) വരെ ആകാം എന്നതിനാൽ ടെലിസ്കോപിങ് സീരീസ് ഉപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൊത്തം സങ്കീർണ്ണതയും O ( h 2 ) ആണെന്നു കാണാം.
വലിയ സംഖ്യകളെ കാര്യക്ഷമമായി ഗുണിക്കാനുപയോഗിക്കുന്ന ഷോൺഹാഗെ-സ്ട്രാസെൻ അൽഗൊരിതം മുതലായവ ഉപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ഇനിയും കുറച്ച് ക്വാസിലീനിയർ (quasilinear) വരെയാക്കാം.
പടികളുടെ എണ്ണം
a , b എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനെടുക്കുന്ന പടികളുടെ എണ്ണത്തെ T ( a , b ) കൊണ്ടു സൂചിപ്പിക്കാം.
ഇവയുടെ ഉസാഘ g ആണെങ്കിൽ a = mg എന്നും b = ng എന്നും വരുന്ന തരത്തിൽ m , n എന്ന സഹ-അഭാജ്യസംഖ്യകൾ കണ്ടുപിടിക്കാം.
ഇതുപയോഗിച്ച് T ( a , b ) = T ( m , n )
എന്നു ലഭിക്കുന്നു (യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ എല്ലാ പടികളെയും g കൊണ്ട് ഹരിച്ചാൽ ഇത് കാണാം) a , b എന്ന സംഖ്യകളെ രണ്ടിനെയും w എന്ന സംഖ്യകൊണ്ട് ഗുണിച്ചാലും പടികളുടെ എണ്ണത്തിൽ മാറ്റം വരില്ല, T ( a , b ) = T ( wa , wb ).
അതിനാൽ അടുത്തടുത്ത സംഖ്യകളുടെ കാര്യത്തിൽ പോലും ഉസാഘ കാണാനെടുക്കുന്ന പടികളുടെ എണ്ണം വ്യത്യാസപ്പെടാം.
അതായത്,  T( a , b ) യും T( a , b + 1) യും കാണാനാവശ്യമായ പടികൾ അവയുടെ ഉസാഘയനുസരിച്ച് വളരെ വ്യത്യസ്തമാണെന്നു വരാം.
യൂക്ലിഡിന്റെ അൽഗൊരിതം സമാവർത്തനമുപയോഗിക്കുന്നതിനാൽ താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യം ലഭിക്കുന്നു T ( a , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = … = N + T ( r N −2 , r N −1 ) = N + 1 .
ഇവിടെ T ( x , 0) = 0 എന്ന് കല്പിച്ചിരിക്കുന്നു.
കൂടിയ വില
ഉസാഘ കണ്ടുപിടിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ N പടികൾ ആവശ്യമായ ഏറ്റവും ചെറിയ സംഖ്യാജോടി ഫിബനാച്ചി സംഖ്യകളായ F N +2 , F N +1 എന്നിവയാണ്.
കൂടുതൽ കൃത്യമായി പറയുകയാണെങ്കിൽ, യൂക്ലിഡിന്റെ അൽഗൊരിതം a b ആയ രണ്ടു സംഖ്യകളുടെ ഉസാഘ കാണാൻ N പടികളെടുക്കുന്നുവെങ്കിൽ a ≥ F N +2 , b ≥ F N +1 ആയിരിക്കും.
ഗണിതീയാഗമനം വഴി ഇത് തെളിയിക്കാം.
N = 1 ആണെങ്കിൽ a യുടെ ഭാജകമായിരിക്കണം b .
ഇങ്ങനെ വരുന്ന ഏറ്റവും ചെറിയ സംഖ്യകൾ b = 1, a = 2 ആണ്.
ഇവ യഥാക്രമം ഫിബനാച്ചി സംഖ്യകളായ F 2 , F 3 എന്നിവയാണെന്നു കാണാം.
N ന്റെ M − 1 വരെയുള്ള എല്ലാ വിലകൾക്കും ഈ പ്രസ്താവന ശരിയാണെന്നു കരുതുക.
M പടികളുള്ള അൽഗൊരിതത്തിന്റെ ആദ്യത്തെ ക്രിയ a = q 0 b + r 0 കാണുകയാണ്, ഇതിനു ശേഷം b r 0 എന്നിവയുടെ ഉസാഘ M − 1 പടികളുപയോഗിച്ച് കാണുന്നു.
ഗണിതീയാഗമനത്തിലെ പരികല്പനയനുസരിച്ച് b ≥ F M +1 , r 0 ≥ F M ആണല്ലോ.
അതിനാൽ a = q 0 b + r 0 ≥ b + r 0 ≥ F M +1 + F M = F M +2
ഇതാണ് M ആമത്തെ പടിയിൽ തെളിയിക്കേണ്ടിയിരുന്ന അസമത.
1944-ൽ ഗബ്രിയേൽ ലാമേ ആണിത് തെളിയിച്ചത്.
ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിന് തുടക്കം കുറിച്ചത് ഈ ഫലമാണ്, ഫിബനാച്ചി സംഖ്യകളുടെ ആദ്യത്തെ പ്രായോഗികമായ ഉപയോഗവും ഈ തെളിവിലായിരുന്നു.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണം സംഖ്യകളെ ദശാംശസമ്പ്രദായത്തിലെഴുതുമ്പോളുള്ള അക്കങ്ങളുടെ എണ്ണത്തിന്റെ അഞ്ചിരട്ടിയിൽ കൂടുകയില്ല എന്നും ഈ ഫലമുപയോഗിച്ച് തെളിയിക്കാം.
അൽഗൊരിതം N പടികളുപയോഗിക്കുന്നുവെങ്കിൽ b യുടെ വില ചുരുങ്ങിയത് F N +1 ആയിരിക്കും എന്ന് മേലെ കണ്ടല്ലോ.
സുവർണ്ണാനുപാതത്തെ φ കൊണ്ട് സൂചിപ്പിച്ചാൽ ഇതിന്റെ വില φ N − 1 എങ്കിലും വരും.
b ≥ φ N − 1 ആയതിനാൽ N − 1 ≤ log φ b എന്നു വരുന്നു.
സുവർണ്ണാനുപാതത്തിന്റെ സ്വാഭാവിക ലോഗരിതത്തിന്റെ വില 1/5 ൽ കുറവായതിനാൽ ( N − 1)/5 log 10 φ log φ b = log 10 b .
എന്നു കാണാം.
അതായത്, N ≤ 5 log 10 b .
ചെറിയ സംഖ്യയായ b യുടെ അക്കങ്ങളുടെ എണ്ണം h ആണെങ്കിൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ O ( h ) ഹരണങ്ങളേ ആവശ്യമായി വരൂ.
ശരാശരി
യൂക്ലിഡിന്റെ അൽഗൊരിതം പൂർത്തീകരിക്കാനെടുക്കുന്ന ശരാശരി പടികളുടെ എണ്ണത്തെ മൂന്ന് രീതിയിൽ നിർവചിക്കാം.
വലിയ സംഖ്യയായ a നിർണ്ണയിച്ച ശേഷം ചെറിയ സംഖ്യയായ b യെ 0 മുതൽ a − 1 വരെയുള്ള പൂർണ്ണസംഖ്യകളിൽ നിന്ന് തുല്യ സംഭാവ്യതയോടെ തിരഞ്ഞെടുത്താൽ അൽഗൊരിതത്തിനാവശ്യമായ ശരാശരി പടികളുടെ എണ്ണമെടുക്കുകയാണ് ഒരു വഴി.
ഇതിനെ T ( a ) എന്ന് സൂചിപ്പിക്കാം T ( a ) = 1 a ∑ 0 ≤ b a T ( a , b ) .
{\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b a}T(a,b).
T ( a , b ) യുടെ വില സംഖ്യകളുടെ ഉസാഘയ്ക്കനുസരിച്ച് കാര്യമായി മാറുന്നതിനാൽ T ( a ) യും ഇവ്വിധം അവിച്ഛിന്നമായിരിക്കാൻ സാധ്യതയുണ്ട്.
ഇത്തരം ഏറ്റക്കുറച്ചിലുകളൊഴിവാക്കാൻ b യെ 0 മുതൽ a − 1 വരെയുള്ള പൂർണ്ണസംഖ്യകളിൽ വച്ച് a യോട് സഹ-അഭാജ്യമായുള്ളവ മാത്രമെടുത്ത് ശരാശരി പടികളുടെ എണ്ണം കാണാം, ഇതിനെ τ ( a ) കൊണ്ട് സൂചിപ്പിക്കുന്നു τ ( a ) = 1 φ ( a ) ∑ 0 ≤ b a gcd ( a , b ) = 1 T ( a , b ) .
{\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).
ഇവിടെ φ ( a ) എന്നത് a യെക്കാൾ ചെറുതും a യോട് സഹ-അഭാജ്യവുമായ സംഖ്യകളുടെ എണ്ണമാണ്, ഇതിനെ ഓയ്‌ലറുടെ ടോഷ്യന്റ് ഫലനം എന്ന് വിളിക്കുന്നു.
ഈ τ ശരാശരി a യുടെ വില വർദ്ധിക്കുന്നതിനനുസരിച്ച് ഏതാണ്ട് ക്രമമായാണ് വർദ്ധിക്കുന്നത് τ ( a ) = 12 π 2 ln ⁡ 2 ln ⁡ a + C + O ( a − 1 / 6 − ε ) .
{\displaystyle \tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon }).
ക്രമമായ വർദ്ധനവിൽ നിന്നുള്ള വ്യതിയാനം ഏതാണ്ട് a −(1/6) + ε മാത്രമാണ് (ഇവിടെ ε അനന്തസൂക്ഷ്മത്തെ സൂചിപ്പിക്കുന്നു).
സമവാക്യത്തിലെ C പോർട്ടറുടെ സ്ഥിരാങ്കം എന്നറിയപ്പെടുന്നു.
ഇതിന്റെ വില C = − 1 2 + 6 ln ⁡ 2 π 2 ( 4 γ − 24 π 2 ζ ′ ( 2 ) + 3 ln ⁡ 2 − 2 ) ≈ 1.467 {\displaystyle C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467}
ഇവിടെ γ ഓയ്‌ലർ-മസ്കരോണി സ്ഥിരാങ്കവും ζ' റീമാൻ സീറ്റ ഫലനത്തിന്റെ അവകലജവുമാണ് .
(12/π 2 ) എന്ന ആദ്യത്തെ ഗുണോത്തരം രണ്ട് സ്വതന്ത്രമായ രീതികളുപയോഗിച്ചാണ് കണ്ടുപിടിച്ചത്.
a യുടെ ഭാജകങ്ങളായ d കളെയെല്ലാം പരിഗണിച്ച് τ ശരാശരിയിൽ നിന്നും T ശരാശരി കണ്ടുപിടിക്കാം T ( a ) = 1 a ∑ d ∣ a φ ( d ) τ ( d ) {\displaystyle T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)}
താഴെ കൊടുത്തിരിക്കുന്ന സൂത്രവാക്യമുപയോഗിച്ച് ഇതിന്റെ വില ഏകദേശനം ചെയ്യാം T ( a ) ≈ C + 12 π 2 ln ⁡ 2 ( ln ⁡ a − ∑ d ∣ a Λ ( d ) d ) .
{\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\left(\ln a-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}\right).
ഇവിടെ Λ( d ) മാൻഗോൾട്ട് ഫലനമാണ് .
a , b എന്ന രണ്ട് സംഖ്യകളും 1 മുതൽ n വരെയുള്ള പൂർണ്ണസംഖ്യകളിൽ നിന്ന് തുല്യ സംഭാവ്യതയോടെ തിരഞ്ഞെടുത്ത് മൂന്നാമതൊരു രീതിയിലും ശരാശരി നിർവ്വചിക്കാം, ഇതിനെ Y ( n ) എന്ന് സൂചിപ്പിക്കുന്നു Y ( n ) = 1 n 2 ∑ a = 1 n ∑ b = 1 n T ( a , b ) = 1 n ∑ a = 1 n T ( a ) .
{\displaystyle Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).
T ( a ) യ്ക്ക് മേലെക്കൊടുത്ത ഏകദേശസൂത്രവാക്യമുപയോഗിച്ച് Y ( n ) നെയും ഏകദേശനം ചെയ്യാം Y ( n ) ≈ 12 π 2 ln ⁡ 2 ln ⁡ n + 0.06.
{\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.
} ഒരു പടിയുടെ സങ്കീർണ്ണത
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ k ആമത്തെ പടിയിൽ r k −2 , r k −1 എന്ന സംഖ്യകളുപയോഗിച്ച് q k എന്ന ഹരണഫലവും r k എന്ന ശിഷ്ടവും കണക്കാക്കുകയാണ് ചെയ്യുന്നത് r k −2 = q k r k −1 + r k .
ഹരണഫലമായ q k കണ്ടുപിടിക്കുന്നതാണ് കൂടുതൽ പ്രയാസമേറിയത്, ഇതിന്റെ വില കിട്ടിയാൽ അതുപയോഗിച്ച് ശിഷ്ടമായ r k എളുപ്പത്തിൽ കണ്ടുപിടിക്കാം r k = r k −2 − q k r k −1 .
h ബിറ്റുകളുള്ള സംഖ്യകളെ ഹരിക്കാനെടുക്കുന്ന സമയസങ്കീർണ്ണത O ( h ( ℓ +1)) ആണ് (ഇവിടെ ഹരണഫലത്തിലെ ബിറ്റുകളുടെ എണ്ണമാണ് ℓ ).
വ്യവകലനമുപയോഗിക്കുന്ന യൂക്ലിഡിന്റെ മൂല അൽഗൊരിതം ഇതിലും വളരെ മന്ദഗതിയിലുള്ളതാണ്.
ഒരു തവണ ഹരിക്കുന്നത് q തവണ വ്യവകലനം ചെയ്യുന്നതിന് തുല്യമാണല്ലോ.
a യുടെയും b യുടെയും ഹരണഫലം വളരെ വലുതാണെങ്കിൽ ഒരുപാടു തവണ വ്യവകലനം ചെയ്യേണ്ടി വരും.
എന്നിരുന്നാലും, സാധാരണഗതിയിൽ ഹരണഫലങ്ങൾ ചെറിയ സംഖ്യകളായിരിക്കും എന്ന് തെളിയിക്കാൻ സാധിക്കും.
u = ( q + 1) 2 എന്നെടുത്താൽ q ഹരണഫലമായി വരാനുള്ള സംഭാവ്യത ഏകദേശം ln| u /( u − 1)| എന്നതിനാലാണിത്.
ഹരണഫലമായി 1, 2, 3, 4 എന്ന സംഖ്യകൾ ലഭിക്കാനുള്ള സംഭാവ്യത യഥാക്രമം ഏകദേശം 41.5%, 17.0%, 9.3%, 5.9% ഇങ്ങനെയാണെന്നു കാണാം.
വ്യവകലനം ഹരണത്തെക്കാൽ സങ്കീർണ്ണത കുറഞ്ഞ സംക്രിയയായതിനാൽ (പ്രത്യേകിച്ച് വലിയ സംഖ്യകൾക്ക് ) വ്യവകലനമുപയോഗിക്കുന്ന മൂല അൽഗൊരിതത്തിന് ഹരണമുപയോഗിക്കുന്ന അൽഗൊരിതത്തോട് കിടനിൽക്കാനാകും.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ബൈനറി രൂപം ഇതിനെ അടിസ്ഥാനമാക്കിയതാണ്.
പടികളുടെ എണ്ണവും ഒരു പടി ചെയ്യാനെടുക്കുന്ന സമയവുമുപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സമയസങ്കീർണ്ണത തുടക്കത്തിലെ സംഖ്യകളിലെ ശരാശരി അക്കങ്ങളുടെ എണ്ണമായ h ന്റെ രണ്ടാംകൃതിയാണെന്ന് ( h 2 ) കാണാം.
r 0 , r 1 , …, r N −1 എന്നീ ശിഷ്ടങ്ങളുടെ അക്കങ്ങളുടെ എണ്ണം h 0 , h 1 , …, h N −1 ആണെന്നെടുക്കുക.
പടികളുടെ എണ്ണം h നോടൊപ്പം രേഖീയമായാണ് വർദ്ധിക്കുന്നത് എന്നതിനാൽ അൽഗൊരിതം എടുക്കുന്ന ആകെ സമയം O ( ∑ i N h i ( h i − h i + 1 + 2 ) ) ⊆ O ( h ∑ i N ( h i − h i + 1 + 2 ) ) ⊆ O ( h ( h 0 + 2 N ) ) ⊆ O ( h 2 ) {\displaystyle O{\Big (}\sum _{i N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2})}
ആണെന്ന് വരുന്നു.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ലാളിത്യം കാരണം അതിന് വളരെ പ്രചാരം ലഭിച്ചിട്ടുണ്ട്.
പ്രത്യേകിച്ച് ചെറിയ സംഖ്യകളുടെ ഉസാഘ കാണാൻ അൽഗൊരിതം വ്യാപകമായി ഉപയോഗിക്കപ്പെടുന്നു.
ഉസാഘ കാണാനുപയോഗിക്കുന്ന മറ്റ് രീതികളുടെ കാര്യക്ഷമത യൂക്ലിഡിന്റെ അൽഗൊരിതവുമായി താരതമ്യം ചെയ്യാം.
a , b എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനുള്ള ഒരു വഴി അവയുടെ പൊതു ഘടകങ്ങളെല്ലാം കണ്ടുപിടിക്കുകയാണ്, ഈ ഘടകങ്ങളിൽ ഏറ്റവും വലുതാണ് ഉസാഘ.
2 മുതൽ ചെറിയ സംഖ്യയായ b വരെയുള്ള എല്ലാ സംഖ്യകളെക്കൊണ്ടും ഹരിച്ചു നോക്കി പൊതു ഘടകങ്ങൾ കണ്ടുപിടിക്കാം.
ഇതിനെടുക്കുന്ന ക്രിയകളുടെ എണ്ണം b വലുതാകുന്നതിനനുസരിച്ച് രേഖീയമായും b യിലെ അക്കങ്ങളുടെ എണ്ണമനുസരിച്ച് ഘാതാങ്കമായും (exponential) വളരുന്നു.
മുകളിൽ വിവരിച്ചതുപോലെ a യുടെയും b യുടെയും പൊതുവായ അഭാജ്യ ഘടകങ്ങളുടെ ഗുണനഫലമായതിനാൽ ആ വിധത്തിലും ഉസാഘ ക്കണ്ടുപിടിക്കാം.
എന്നാൽ പൂർണ്ണസംഖ്യകളെ ഘടകക്രിയ ചെയ്യാനുള്ള അൽഗൊരിതങ്ങളും ഉയർന്ന സമയസങ്കീർണ്ണതയുള്ളവയായതിനാൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തോളം കാര്യക്ഷമമല്ല.
ഇങ്ങനെ പൂർണ്ണസംഖ്യകളെ ഘടകക്രിയ ചെയ്യൽ പ്രയാസമാണ് എന്നതാണ് പല ആധുനിക ഗൂഢാലേഖനവിദ്യകളുടെയും അടിസ്ഥാനം.
കമ്പ്യൂട്ടറിൽ ഉപയോഗിക്കുന്ന ദ്വയാങ്കസംഖ്യാവ്യവസ്ഥ അടിസ്ഥാനമാക്കി ഹരണത്തിനു പകരം കൂടുതൽ വേഗത്തിൽ ചെയ്യാവുന്ന സംക്രിയകളുപയോഗിച്ച് ഉസാഘ കാണുന്ന രീതിയാണ് ദ്വയാങ്ക ഉസാഘ അൽഗൊരിതം .
ഈ അൽഗൊരിതത്തിന്റെയും സമയസങ്കീർണ്ണത O ( h ²) ആണെങ്കിലും സാധാരണ കമ്പ്യൂട്ടറുകളിൽ അത് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കാൾ വേഗത്തിൽ ഉസാഘ കാണുന്നു.
a യുടെയും b യുടെയും ആദ്യ അക്കങ്ങൾ മാത്രം പരിശോധിച്ച് കാര്യക്ഷമത വർദ്ധിപ്പിക്കാൻ സാധിക്കും.
ഇതുപോലെ മറ്റ് സംഖ്യാവ്യവസ്ഥകളെ അടിസ്ഥാനമാക്കിയും  ( k -ary അൽഗൊരിതങ്ങൾ) ഉസാഘ കണ്ടുപിടിക്കാനുള്ള അൽഗൊരിതങ്ങൾ വികസിപ്പിക്കാം, ഇവ അഞ്ചിരട്ടി വരെ വേഗത്തിൽ ഉസാഘ കണ്ടുപിടിക്കാൻ സഹായിക്കുന്നു.
ദ്വയാങ്ക അൽഗൊരിതത്തിന്റെ പൊതു തത്ത്വങ്ങളെ അടിസ്ഥാനമാക്കി ഏത് സംഖ്യാവ്യവസ്ഥയിലും ഉസാഘ കാണാനുള്ള വേഗം കൂട്ടുന്ന അൽഗൊരിതമാണ് ലെഹ്മറുടെ ഉസാഘ അൽഗൊരിതം .
വളരെ വലിയ സംഖ്യകളുടെ (25,000 ലേറെ അക്കങ്ങൾ) ഉസാഘ കാണാനുള്ള ക്വാസിലീനിയർ അൽഗൊരിതങ്ങളുമുണ്ട്.
ഷോൺഹാഗെ, സ്റ്റെഹ്ലെ-സിമ്മെർമാൻ മുതലായവരുടെ അൽഗൊരിതങ്ങൾ ഉദാഹരണമാണ്.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മാട്രിക്സ് രീതി ആണ് ഇവയ്ക്കടിസ്ഥാനം.
ഇവയുടെ സമയസങ്കീർണ്ണത പൊതുവെ O ( h (log h ) 2 (log log h )) ആണ്.
സാമാന്യവത്കരണങ്ങൾ
സാധാരണ ഗതിയിൽ എണ്ണൽ സംഖ്യകളുടെ ഉസാഘ കാണാനാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കുന്നതെങ്കിലും വാസ്തവികസംഖ്യകൾക്കായും ബഹുപദങ്ങൾ , ദ്വിമാന പൂർണ്ണസംഖ്യകൾ , ഹുർവിറ്റ്സ് ക്വാട്ടേർണിയനുകൾ മുതലായ ഗണിതഘടനകൾക്കായും അൽഗൊരിതത്തെ സാമാന്യവത്കരിക്കാം.
ഇത്തരം ഗണിതഘടനകളിൽ അനന്യമായ ഘടകക്രിയ സാധ്യമാണ് എന്ന് തെളിയിക്കാൻ അൽഗൊരിതം ഉപയോഗിക്കുന്നു.
അതായത്, ഘടനയിലെ അംഗങ്ങളെ അച്ഛേദ്യമായ അംഗങ്ങളാക്കി (ഘടനയിൽ അഭാജ്യസംഖ്യകൾക്ക് സമാനമായ അംഗങ്ങളാണിവ) ഘടകക്രിയ നടത്താൻ ഒരു വഴിയേ ഉള്ളൂ എന്ന് തെളിയിക്കാം.
സംഖ്യാസിദ്ധാന്തത്തിലെ പല തെളിവുകളുടെയും അടിസ്ഥാനം അനന്യമായ ഘടകക്രിയയാണ്.
ഭിന്നകസംഖ്യകളും വാസ്തവികസംഖ്യകളും
യൂക്ലിഡ് എലിമെന്റ്സിലെ പത്താം പുസ്തകത്തിൽ വിവരിച്ചതുപോലെ വാസ്തവികസംഖ്യകൾക്കും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം.
a , b എന്ന വാസ്തവികസംഖ്യകളിൽ നിന്നും ഇവ പൂർണ്ണസംഖ്യാഗുണിതങ്ങളായി വരുന്ന g എന്ന വാസ്തവികസംഖ്യ കാണുകയാണ് അൽഗൊരിതത്തിന്റെ ലക്ഷ്യം.
അതായത്, a = mg , b = ng എന്ന സമവാക്യങ്ങൾ ശരിയായി വരുകയും m , n എന്നിവ പൂർണ്ണസംഖ്യകളാവുകയും വേണം.
a യുടെയും b യുടെയുമിടയിൽ ഒരു പൂർണ്ണസംഖ്യാബന്ധം (integer relation) കണ്ടുപിടിക്കുന്നതിനു തുല്യമാണിത്; അതായത്, sa + tb = 0 എന്ന സമവാക്യമനുസരിക്കുന്ന s , t എന്ന പൂർണ്ണസംഖ്യകൾ കണ്ടുപിടിക്കുക.
രണ്ട് നീളങ്ങൾ സാനുപാതമാണോ എന്ന ചോദ്യത്തിനുത്തരമായാണ് യൂക്ലിഡ് ഈ രീതി വികസിപ്പിച്ചത്.
വാസ്തവികസംഖ്യകൾക്കു മേൽ യൂക്ലിഡിന്റെ അൽഗൊരിതം പ്രയോഗിക്കുന്നതിൽ പൂർണ്ണസംഖ്യകളുടെ അൽഗൊരിതവുമായി രണ്ടു വ്യത്യാസങ്ങൾ കാണാം.
ഹരണഫലങ്ങളായ q k മുമ്പത്തെപ്പോലെ പൂർണ്ണസംഖ്യകളാണെങ്കിലും ശിഷ്ടങ്ങളായ r k വാസ്തവികസംഖ്യകളാണ് എന്നതാണ് ആദ്യത്തെ വ്യത്യാസം.
അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണം പരിമിതമല്ല എന്നതാണ് രണ്ടാമത്തേത്.
N പടികളോടെ അൽഗൊരിതം അവസാനിക്കുക a / b ഭിന്നകസംഖ്യയാകുമ്പോൾ (അതായത്, രണ്ടു പൂർണ്ണസംഖ്യകളുടെ അനുപാതം‌) മാത്രമാണ്, a b = m g n g = m n .
{\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}}.
ഇങ്ങനെ വരുമ്പോൾ ഈ ഭിന്നത്തെ [ q 0 ; q 1 , q 2 , ..., q N ] എന്നിങ്ങനെ ഒരു പരിമിത സതതഭിന്നമായി എഴുതാനാകും.
അൽഗൊരിതം അവസാനിക്കുന്നില്ലെങ്കിൽ a / b ഒരു അഭിന്നകസംഖ്യയായിരിക്കും , അതിന്റെ സതതഭിന്നമായ [ q 0 ; q 1 , q 2 , …] അനന്തവും.
ഇങ്ങനെ അനന്തമായ സതതഭിന്നങ്ങൾക്ക് ഉദാഹരണമാണ് സുവർണ്ണാനുപാതവും ( φ = [1; 1, 1, ...] ) രണ്ടിന്റെ വർഗ്ഗമൂലവും ( √ 2 = [1; 2, 2, ...] ‌).
a / b എന്ന വാസ്തവികസംഖ്യകളുടെ അനുപാതങ്ങൾ ഏതാണ്ടെല്ലാം തന്നെ അഭിന്നകങ്ങളായതിനാൽ അൽഗൊരിതം അവസാനിക്കാതിരിക്കാനാണ് കൂടുതൽ സാധ്യത.
അനന്തമായ സതതഭിന്നത്തെ k പടികൾക്കു ശേഷം മുറിക്കാം.
ഇങ്ങനെ ലഭിക്കുന്ന [ q 0 ; q 1 , q 2 , ..., q k ] എന്ന പരിമിത സതതഭിന്നം a / b യുടെ ഏകദേശവില നൽകുന്നു.
k യുടെ വില വർദ്ധിക്കുന്നതിനനുസരിച്ച് ഈ ഏകദേശനം കൂടുതൽ കൃത്യമായി വരുന്നു.
k ആമത്തെ പടിയിലെ ഏകദേശവില m k / n k ആണ്, ഈ അനുക്രമത്തെ അഭിസാരി (convergent) എന്നു വിളിക്കുന്നു.
ഈ ഭിന്നത്തിലെ അംശവും ഛേദവും സഹ-അഭാജ്യമായ പൂർണ്ണസംഖ്യകളാണ്, ഇവ താഴെക്കൊടുത്തിരിക്കുന്ന ആവർത്തനബന്ധം അനുസരിക്കുന്നു, m k = q k m k − 1 + m k − 2 n k = q k n k − 1 + n k − 2 .
{\displaystyle {\begin{aligned}m_{k} =q_{k}m_{k-1}+m_{k-2}\\n_{k} =q_{k}n_{k-1}+n_{k-2}.
m −1 = n −2 = 1 , m −2 = n −1 = 0 എന്ന അടിസ്ഥാനവിലകളോടെയാണ് ആവർത്തനബന്ധം ആരംഭിക്കുന്നത്.
m k / n k എന്ന അഭിസാരി a / b യെ ഏകദേശനം ചെയ്യുന്ന ഭിന്നകങ്ങളിൽ ഛേദം n k ആയുള്ളവയിൽ വച്ച് ഏറ്റവും കൃത്യമായിരിക്കും: | a b − m k n k | 1 n k 2 .
{\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right| {\frac {1}{n_{k}^{2}}}.
} ബഹുപദങ്ങൾ
ഒരു ചരത്തിനുമേലുള്ള ( x എന്നെടുക്കുക) ബഹുപദങ്ങളെ കൂട്ടുകയും ഗുണിക്കുകയും ചെയ്യുന്നതിനു പുറമെ അവയെ അച്ഛേദ്യ ബഹുപദങ്ങളുടെ (അഭാജ്യസംഖ്യകൾക്ക് സമാനമായ അംഗങ്ങളാണിവ) ഗുണനഫലമായി എഴുതാനും സാധിക്കും.
a ( x ) , b ( x ) എന്ന ബഹുപദങ്ങളുടെ പൊതുവായ അച്ഛേദ്യ ബഹുപദ ഘടകങ്ങളുടെ ഗുണനഫലമാണ് അവയുടെ ബഹുപദ ഉസാഘയായ g ( x ) .
യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് ബഹുപദ ഉസാഘ കണ്ടുപിടിക്കാം.
പൂർണ്ണസംഖ്യകളൂടെ അൽഗൊരിതത്തിന് സമാനമായാണ് ഇവിടെയും ഉസാഘ കാണുന്നത്.
k ആമത്തെ പടിയിൽ ഹരണഫലമായ q k ( x ) എന്ന ബഹുപദവും r k ( x ) എന്ന ശിഷ്ട ബഹുപദവും കണ്ടുപിടിക്കുന്നു.
ഇവ താഴെക്കൊടുത്തിരിക്കുന്ന ആവർത്തനബന്ധം അനുസരിക്കുന്നു, r k − 2 ( x ) = q k ( x ) r k − 1 ( x ) + r k ( x ) .
{\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x).
r −2 ( x ) = a ( x ) , r −1 ( x ) = b ( x ) എന്ന വിലകളോടെയാണ് അൽഗൊരിതം ആരംഭിക്കുന്നത്.
q k ( x ) r k −1 ( x ) ന്റെ ആദ്യത്തെ പദം r k −2 ( x ) ന്റെ ആദ്യത്തെ പദത്തിന് തുല്യമാവുന്ന തരത്തിലാണ് ഹരണഫലം കാണുന്നത്.
ഓരോ പടിയിലും ഹരണഫല ബഹുപദത്തിന്റെ കൃതി കുറഞ്ഞുവരുമെന്ന് ഇത് ഉറപ്പുവരുത്തുന്നു.
: deg[ r k ( x )] deg[ r k −1 ( x )] .
ബഹുപദങ്ങളുടെ കൃതി ഒരിക്കലും പൂജ്യത്തിൽ കുറവാവുകയില്ല എന്നതിനാൽ അൽഗൊരിതം പരിമിത എണ്ണം പടികൾക്കു ശേഷം അവസാനിക്കും.
ഏറ്റവുമൊടുവിൽ ലഭിക്കുന്ന പൂജ്യമല്ലാത്ത ശിഷ്ടമാണ് a ( x ) ന്റെയും b ( x ) ന്റെയും ഉസാഘ.
ഉദാഹരണമായി, താഴെ കൊടുത്തിരിക്കുന്ന നാലം കൃതി ബഹുപദങ്ങളുടെ (ഇവയുടെ ഘടകക്രിയ കൊടുത്തിരിക്കുന്നു) ഉസാഘ കാണുന്നതെങ്ങനെയെന്നു നോക്കാം a ( x ) = x 4 − 4 x 3 + 4 x 2 − 3 x + 14 = ( x 2 − 5 x + 7 ) ( x 2 + x + 2 ) and b ( x ) = x 4 + 8 x 3 + 12 x 2 + 17 x + 6 = ( x 2 + 7 x + 3 ) ( x 2 + x + 2 ) .
{\displaystyle {\begin{aligned}a(x) =x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x) =x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).
a ( x ) നെ b ( x ) കൊണ്ടു ഹരിച്ചാൽ ശിഷ്ടം r 0 ( x ) = x 3 + (2/3) x 2 + (5/3) x − (2/3) ലഭിക്കുന്നു.
അടുത്ത പടിയിൽ b ( x ) നെ r 0 ( x ) കൊണ്ട് ഹരിച്ച് ശിഷ്ടം r 1 ( x ) = x 2 + x + 2 ലഭിക്കുന്നു.
രണ്ടാമത്തെ പടിയിൽ ശിഷ്ടത്തിന്റെ കൃതി കുറഞ്ഞതു കാണാം.
ഒടുവിൽ r 0 ( x ) നെ r 1 ( x ) കൊണ്ടു ഹരിച്ചാൽ ശിഷ്ടം വരില്ലെന്നും അതിനാൽ a ( x ) ന്റെയും b ( x ) ന്റെയും ഉസാഘ r 1 ( x ) ആണെന്നും കാണാം.
ബഹുപദങ്ങളെ ഘടകക്രിയ ചെയ്തപ്പോൾ ലഭിച്ച പൊതു ഘടകം തന്നെയാണിത്.
പൂർണ്ണസംഖ്യകളുടെ അൽഗൊരിതത്തിന്റെ മേൽ വിവരിച്ച ഉപയോഗങ്ങളിൽ പലതും ബഹുപദങ്ങൾക്കും ഉപയോഗിക്കാം.
ബഹുപദങ്ങളുടെ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാനും ചൈനീസ് ശിഷ്ട പ്രമേയത്തിനും അൽഗൊരിതം ഉപയോഗിക്കാം, ബഹുപദങ്ങളുടെ സതതഭിന്നങ്ങൾ നിർവചിക്കുകയും ചെയ്യാം.
ബഹപദങ്ങളുടെ യൂക്ലിഡിയൻ അൽഗൊരിതത്തിന് വേറെയും ഉപയോഗങ്ങളുണ്ട്.
ഒരു ബഹുപദ സമവാക്യത്തിന് ഏതെങ്കിലും ഇടവേയിൽ നിർദ്ധാരണം കാണാൻ സഹായിക്കുന്ന സ്റ്റുർമ് ശൃംഖല ഇതിനെ അടിസ്ഥാനമാക്കിയതാണ്.
കണ്ട്രോൾ തിയറി യിലെ റൂത്ത്-ഹുർവിറ്റ്സ് സ്ഥിരത മാനദണ്ഡത്തിൽ സ്റ്റുർമ് ശൃംഖല ഉപയോഗിക്കുന്നു.
യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാൻ ബഹുപദങ്ങളുടെ ഗുണോത്തരങ്ങൾ പൂർണ്ണസംഖ്യകളോ വാസ്തവികസംഖ്യകളോ മിശ്രസംഖ്യകൾ പോലുമോ ആകണമെന്ന് നിർബന്ധമില്ല.
മേൽ വിവരിച്ച പരിമിത ക്ഷേത്രങ്ങൾ ( GF( p ) ) പോലുള്ള ഏതെങ്കിലും ക്ഷേത്രത്തിലെ അംഗങ്ങൾ ഗുണോത്തരങ്ങളായ ബഹുപദങ്ങൾക്കുമേലും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം.
പൂർണ്ണസംഖ്യകൾക്കു മേൽ അൽഗൊരിതം പ്രയോഗിക്കുന്നതിനെക്കുറിച്ച് മേലെ പറഞ്ഞതെല്ലാം ഇത്തരം ബഹുപദങ്ങളുടെ കാര്യത്തിലും ശരിയായി വരുന്നു..
ഗോസിയൻ പൂർണ്ണസംഖ്യകൾ u 2 + v 2 ന്റെ വില 500ൽ കുറവുള്ള ഗോസിയൻ അഭാജ്യസംഖ്യകൾ ( u + vi )
α = u + vi എന്ന രൂപത്തിൽ എഴുതാവുന്ന മിശ്രസംഖ്യകളാണ് ഗോസിയൻ പൂർണ്ണസംഖ്യകൾ .
ഇവിടെ u , v എന്നിവ സാധാരണ പൂർണ്ണസംഖ്യകളും i എന്നത് -1 ന്റെ വർഗ്ഗമൂലവുമാണ് .
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ പരിഷ്കരിച്ച രൂപമുപയോഗിച്ച് മുകളിൽ വിവരിച്ച രീതിയിൽ ഗോസിയൻ പൂർണ്ണസംഖ്യകളുടെ ഘടകക്രിയ അനന്യമാണെന്ന് തെളിയിക്കാനാകും..
എല്ലാ പൈതഗോറിയൻ ത്രയങ്ങളും കണ്ടുപിടിക്കാനും ഫെർമയുടെ രണ്ടു വർഗ്ഗ പ്രമേയം തെളിയിക്കാനും ഘടകക്രിയയുടെ അനന്യത ഉപയോഗിക്കാം.
എന്നിരുന്നാലും, യൂക്ലിഡിയൻ അൽഗൊരിതത്തിന്റെ സഹായം കൂടാതെ തന്നെ മറ്റു വഴികളിലും ഇത്തരം പ്രമേയങ്ങൾ തെളിയിക്കാവുന്നതാണ്.
α , β എന്ന ഗോസിയൻ പൂർണ്ണസംഖ്യകളുടെ ഉസാഘ കാണാനുള്ള അൽഗൊരിതം സാധാരണ പൂർണ്ണസംഖ്യകൾക്കായുള്ള അൽഗൊരിതത്തിന് വളരെ സമാനമാണെങ്കിലും രണ്ട് വ്യത്യാസങ്ങളുണ്ട്.
മുമ്പത്തെപ്പോലെത്തന്നെ അൽഗൊരിതത്തിന്റെ k ആമത്തെ പടിയിൽ താഴെ കൊടുത്തിരിക്കുന്ന ആവർത്തനബന്ധമനുസരിക്കുന്ന q k എന്ന ഹരണഫലവും r k എന്ന ശിഷ്ടവും കണ്ടുപിടിക്കുകയാണ് ലക്ഷ്യം, r k = r k − 2 − q k r k − 1 .
{\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1}.