CODEWITHSUNDEEP
calgorithmmath
user567879
user567879

Reputation: 5349

Algorithm to find nth root of a number

I am looking for an efficient algorithm to find nth root of a number. The answer must be an integer. I have found that newtons method and bisection method are popular methods. Are there any efficient and simple methods for integer output?

Upvotes: 15

Views: 46482

Answers (5)

Michel
Michel

Reputation: 349

You can try this C function to get the nth_root of an unsigned integer :

unsigned initial_guess_nth_root(unsigned n, unsigned nth){
    unsigned res = 1;
    for(; n >>= 1; ++res);
    return nth ? 1 << (res + nth - 1) / nth : 0 ;
}

// return a number that, when multiplied by itself nth times, makes N.
unsigned nth_root(const unsigned n, const unsigned nth) {
    unsigned a = initial_guess_nth_root(n , nth), b, c, r = nth ? a + (n > 0) : n == 1 ;
    for (; a < r; b = a + (nth - 1) * r, a = b / nth)
        for (r = a, a = n, c = nth - 1; c && (a /= r); --c);
    return r;
}

Example of output :

  24 == (int) pow(15625, 1.0/3)

  25 == nth_root(15625, 3)
   0 == nth_root(0, 0)
   1 == nth_root(1, 0)
   4 == nth_root(4096, 6)
  13 == nth_root(18446744073709551614, 17) // 64-bit 20 digits
  11 == nth_root(340282366920938463463374607431768211454, 37) // 128-bit 39 digits

Here is the github source.

Upvotes: 1

Todd Lehman
Todd Lehman

Reputation: 2950

Here is an efficient general implementation in C, using a simplified version of the "shifting nth root algorithm" to compute the floor of the nth root of x:

uint64_t iroot(const uint64_t x, const unsigned n)
{
  if ((x == 0) || (n == 0)) return 0;
  if (n == 1) return x;

  uint64_t r = 1;
  for (int s = ((ilog2(x) / n) * n) - n; s >= 0; s -= n)
  {
    r <<= 1;
    r |= (ipow(r|1, n) <= (x >> s));
  }

  return r;
}

It needs this function to compute the nth power of x (using the method of exponentiation by squaring):

uint64_t ipow(uint64_t x, unsigned n)
{
  if (x <= 1) return x;

  uint64_t y = 1;
  for (; n != 0; n >>= 1, x *= x)
    if (n & 1)
      y *= x;
  return y;
}

and this function to compute the floor of base-2 logarithm of x:

int ilog2(uint64_t x)
{
  #if __has_builtin(__builtin_clzll)
    return 63 - ((x != 0) * (int)__builtin_clzll(x)) - ((x == 0) * 64);
  #else
    int y = -(x == 0);
    for (unsigned k = 64 / 2; k != 0; k /= 2)
      if ((x >> k) != 0)
        { x >>= k; y += k; }
    return y;
  #endif
}

Note: This assumes that your compiler understands GCC's __has_builtin test and that your compiler's uint64_t type is the same size as an unsigned long long.

Upvotes: 1

guest
guest

Reputation: 119

I know this thread is probably dead, but I don't see any answers I like and that bugs me...

int root(int a, int n) {
    int v = 1, bit, tp, t;
    if (n == 0) return 0; //error: zeroth root is indeterminate!
    if (n == 1) return a;
    tp = iPow(v,n);
    while (tp < a) {    // first power of two such that v**n >= a
        v <<= 1;
        tp = iPow(v,n);
    }
    if (tp == a) return v;  // answer is a power of two
    v >>= 1;
    bit = v >> 1;
    tp = iPow(v, n);    // v is highest power of two such that v**n < a
    while (a > tp) {
        v += bit;       // add bit to value
        t = iPow(v, n);
        if (t > a) v -= bit;    // did we add too much?
        else tp = t;
        if ( (bit >>= 1) == 0) break;
    }
    return v;   // closest integer such that v**n <= a
}
// used by root function...
int iPow(int a, int e) {
    int r = 1;
    if (e == 0) return r;
    while (e != 0) {
        if ((e & 1) == 1) r *= a;
        e >>= 1;
        a *= a;
    }
    return r;
}

This method will also work with arbitrary precision fixed point math in case you want to compute something like sqrt(2) to 100 decimal places...

Upvotes: 11

rubenvb
rubenvb

Reputation: 76785

#include <math.h>
inline int root(int input, int n)
{
  return round(pow(input, 1./n));
}

This works for pretty much the whole integer range (as IEEE754 8-byte doubles can represent the whole 32-bit int range exactly, which are the representations and sizes that are used on pretty much every system). And I doubt any integer based algorithm is faster on non-ancient hardware. Including ARM. Embedded controllers (the microwave washing machine kind) might not have floating point hardware though. But that part of the question was underspecified.

Upvotes: 22

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

I question your use of "algorithm" when speaking of C programs. Programs and algorithms are not the same (an algorithm is mathematical; a C program is expected to be implementing some algorithm).

But on current processors (like in recent x86-64 laptops or desktops) the FPU is doing fairly well. I guess (but did not benchmark) that a fast way of computing the n-th root could be, 

 inline unsigned root(unsigned x, unsigned n) {
   switch (n) {
     case 0: return 1;
     case 1: return x;
     case 2: return (unsigned)sqrt((double)x);
     case 3: return (unsigned)cbrt((double)x);
     default: return (unsigned) pow (x, 1.0/n);
   }
 }

(I made a switch because many processors have hardware to compute sqrt and some have hardware to compute cbrt ..., so you should prefer these when relevant...).

I am not sure that n-th root of a negative number makes sense in general. So my root function takes some unsigned x and returns some unsigned number.  

Upvotes: 6

Related Questions