So to find a root we could use newtons method which is pick a random x0 starting point, then x(n-1) is NOT x times (n-1) it is the (n-1)th x value
xn = x(n-1) + f(x(n-1))/f'(x(n-1))
Want to solve root(c) is solving the equation x^2-c for roots and the derivative of this is 2x.
xn = x(n-1) + (x(n-1)^2 - c)/(2x(n-1))
From stack overflow, some guy just posted "from c decimal places, you will need log(c) iterations" which seems to be the exact complexity of this.
Another way of finding roots is through the continued fractions. With these you find your best (good enough) approximation after you hit the first value 2*d or right when it starts repeating. This (I think) has an upper bound of log(n) or sqrt(n) not totally sure. The thing is this way you still need to calculate the continued fraction in the first place which would take some time so I bet you go with the first one above.