Is it possible to compute the nth root using the non-restoring SQRT-algorithm?

Question

My professor said that it's possible to compute the nth-root using the non-restoring SQRT-algorithm:

https://www.researchgate.net/figure/The-example-of-restoring-algorithm-to-solve-square-root_fig1_274631135)

when combining it with binomial expansion.

I am completely at a loss what he was getting at. In my opinion, it's not possible (unless by completely bastardizing the algorithm). Unfortunately, I can't reach him right now.

Is it possible to do that, or have I just misheard him?

Answer 1

if I see it right your restoring algorithm is computing integer division a/b...

integer n-th root is computing a^(1/b) the usual ways are either using log,exp approach and round/truncate or binary search along with power a^b

for more info see:

• Power by squaring for negative exponents

Yes you can use division instead but unless I miss something it would be very inefficient.

simply binary search a / (answer^(b-1)) >= answer

the answer limit will be 2^(log2(a)/b) so just find the min power of 2 which is >= a and use b times less bits ...

you could probably optimize this by ignore answers that are multiple of already rejected answer and or use some modular arithemic trick related to GCD or something where binomal expansion might come be handy... My intuition tells me you would end up with prime decomposition and just check if the exponents are all b or the same multiple of b ...

So in my opinion its possible but its too much work with most likely much worse performance than simple approaches mentioned before unless I missing something ...

Answer 2

I think you are misunderstanding what the professor is saying. They're not saying that you can use the square root algorithm to find an arbitrary nth root. Rather that there exists an algorithm similar to the non-restoring square-root algorithm in spirit that can be used to compute other roots. These algorithms calculate the root one digit at a time.

Let's take the nth root. As I describe the algorithm, think of how it works with square root:

You take the digits and put them into groups of n. The decimal point should be between two groups. Find the leftmost non-zero group. Put a "1" above that group, indicating the current "result" is 1, and subtract 1 from it.

Repeatedly:

1. Add another group of n digits from above down to your running subtraction.
2. Calculate a value f(result), where result is the answer so far. For square root, it's 4*result + 1. If this value is ≥ your running subtraction, subtract f(result) and add a 1 to the end of result. (result := 2 * result + 1). Otherwise, add a 0 to the end of the result. (result := 2 * result)

The function f is just (2 * result + 1)** n - (2 * result)**n

Answer 3

My professor cleared it up for me.

There exists indeed a non-restoring square root algorithm (they call it variant 2 in my university) that can be easily extended for nth roots.

You need to substract the square of the divisor from the dividend, and check whether the result is positive or negative.

If you want to use it for the nth root, you need to substract dividend^n. That's it. So you substract the cube of the dividend if you're searching for the 3th root.

Here's an example of finding the square root of 127, the result ist 11:

Here's an example of finding the third root of 127, the result is 5: