Integer n-th root

Question

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

By the way, I even tried a binary search from 1 to y to determine the largest x, such that x ^ n <= y, but it does not work, because x ^ n overflows easily, especially when n is large.

Answer 1

Keep a table for the given y maximum x so that x ^ y does not overflow. Use these values ​​for binary search; Thus, there is no more overflow and a neat algorithm that will work as long as x and n are of 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 that your system understands approximately.

Answer 2

Are you looking for whole roots only? Or do you want to know that the 5th root of 34 is 2.024 ...? Or is "2" enough answer? If you need decimal places, you will need to do some math with floating point or fixed point.

You should read Calculate the main roots and note that he speaks of Newton's first approximation. If the error of about 0.03% is close enough, I would suggest you go with that. You probably want to create a table that you can use for initial approximations. This table is not as big as it seems. The cube root of 2 ^ 32 is only about 1626. You can easily calculate the squares, and it is easy to generate x ^ n if you can generate x ^ 2 and x ^ 3. Thus, the approximation is quite simple.

Another possibility is to build yourself a table of roots and use some kind of interpolation. Again, this table does not have to be very large if you consider the square root as a special case. The 5th root of 2 ^ 32 is less than 100, so you say a fairly small table to get a fairly large range of roots.

Answer 3

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

A good initial value can be calculated from the input bit length divided by n . At each iteration, you use integer division, which is rounded down. Iterate until you find a value x such that x^n <= y < (x+1)^n .

You must be careful to avoid overflow. As another answer says, you can use the maximum root table for n < bit size for this (for larger n answer is always 1 , except for y = 0 ).