15

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?

Improve this question
5
  • with integer means no decimal places? Commented Dec 22, 2013 at 13:42
  • @Ishmeet Yes Answer should be integer Commented Dec 22, 2013 at 13:46
  • So, do you want the result rounded, and if so, then how? Or do you want to get answer only if it is integer, and error (or whatever) otherwise? Commented Dec 22, 2013 at 13:47
  • @hyde Result must be rounded Commented Dec 22, 2013 at 13:50
  • Why close this question! Commented Dec 24, 2013 at 2:09

5 Answers 5

Reset to default
23 
#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.

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

@Madura I am sure, because I don't use compilers from the last millennium.
@user567879 The maths: raising to a 1/n-th power is the same as taking the n-th root. That's by definition. In C(++), 1/n is an integer division, whereas in 1./n 1. is a double literal, so n gets converted to a double, and then divides 1.
I'd prefer writing 1.0 / n. It'll save a lot of people who might read the code a few "brain cycles" when they think what does this mean...
@MaduraAnushanga: Why would you compile without -O2 or -O3? It seems obvious that if you compile without optimisations enabled then optimisations will not be performed.
Great benchmarking right there. As Scooter once said: "Statistically these are the safest cars on Pandora. Let me throw some numbers at you... Five! Twenty-three! Eight Hundred and Six!"
|
11

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...

Improve this answer

2 Comments

Is this shifting nth root algorithm?
fails for large integers - I tried this to get 111'th root of an 80-digit integer (string of 8 consecutive copies of "1234567890") which is 5, but got 1 from this routine. (my current routine took 12 minutes to finish, so I'm looking for a faster one :)
7

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.  

Improve this answer

3 Comments

I question your questioning of the term algorithm when speaking of any programs...?
Even when signed values make no sense, they're troublesome if you want to write clean code with no "risky" signed-unsigned conversions, unless all values really are unsigned, which they rarely are. An in this case, consider for example cbrt(-8)...
The use of the double-precision floating-point function pow here is specious and is guaranteed to give you wrong results on occasion, due to floating-point rounding error. For example, (unsigned)pow(4096, 1.0/6) is 3, but the 6th root of 4096 is actually 4. This is because pow returns 3.9999999999999996 instead of 4.0, which is because 1.0/6 is 0.1666666666666667 instead of exactly 1/6.
1

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.

Improve this answer

Comments

1

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.