integer nth root

x' is the nth root of y if x' is the largest integer such that x^n <= y. x, x' and y are all integers. Is there any efficient way to compute such nth root? I know this is usually done by nth root algorithm, but the difficulty here is everything is integer because I'm working with an embedded system.

BTW, I've even tried to binary search from 1 to y to identify largest x such that x^n <= y, but it does not work s开发者_Go百科ince x^n overflows easily especially when n is large.

Store a table for given y of the maximum x such that x^y does not overflow. Use these values for binary search; that way, no more overflow and a neat algorithm that will work as long as x and n have the same (integer) type. Right?

Note: for y > 32, the maximum value for x is 2 for 32-bit integers... in other words, your table will be the same size as the number of bits in integers your system understands, approximately.

Are you looking for integer roots only? Or do you want to know that the 5th root of 34 is 2.024...? Or is "2" a sufficient answer? If you want the decimal places, you'll have to do some kind of floating point or fixed point math.

You should read Computing principal roots, and note what it says about the first Newton approximate. If an error of about 0.03% is close enough, I'd suggest you go with this. You'd probably want to build a table that you can use to do the initial approximations. This table isn't as large as it sounds. The cube root of 2^32 is only about 1,626. You can easily compute the squares, and it's easy to generate x^n if you can generate x^2 and x^3. So doing the approximations is pretty easy.

Another possibility is to build yourself a table of roots and use some kind of interpolation. Again, that table wouldn't have to be very large if you treat the square root as a special case. The 5th root of 2^32 is less than 100, so you're talking a pretty small table to get a pretty large range of roots.

I think the best method is to use the Newton-Raphson method from the Wikipedia article.

A good starting value can be computed from the bit length of the input divided by n. In each iteration you use integer division that rounds down. Iterate until you have found a value x such that x^n <= y < (x+1)^n.

You have to be careful to avoid overflow. As the other answer says, you can use a table of the maximal root for n < bit size to do that (for greater n the answer is always 1, except for y = 0).