Calculate Nth root with integer arithmetic

Question

There are a couple of ways to find integer square roots using only integer arithmetic. For example this one. It makes for interesting reading and also a very interesting theory, particularly for my generation where such techniques aren't so useful any more.

The main thing is that it can't use floating point arithmetic, so that rules out newtons method and it's derivations. The only other way I know of to find roots is binomial expansion, but that also requires floating point arithmetic.

What techniques/algorithms are there for computing integral nth roots using only integer arithmetic?

Edit: Thanks for all the answers so far. They all seem to be slightly more intelligent trial and improvement. Is there no better way?

Edit2: Ok, so it would seem there is no smart way to do this without trial/improvement and either newtons method or a binary search. Can anyone provide a comparison of the two in theory? I have run a number of benchmarks between the two and found them quite similar.

Answer 1

You can use Newton's method using only integer arithmetic, the step is the same as for floating point arithmetic, except you have to replace floating point operators with the corresponding integer operators in languages which have different operators for these.

Let's say you want to find the integer-k-th root of a > 0, which should be the largest integer r such that r^k <= a. You start with any positive integer (of course a good starting point helps).

int_type step(int_type k, int_type a, int_type x) {
    return ((k-1)*x + a/x^(k-1))/k;
}

int_type root(int_type k, int_type a) {
    int_type x = 1, y = step(k,a,x);
    do {
        x = y;
        y = step(k,a,x);
    }while(y < x);
    return x;
}

Except for the very first step, you have x == r <==> step(k,a,x) >= x.

Answer 2

One obvious way would be to use binary search together with exponentiation by squaring. This will allow you to find nthRoot(x, n) in O(log (x + n)): binary search in [0, x] for the largest integer k such that k^n <= x. For some k, if k^n <= x, reduce the search to [k + 1, x], otherwise reduce it to [0, k].

Do you require something smarter or faster?

Answer 3

One easy solution is to use the binary search.

Assume we are finding nth root of x.

Function GetRange(x,n):
    y=1
    While y^n < x:
        y*2
    return (y/2,y)

Function BinSearch(a,b,x,):
    if a == b+1:
        if x-a^n < b^n - x:
           return a
        else:
           return b
    c = (a+b)/2
    if n< c^n:
        return BinSearch(a,c,x,n)
    else:
        return BinSearch(c,b,x,n)

a,b = GetRange(x,n)
print BinSearch(a,b,x,n)

===Faster Version===

Function BinSearch(a,b,x,):
    w1 = x-a^n
    w2 = b^n - x
    if a <= b+1:
        if w1 < w2:
           return a
        else:
           return b
    c = (w2*a+w1*b)/(w1+w2)
    if n< c^n:
        return BinSearch(a,c,x,n)
    else:
        return BinSearch(c,b,x,n)

Answer 4

It seems to me that the Shifting nth root algorithm provides exactly what you want:

The shifting nth root algorithm is an algorithm for extracting the nth root of a positive real number which proceeds iteratively by shifting in n digits of the radicand, starting with the most significant, and produces one digit of the root on each iteration, in a manner similar to long division.

There are worked examples on the linked wikipedia page.

Answer 5

I made the algorithm in VBA in Excel. For now it only calculates roots of integers. It is easy to implement the decimals as well.

Just copy and paste the code into an EXCEL module and type the name of the function into some cell, passing the parameters.

Public Function RootShift(ByVal radicand As Double, degree As Long, Optional ByRef remainder As Double = 0) As Double

   Dim fullRadicand As String, partialRadicand As String, missingZeroes As Long, digit As Long

   Dim minimalPotency As Double, minimalRemainder As Double, potency As Double

   radicand = Int(radicand)

   degree = Abs(degree)

   fullRadicand = CStr(radicand)

   missingZeroes = degree - Len(fullRadicand) Mod degree

   If missingZeroes < degree Then

      fullRadicand = String(missingZeroes, "0") + fullRadicand

   End If

   remainder = 0

   RootShift = 0

   Do While fullRadicand <> ""

      partialRadicand = Left(fullRadicand, degree)

      fullRadicand = Mid(fullRadicand, degree + 1)

      minimalPotency = (RootShift * 10) ^ degree

      minimalRemainder = remainder * 10 ^ degree + Val(partialRadicand)

      For digit = 9 To 0 Step -1

          potency = (RootShift * 10 + digit) ^ degree - minimalPotency

          If potency <= minimalRemainder Then

             Exit For

          End If

      Next

      RootShift = RootShift * 10 + digit

      remainder = minimalRemainder - potency

   Loop

End Function

Answer 6

Algorithm more simple in VBA.

Public Function RootNth(radicand As Double, degree As Long) As Double
   Dim countDigits As Long, digit As Long, potency As Double
   Dim minDigit As Long, maxDigit As Long, partialRadicand As String
   Dim totalRadicand As String, remainder As Double

  radicand = Int(radicand)
  degree = Abs(degree)
  RootNth = 0
  partialRadicand = ""
  totalRadicand = CStr(radicand)
  countDigits = Len(totalRadicand) Mod degree
  countDigits = IIf(countDigits = 0, degree, countDigits)
  Do While totalRadicand <> ""
     partialRadicand = partialRadicand + Left(totalRadicand, countDigits)
     totalRadicand = Mid(totalRadicand, countDigits + 1)
     countDigits = degree
     minDigit = 0
     maxDigit = 9
     Do While minDigit <= maxDigit
        digit = Int((minDigit + maxDigit) / 2)
        potency = (RootNth * 10 + digit) ^ degree
        If potency = Val(partialRadicand) Then
           maxDigit = digit
           Exit Do
        End If
        If potency < Val(partialRadicand) Then
           minDigit = digit + 1
        Else
           maxDigit = digit - 1
        End If
     Loop
     RootNth = RootNth * 10 + maxDigit
  Loop
   End Function