Вычислить корень N с целочисленной арифметикой

Вы можете использовать метод Ньютона, используя только целочисленную арифметику, шаг такой же, как и для арифметики с плавающей запятой, за исключением того, что вы должны заменить операторы с плавающей запятой соответствующими целочисленными операторами в языках, которые имеют для них другие операторы.

Допустим, вы хотите найти целое число k-го корня из a > 0, которое должно быть наибольшим целым числом r, таким что r^k <= a. Вы начинаете с любого положительного целого числа (конечно, хорошая отправная точка помогает).

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;
}

За исключением самого первого шага, у вас есть x == r <==> step(k,a,x) >= x.

Одним из очевидных способов может быть использование бинарного поиска вместе с возведение в степень путем возведения в квадрат. Это позволит вам найти nthRoot(x, n) в O(log (x + n)): бинарный поиск в [0, x] для наибольшего целого числа k такого, что k^n <= x. Для некоторых k, если k^n <= x, сократить поиск до [k + 1, x], иначе сократить до [0, k].

Вам нужно что-то умнее или быстрее?

Мне кажется, что алгоритм сдвига n-го корня обеспечивает именно то, что вам нужно:

Алгоритм сдвига n-го корня — это алгоритм извлечения n-го корня положительного действительного числа, который итеративно выполняется путем сдвига n цифр подкоренного числа, начиная со старшего, и дает одну цифру корня на каждой итерации, таким образом аналогично длинному делению.

На связанной странице википедии есть рабочие примеры.

Одним из простых решений является использование бинарного поиска.

Предположим, мы нашли корень n-й степени из 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)

===Быстрая версия===

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)

Я сделал алгоритм в VBA в Excel. Пока он вычисляет только корни целых чисел. Также легко реализовать десятичные дроби.

Просто скопируйте и вставьте код в модуль EXCEL и введите имя функции в какую-нибудь ячейку, передав параметры.

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

Алгоритм проще в 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