I have implemented a class for Big Integer in c# (project for school) , and I have to calculate nth root. I tried binary seach but it is taking too long for very big integers. I also tried to implement Newton method. The problem is that my Division function return only the integer part, with no digits. The Newton method require division operation with digits. My wish is to find a way to GET ONLY THE INTEGER PART FROM NTH ROOT.
Newton's method is
N(x) = x - (x^n-a)/(n*x^(n-1))=( (n-1)*x + a/(x^(n-1)))/n
This should work well also with integer operations. You may have to correct the result by plusminus 1.
It is important to use a good initial value since far away from the root the convergence of Newtons method for polynomials of degree n is geometric resp. linear with factor (1-1/n), thus very slow for larger values of n.
Using base B, for an integer x with d digits set q=d/n, compute rx=x/B^(n*q) by truncation of the digit sequence and converting to floating point, compute ry=pow(rx, 1.0/n) in floating point and convert y=ry*B^q back into the biginteger format to use as first approximate root.
Please report on your problems while using this method.
You may also try to implement the manual digit extraction method as described in http://en.wikipedia.org/wiki/Shifting_nth_root_algorithm