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

Ответ 1

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

Скажем, вы хотите найти целочисленный 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.

Ответ 2

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

Требуется ли что-то умнее или быстрее?

Ответ 3

Мне кажется, что Shifting nth root algorithm обеспечивает именно то, что вы хотите:

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

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

Ответ 4

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

Предположим, что мы находим 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)

Ответ 5

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

Ответ 6

Я сделал алгоритм в 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