Làm thế nào để có được gốc thứ n của các số lớn trong C++?

Question

Có thư viện C++ nào có thể lấy gốc thứ n của các số lớn (số không thể phù hợp trong một số unsigned long long) không?

Answer 1

Bạn có thể sử dụng GMP, thư viện toán học chính xác tùy ý mã nguồn mở phổ biến. Nó có C++ bindings.

Answer 2

Nếu bạn muốn mã này cho mình, hãy kiểm tra các trang Wikipedia trên rễ thứ n:

http://en.wikipedia.org/wiki/Nth_root

Các thuật toán lặp là khá đơn giản:

Gốc thứ n của một số A có thể được tính toán bởi thuật toán gốc thứ n, một trường hợp đặc biệt của phương pháp Newton. Bắt đầu với một đoán ban đầu x (0) và sau đó lặp lại bằng cách sử dụng mối quan hệ lặp lại

x(k+1) = [(n - 1) * x(k) + A/x(k)^(n - 1)]/n 

Dừng khi bạn đã hội tụ với độ chính xác mong muốn.

Answer 3

Tùy thuộc vào mức độ lớn hơn 2^64 bạn muốn, tôi đoán vậy. Chỉ cần sử dụng tăng gấp đôi là tốt cho khoảng 1 phần trong 10^9. Tôi đã viết một chương trình thử nghiệm trong C:

#include <stdio.h> 
#include <math.h> 

int main(int argc, char **argv) 
{ 
    unsigned long long x; 
    double dx; 
    int i; 

    //make x the max possible value 
    x = ~0ULL; 
    dx = (double)x; 
    printf("Starting with dx = %f\n", dx); 
    //print the 2th to 20th roots 
    for (i = 2; i < 21; i++) 
    { 
     printf("%dth root %.15f\n", i, pow(dx, 1.0/i)); 
    } 
    return 0; 
} 

mà sản xuất đầu ra sau đây:

Starting with dx = 18446744073709551616.000000 
2th root 4294967296.000000000000000 
3th root 2642245.949629130773246 
4th root 65536.000000000000000 
5th root 7131.550214521852467 
6th root 1625.498677215435691 
7th root 565.293831000991759 
8th root 256.000000000000000 
9th root 138.247646578215154 
10th root 84.448506289465257 
11th root 56.421840319745364 
12th root 40.317473596635935 
13th root 30.338480458853493 
14th root 23.775908626191171 
15th root 19.248400577313866 
16th root 16.000000000000000 
17th root 13.592188707483222 
18th root 11.757875938204789 
19th root 10.327513583579238 
20th root 9.189586839976281 

Sau đó, tôi so với Wolfram Alpha cho mỗi gốc để có được những lỗi tôi trích dẫn ở trên.

Tùy thuộc vào ứng dụng của bạn, có lẽ điều này sẽ đủ tốt.

Answer 4

Hãy thử thêm MAPM và qd.

MAPM được viết bằng C nhưng cũng có API C++. qd được viết bằng C++ nhưng cũng có một API C.

Answer 5

Phương pháp chia dài là phương pháp tốt nhất để tính toán gốc thứ n của bất kỳ số thực dương nào. Nó cho độ chính xác tốt nhất của mỗi chữ số được tính toán. Không có dự đoán ban đầu và không có xấp xỉ lặp lại là bắt buộc.