Вычислить 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

Мне кажется, что Алгоритм смещения n-го корня обеспечивает именно то, что вы хотите:

Алгоритм смещения 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