how to find (efficiently) binary expansion of a square root of a number which is given as a binary number. Is there any general method to find the n-nary expansion of m-th root of a number which is given in its n-nary expansion. I hope n-nary is the term used to say a number is represented in the base n.
$\endgroup$ 61 Answer
$\begingroup$Either use a numerical method (like Newton's) to solve $x^n - a = 0$ (starting points could be estimated roughly, or given by a table), or use a CORDIC algorithm for digit-by-digit computation. Newton himself used the binomial expansion of $(1 + x)^{1/2}$ judiciously.
If you have the luxury of being able to precompute, a table and interpolation could serve. Or perhaps cook up a polynomial or rational approximation for the range of interest.
In either case range reducing transformations (e.g. reduce $\sin$ to the range 0 to $\dfrac{\pi}{2}$ by periodicity and other equivalences, or e.g. $\sqrt{8} = 2 \sqrt{2}$) should be applied first.
$\endgroup$ 4
