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

Question

Есть несколько способов найти целочисленные квадратные корни, используя только целочисленную арифметику. Например, этот. Это делает для интересного чтения, а также очень интересную теорию, особенно для моего поколения, где такие методы уже не так полезны.

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

Какие существуют методы / алгоритмы для вычисления целых n-х корней с использованием только целочисленной арифметики?

Редактировать: Спасибо за все ответы до сих пор. Все они кажутся немного более разумным методом проб и улучшений. Нет лучшего способа?

Edit2: Хорошо, так что казалось бы, что нет разумного способа сделать это без проб / улучшений и метода ньютонов или бинарного поиска. Кто-нибудь может дать сравнение двух в теории? Я провел ряд тестов между ними и нашел их очень похожими.

Answer 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,

Answer 2

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

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

Answer 3

Мне кажется, что алгоритм Shthting nth root обеспечивает именно то, что вы хотите:

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

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

Answer 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)

Answer 5

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

Answer 6

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