Esiste una libreria C++ in grado di prendere le radici nth dei numeri grandi (numeri che non possono essere contenuti in un unsigned long long
)?Come ottenere l'ennesima radice di grandi numeri in C++?
risposta
È possibile utilizzare GMP, una libreria di matematica di precisione arbitraria open source. Ha C++ bindings.
Se volete codificare da soli, controllare la pagina Wikipedia su radici n-esime:
http://en.wikipedia.org/wiki/Nth_root
L'algoritmo iterativo è molto semplice:
La radice ennesima di una serie A può essere calcolato dall'ennesimo algoritmo radice, un caso speciale del metodo di Newton. Inizia con un'ipotesi iniziale x (0) e poi iterare utilizzando la relazione di ricorrenza
x(k+1) = [(n - 1) * x(k) + A/x(k)^(n - 1)]/n
stop una volta che hai convergenti per la precisione desiderata.
Dipende da quanto più grande di 2^64 si vuole andare, credo. Il solo uso del doppio è buono a circa 1 parte in 10^9. Ho scritto un programma di test in 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;
}
che ha prodotto il seguente risultato:
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
Poi ho confrontato con Wolfram Alpha per ogni radice per ottenere l'errore che ho citato sopra.
A seconda dell'applicazione, forse questo sarà sufficiente.
Il metodo a divisione lunga è il metodo migliore per calcolare l'ennesima radice di qualsiasi numero reale positivo. Fornisce la migliore precisione di ogni cifra calcolata. Nessuna supposizione iniziale e nessuna approssimazione iterativa è richiesta.
un esempio è degno di un pezzo di mille parole ... –
Mentre questo potrebbe essere un suggerimento prezioso per risolvere il problema, una buona risposta dimostra anche la soluzione. Si prega di [modificare] per fornire un codice di esempio per mostrare cosa intendi. In alternativa, considera di scrivere questo come un commento. –
Sì, in particolare la funzione mpz_root. –