The two classic algorithms for square root, sqrt, are shown below. The first is the iterative approximation algorithm, followed by the sequential algorithm modeled after the non restoring binary divide algorithm. The basic theory is shown in the final decimal example. To compute y = sqrt(x) (x>=0, iterative quadratic convergence) if x = 0 then return x (IEEE, math: return 0) y = 1.0 (any reasonable guess>0) y1 = 0 while abs(y-y1)>tolerance (any reasonable tolerance>0) y1 = y y = (y + x/y)/2 end while return y To compute y = sqrt(x) (x>=0 demonstrated in binary) 1 0 1 let x=11010 26 decimal +--------- choose 1 squared, subtract, keep if positive ) 01 10 10 shift two bits at a time -01 subtract guess squared ------ 0 10 -1 01 sqrt so far with 01 appended -------- no subtract because result would be negative 10 10 -10 01 sqrt so far with 01 appended ------ 1 In digital logic, the sqrt algorithm for n-bit numbers: requires n/2 sequential steps or requires n/2 parallel subtractors In decimal from www.dattalo.com/technical/theory/sqrt.html 1 7 7. 2 ------------- ) 03 14 15.92 -01 square 1*1 ------ 1*20 = 20 (20 is base ten times 2) 2 14 need x (20+x)*x<214 x=7 -1.89 (20+7)*7=189 ------- so far, 17*20 = 340 25 15 need (340+x)*x<2515 x=7 -24 29 (340+7)7*7=2429 ------- so far, 177*20 = 3540 86 92 need (3540+x)*x<8692 x=2 -70 84 (3540+2)*2=7084 ----- 16 08 (Note that the binary is easier because 20 becomes 4, a two place shift, and x is always tested as a 1, 01 positionally)