Fastest method to find nth root of a number

Question

The problem is to find nth root of a number and if the root is an integer i need to print it, else I will have to print -1. I had used this method but I get tle. Is there any method faster than the one I have implemented?

Here is my code:

public class Sqrt {
  public static double nthroot(int n, double x)//calculates root
  {
    return Math.pow(x,1./n);
  }

  public static void main(String[] args) throws IOException 
  {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int t,n,m;
    double x;
    String[] y;
    t=Integer.parseInt(br.readLine());
    while(t-->0)//test cases
    {
      y=br.readLine().split(" ");//to get number and the exp
      n=Integer.parseInt(y[1]);//the exp
      m=Integer.parseInt(y[0]);//the number
      x=nthroot(m,n);
      x=BigDecimal.valueOf(x)
                            .setScale(5, RoundingMode.HALF_UP)
                            .doubleValue();//to set precision upto 5 decimal places
      if(x==(int)x)// **checks whether the root obtained is integer or not**
      {
        System.out.println((int)x);
      }
      else
      {  
        System.out.println(-1);
      }
    }
  }
}

Answer 1

the fastest (optimized to handle many queries) would be to create SoE (Sieve of Eratosthenes) table for all non trivial roots (exp = 2,3,4,5,...).

The table for x^(1/2) would be (10^9)^(1/2) = 31622 integers. For x^1/3 it is just 1000 integers and the number is decreasing with exponent ... You can use integer bit width division instead to get the table sizes instead of pow ...

For example SoE for x^(1/3) would be in C++ like this:

const bits=32;  // binary bits count of 10^9
int e = 3;      // rooth exponent
int n =1<<(1+bits/e); // table size
int *soe=new int [n+1];
int x;
for (x=0;x<=n;x++) soe[x]=x*x*x;

Now soe[] holds { 0,1,27,64,125,...} which are all integer cube roots. So for any query on cubic roots you just bin search soe table and if exact match found return its index in soe or -1 otherwise.

You can construct one soe table for each exponent (except 1) for example something like soe[exp-2][] ...

If you want to construct this without SoE then use integer binary search only like this:

• Power by squaring for negative exponents
• How to get a square root for 32 bit input in one clock cycle only?

[Edit1] Here simple 32bit C++ (sorry I do not code in JAVA) example:

//---------------------------------------------------------------------------
//typedef uint32_t DWORD;           // uncomment this if no DWORD type is present
//typedef uint16_t WORD;            // uncomment this if no WORD type is present
const int _nroot_maxe=30;           // max exponent
DWORD *soe[_nroot_maxe+3]={NULL};   // soe[][]
DWORD soen[_nroot_maxe+3];          // soe[e] size
DWORD soem[_nroot_maxe+3];          // soe[e] index MSB mask
//---------------------------------------------------------------------------
void mul(DWORD &h,DWORD &l,DWORD x,DWORD y) // (h,l) =  x * y
    {                                       //  64   = 32 * 32 bits
    const int _h=1; // this is platform dependent MSW/LSW order !!!
    const int _l=0;
    union _u
        {
        DWORD u32;
        WORD u16[2];
        }u;
    DWORD al,ah,bl,bh;
    DWORD c0,c1,c2,c3;
    // separate 2^16 base digits
    u.u32=x; al=u.u16[_l]; ah=u.u16[_h];
    u.u32=y; bl=u.u16[_l]; bh=u.u16[_h];
    // multiplication (al+ah<<1)*(bl+bh<<1) = al*bl + al*bh<<1 + ah*bl<<1 + ah*bh<<2
    c0=(al*bl);        
    c1=(al*bh)+(ah*bl);
    c2=(ah*bh);        
    c3= 0;
    // propagate 2^16 overflows (backward to avoid overflow)
    c3+=c2>>16; c2&=0x0000FFFF; 
    c2+=c1>>16; c1&=0x0000FFFF; 
    c1+=c0>>16; c0&=0x0000FFFF;
    // propagate 2^16 overflows (normaly to recover from secondary overflow)
    c2+=c1>>16; c1&=0x0000FFFF;
    c3+=c2>>16; c2&=0x0000FFFF;
    // (c3,c2,c1,c0) -> (h,l)
    u.u16[_l]=c0; u.u16[_h]=c1; l=u.u32;
    u.u16[_l]=c2; u.u16[_h]=c3; h=u.u32;
    }
//---------------------------------------------------------------------------
void nroot_init()   // init SoE tables for nroot
    {
    DWORD i,e,n,m,h,l;
    // compute table sizes
    soen[0]=0; soem[0]=0;
    soen[1]=0; soem[1]=0;
    for (n=0,e=2;e<=_nroot_maxe;e++)
        {
        i=1<<((31+e-1)/e);
        soen[e]=i;
        n+=i;
        }
    // allocate memory and set pointers
    soe[0]=new DWORD[n];
    for (e=1;e<=_nroot_maxe;e++) soe[e]=soe[e-1]+soen[e-1];
    // soe
    for (e=2,i=0;i<soen[e];i++) soe[e][i]=i*i;
    for (e=3;e<=_nroot_maxe;e++)
     for (i=0;i<soen[e];i++)
        {
        mul(h,l,i,soe[e-1][i]);     // 32bit * 32bit = 64bit
        if (!h) soe[e][i]=l;        // if no 32bit overflow store result
         else soen[e]=i;            // stop otherwise
        }
    // compute bin search index masks
    for (m=0x80000000,e=2;e<=_nroot_maxe;e++)
        {
        while (m>=soen[e]) m>>=1; m<<=1;
        soem[e]=m;
        }
    }
//---------------------------------------------------------------------------
void nroot_exit()   // release SoE tables (free memory)
    {
    // release memory
    if (soe[0]!=NULL) delete[] soe[0];
    for (DWORD e=0;e<=_nroot_maxe;e++)
        {
        soe[e]=NULL;
        soen[e]=0;
        soem[e]=0;
        }
    }
//---------------------------------------------------------------------------
int nroot(DWORD x,DWORD e)  // e-th root of x or -1 if not integer result
    {
    // special cases
    if (e==0) return -1;
    if (e==1) return x;
    if (e>_nroot_maxe) return -1;
    // init if needed
    if (soe[0]==NULL) nroot_init();
    // binary search
    DWORD m,i;
    for (i=0,m=soem[e];m;m>>=1)
        {
        i|=m;
        if ((i>=soen[e])||(soe[e][i]>x)) i^=m;
        }
    if (soe[e][i]==x) return i;
    return -1;
    }
//---------------------------------------------------------------------------

For those of you that do not have DWORD or WORD uncomment the typedefs or change to unsigned 32 and 16 bit integers on your platform ... Also set the _h,_l constants to match your platform.

Even this can be speeded up ... just realize that for higher exponents there are possible only 0,1,2,3 ... 0,1 exponents...

The init function has to be called just once. On my setup it took ~0.187ms which is negligible. Testing all 1000000000 5th-roots took around ~16sec