Calcola la radice Nth con l'aritmetica dei numeri interi

Question

Esistono un paio di modi per trovare le radici quadrate integer utilizzando solo l'aritmetica dei numeri interi. Ad esempio this one. È una lettura interessante e anche una teoria molto interessante, in particolare per la mia generazione in cui tali tecniche non sono più così utili.

L'elemento principale è che non è possibile utilizzare l'aritmetica in virgola mobile, in modo da escludere il metodo newton e le derivazioni. L'unico altro modo che conosco per trovare le radici è l'espansione binomiale, ma richiede anche l'aritmetica in virgola mobile.

Quali tecniche/algoritmi ci sono per calcolare radici ennesime integrali utilizzando solo l'aritmetica intera?

Modifica: Grazie per tutte le risposte finora. Sembrano tutti processi e miglioramenti leggermente più intelligenti. Non c'è modo migliore?

Edit2: Ok, quindi sembra che non ci sia un modo intelligente per farlo senza trial/miglioramenti e sia il metodo newton che una ricerca binaria. Qualcuno può fornire un confronto dei due in teoria? Ho eseguito una serie di punti di riferimento tra i due e li ho trovati abbastanza simili.

Answer 1

È possibile utilizzare il metodo di Newton utilizzando solo l'aritmetica di interi, il passo è lo stesso dell'aritmetica in virgola mobile, tranne che è necessario sostituire gli operatori in virgola mobile con gli operatori di numeri interi corrispondenti in lingue che dispongono di operatori diversi per questi.

Diciamo che si desidera trovare la radice intero-k-esimo di a > 0, che dovrebbe essere il più grande intero r tale che r^k <= a. Si inizia con qualsiasi numero intero positivo (ovviamente un buon punto di partenza aiuta).

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

Fatta eccezione per il primo passo, è necessario x == r <==> step(k,a,x) >= x.

Answer 2

Una soluzione semplice consiste nell'utilizzare la ricerca binaria.

Supponiamo di trovare l'ennesima radice di 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) 

=== === più veloce versione

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

Un modo ovvio sarebbe quello di utilizzare binary search insieme exponentiation by squaring. Ciò ti consentirà di trovare nthRoot(x, n) in O(log (x + n)): ricerca binaria in [0, x] per il numero intero maggiore k tale che k^n <= x. Per alcuni k^n <= x, se k^n <= x, ridurre la ricerca a [k + 1, x], altrimenti ridurlo a [0, k].

Avete bisogno di qualcosa di più intelligente o più veloce?

Answer 4

Mi sembra che la Shifting nth root algorithm fornisce esattamente quello che vuoi:

L'algoritmo di radice ennesima spostamento è un algoritmo per l'estrazione della radice ennesima di un numero reale positivo che procede in modo iterativo spostando in n cifre il radicando, a partire dal più significativo, e produce una cifra della radice su ogni iterazione, in un modo simile alla divisione lunga.

Ci sono esempi funzionati nella pagina wikipedia collegata.

Answer 5

Algoritmo più semplice in 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