Кіріспе
Жылжымалы n-ші түбір алгоритмі – оң нақты санның n-ші түбірін табу алгоритмі. Бұл алгоритм радикалдың цифрларын ең маңыздысынан бастап, n цифрдан қайта-қайта қосып, ұзақ бөлуге ұқсас әр итерацияда түбірдің бір цифрын шығарады.
Нөмірлік
Сіз қолданатын сандық жүйенің негізі болсын, ал ізделінетін тамырдың дәрежесі болсын. Осы уақытқа дейін өңделген радикант, осы уақытқа дейін алынған тамыр және қалдық болсын. Келесі радиканттың цифрлары болсын, ал келесі тамырдың цифры болсын. Келесі итерациядағы жаңа мән болсын, келесі итерациядағы жаңа мән болсын, және келесі итерациядағы жаңа мән болсын. Бұлардың бәрі бүтін сандар.
Өзгермейтіндер
Әр итерацияда инвариант орындалады. Инвариант орындалады. Осылайша, – бұл санның th түбірінен кем немесе тең болатын ең үлкен бүтін сан, ал – қалдық.
Бастапқылау
, және бастапқы мәндері 0 болуы керек. Бірінші итерация үшін a мәні радикалдың ең маңызды сәйкестендірілген цифрлар блогы болуы керек. Сәйкестендірілген цифрлар блогы – ондық нүкте блоктар арасында орналасуы үшін реттелген цифрлар тобы. Мысалы, 123.4 санында екі цифрдан тұратын ең маңызды сәйкестендірілген блок – 01, одан кейінгісі – 23, ал үшіншісі – 40.
Өнер көрсету
Әрбір итерацияда ең көп уақытты алатын міндет – таңдау. Біз мүмкін мәндердің бар екенін білеміз, сондықтан біз салыстыруларды қолдана отырып анықтай аламыз. Әрбір салыстыруда бағалау қажет болады. k-шы итерацияда сан өте цифрдан тұрады, ал полином өте цифрға дейін көбейту және өте цифрға дейін қосу арқылы бағаланады, егер біз және күштерін білсек және үшін және үшін. шектелген диапазоны бар, сондықтан біз тұрақты уақытта күштерін ала аламыз. Біз өте цифрға дейін көбейту арқылы күштерін ала аламыз. Егер цифрды көбейту уақытты, ал қосу уақытты алса, онда әрбір салыстыру үшін уақыт кетеді, немесе таңдау үшін уақыт кетеді. Алгоритмнің қалған бөлігі – қосу және алу, ол уақытты алады, сондықтан әрбір итерация уақытты алады. Барлық цифрлар үшін бізге уақыт қажет. Бұл алгоритмнің шектелген жадты пайдалануы болмауы, арифметиканың қарапайым алгоритмдерінен айырмашылығы, саналы түрде есептеуге болатын цифрлар санына жоғарғы шек қояды. Өкінішке орай, кез келген периодтық кіріспен шектелген жадты күй машинасы тек периодтық шығыстарды ғана шығара алады, сондықтан рационалды сандардан иррационалды сандарды есептейтін мұндай алгоритмдер жоқ, демек, шектелген жадты түбір табу алгоритмдері де жоқ. Базаны ұлғайту таңдауға қажетті уақытты фактормен арттырады, бірақ берілген дәлдікке жету үшін қажетті цифрлар санын сол фактормен азайтады, ал алгоритм цифрлар санының кубикалық уақытында жұмыс істейтіндіктен, базаны ұлғайту жалпы жылдамдықты арттырады. Егер база радикандтан үлкен болса, алгоритм екілік іздеуге дейін төмендейді, сондықтан бұл алгоритм компьютерде түбірлерді есептеу үшін пайдалы емес, өйткені ол әрқашан әлдеқайда қарапайым екілік іздеуден нашар орындалады және жадтың күрделілігі бірдей.
for each comparison, or time to pick The remainder of the algorithm is addition and subtraction that takes time , so each iteration takes For all digits, we need time
The only internal storage needed is , which is digits on the kth iteration. That this algorithm does not have bounded memory usage puts an upper bound on the number of digits which can be computed mentally, unlike the more elementary algorithms of arithmetic. Unfortunately, any bounded memory state machine with periodic inputs can only produce periodic outputs, so there are no such algorithms which can compute irrational numbers from rational ones, and thus no bounded memory root extraction algorithms. Note that increasing the base increases the time needed to pick by a factor of , but decreases the number of digits needed to achieve a given precision by the same factor, and since the algorithm is cubic time in the number of digits, increasing the base gives an overall speedup of When the base is larger than the radicand, the algorithm degenerates to binary search, so it follows that this algorithm is not useful for computing roots with a computer, as it is always outperformed by much simpler binary search, and has the same memory complexity.