Menu
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 since x^n overflows easily especially when n is large.
809
In mathematics, an nth root of a number x is a number r which, when raised to the power n, yields x: where n is a positive integer, sometimes called the degree of the root. A root of degree 2 is called a square root and a root of degree 3, a cube root.
n th Roots Example: √49=7 , because 72=49 . Similarly, the cube root of a number b , written 3√b , is a solution to the equation x3=b . Example: 3√64=4 , because 43=64 . More generally, the nth root of b , written n√b , is a number x which satisfies xn=b .
N th root of a number K is a root of the function f(x) = x^N - K .
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.
62
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
