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

Question

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

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

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

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

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

Answer 1

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

Допустим, вы хотите, чтобы найти целое-к-й корень 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

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

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

=== Faster версия ===

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 3

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

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

Answer 4

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

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

Приведенные примеры на связанной странице wikipedia.

Answer 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