Tính toán gốc thứ N với số học số nguyên

Question

Có một số cách để tìm số nguyên căn bậc hai chỉ sử dụng số học số nguyên. Ví dụ: this one. Nó làm cho đọc thú vị và cũng là một lý thuyết rất thú vị, đặc biệt là cho thế hệ của tôi, nơi các kỹ thuật như vậy không còn hữu ích nữa.

Điều chính là nó không thể sử dụng số học dấu phẩy động, để quy tắc ra phương thức newton và dẫn xuất của nó. Cách duy nhất tôi biết tìm rễ là nhị thức mở rộng, nhưng điều đó cũng đòi hỏi số học dấu chấm động.

Những kỹ thuật/thuật toán nào có thể sử dụng để tính toán số nguyên nth không thể thiếu bằng số học số nguyên?

Chỉnh sửa: Cảm ơn tất cả các câu trả lời cho đến thời điểm này. Tất cả chúng dường như là một thử nghiệm và cải tiến thông minh hơn một chút. Có cách nào tốt hơn không?

Chỉnh sửa2: Ok, do đó, có vẻ như không có cách thông minh nào để thực hiện việc này mà không cần dùng thử/cải tiến và phương thức newton hoặc tìm kiếm nhị phân. Có ai có thể so sánh hai số trong lý thuyết không? Tôi đã chạy một số điểm chuẩn giữa hai và thấy chúng khá giống nhau.

Answer 1

Bạn có thể sử dụng phương pháp Newton chỉ sử dụng số học số nguyên, bước này giống với số học dấu phẩy động, ngoại trừ bạn phải thay thế toán tử dấu phẩy động bằng toán tử số nguyên tương ứng bằng ngôn ngữ có toán tử khác nhau.

Giả sử bạn muốn tìm số nguyên-k-th của a > 0, số này phải là số nguyên lớn nhất r sao cho r^k <= a. Bạn bắt đầu với bất kỳ số nguyên dương nào (dĩ nhiên điểm bắt đầu tốt sẽ giúp).

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

Ngoại trừ bước đầu tiên, bạn có x == r <==> step(k,a,x) >= x.

Answer 2

Một giải pháp dễ dàng là sử dụng tìm kiếm nhị phân.

Giả sử chúng tôi đang tìm gốc thứ n của 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) 

=== Version nhanh hơ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 3

Một cách rõ ràng sẽ được sử dụng cùng với binary searchexponentiation by squaring. Điều này sẽ cho phép bạn tìm thấy nthRoot(x, n) trong O(log (x + n)): tìm kiếm nhị phân trong [0, x] cho số nguyên lớn nhất k sao cho k^n <= x. Đối với một số k, nếu k^n <= x, hãy giảm tìm kiếm thành [k + 1, x], nếu không hãy giảm số này thành [0, k].

Bạn có yêu cầu điều gì đó thông minh hơn hoặc nhanh hơn không?

Answer 4

Dường như với tôi rằng Shifting nth root algorithm cung cấp chính xác những gì bạn muốn:

Thuật toán gốc thứ n chuyển là một thuật toán để giải nén vào thư mục gốc thứ n của một số thực dương mà tiến hành lặp đi lặp lại bằng cách thay đổi trong n chữ số radicand, bắt đầu với ý nghĩa quan trọng nhất, và tạo ra một chữ số của gốc trên mỗi lần lặp, theo cách tương tự như phân chia dài.

Có các ví dụ được làm việc trên trang wikipedia được liên kết.

Answer 5

Thuật toán đơn giản hơn trong 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