  the shifting nth root algorithm is an algorithm for extracting the nth root of a positive real number which proceeds iteratively by shifting in n digits of the radicand, starting with the most significant, and produces one digit of the root on each iteration, in a manner similar to long division. ==algorithm== ===notation=== let b be the base of the number system you are using, and n be the degree of the root to be extracted. let x be the radicand processed thus far, y be the root extracted thus far, and r be the remainder. let Î± be the next n digits of the radicand, and Î² be the next digit of the root. let x be the new value of x for the next iteration, y be the new value of y for the next iteration, and r be the new value of r for the next iteration. these are all integers. ===invariants=== at each iteration, the invariant y^n + r = x will hold. the invariant (y+1)^n>x will hold. thus y is the largest integer less than the nth root of x, and r is the remainder. ===initialization=== the initial values of x, y, and r should be 0. the value of Î± for the first iteration should be the most significant aligned block of n digits of the radicand. an aligned block of n digits means a block of digits aligned so that the decimal point falls between blocks. for example, in 123.4 the most significant aligned block of 2 digits is 01, the next most significant is 23, and the third most significant is 40. ===main loop=== on each iteration we shift in n digits of the radicand, so we have x' = b^n x + \alpha and we produce 1 digit of the root, so we have y' = b y + \beta . we want to choose Î² and r so that the invariants described above hold. it turns out that there is always exactly one such choice, as will be proved below. the first invariant says that: :x' = y'^n + r' or :b^n x + \alpha = (b y + \beta)^n + r'. so, pick the largest integer Î² such that :(b y + \beta)^n \le b^n x + \alpha and let :r' = b^n x + \alpha - (b y + \beta)^n. such a Î² always exists, since if \beta = 0 then the condition is b^n y^n \le b^n x + \alpha, but y^n \le x, so this is always true. also, Î² must be less than b, since if \beta = b then we would have :(b(y+1))^n \le b^n x + \alpha\, but the second invariant implies that :b^n x < b^n (y+1)^n\, and since b^n x and b^n (y+1)^n are both multiples of b^n the difference between them must be at least b^n, and then we have :b^n x + b^n \le b^n (y+1)^n\, :b^n x + b^n \le b^n x + \alpha\, :b^n \le \alpha\, but 0 \le \alpha < b^n by definition of Î±, so this can't be true, and (b y + \beta)^n is a monotonically increasing function of Î², so it can't be true for larger Î² either, so we conclude that there exists an integer Î³ with \gamma<b such 
Computer_arithmetic_algorithms Root-finding_algorithms