Calcolo Radici n-esime in tempo polinomiale Vs bisezione
Inviato: lun gen 20, 2014 8:09 am
Qualcuno ha voglia di vedere quale di questi due metodi è il più veloce per il calcolo delle radici n-esime ?
1) metodo classico
2) (mio?) metodo polinomiale con differenza ricorsiva ricordando che:
$A^n = \sum_{m=1}^{A} [ m^n - ( m-1)^n]$
quindi utilizzando il procedimento inverso, cioè la differenza ricorsiva a partire da un valore noto A.
Es. n=3 se voglio calcolare la radice cubica di 27 faccio:
A partire da m=1 fin tanto che il resto non è zero o tale per cui al passaggio successivo diventa negativo:
1° giro m=1 :
27 - [ m^n - ( m-1)^n] = 27 - (3m^2-3m+1) = 27- 1 = 26 (resto)
2° giro m=2:
26 - (3m^2-3m+1) = 26 - 7 = 19 (resto)
3° giro m=2:
19 - (3m^2-3m+1) = 19 - 19 = 0 (resto)
ok 3 è la radice cubica di 27.
Per fare il calcolo con precisione decimale la formula va cambiata usando le regole del binomio (ma chi legge i miei post sa già qual è)
A parità di base A, questo metodo impiega lo stesso numero di passi per n=2 come per n= qualsiasi, ma un numero crescente di operazioni, quindi probabilmente è più lento del metodo classico per n piccoli, ma più veloce per n grandi...
Grazie
Ciao
S.
1) metodo classico
2) (mio?) metodo polinomiale con differenza ricorsiva ricordando che:
$A^n = \sum_{m=1}^{A} [ m^n - ( m-1)^n]$
quindi utilizzando il procedimento inverso, cioè la differenza ricorsiva a partire da un valore noto A.
Es. n=3 se voglio calcolare la radice cubica di 27 faccio:
A partire da m=1 fin tanto che il resto non è zero o tale per cui al passaggio successivo diventa negativo:
1° giro m=1 :
27 - [ m^n - ( m-1)^n] = 27 - (3m^2-3m+1) = 27- 1 = 26 (resto)
2° giro m=2:
26 - (3m^2-3m+1) = 26 - 7 = 19 (resto)
3° giro m=2:
19 - (3m^2-3m+1) = 19 - 19 = 0 (resto)
ok 3 è la radice cubica di 27.
Per fare il calcolo con precisione decimale la formula va cambiata usando le regole del binomio (ma chi legge i miei post sa già qual è)
A parità di base A, questo metodo impiega lo stesso numero di passi per n=2 come per n= qualsiasi, ma un numero crescente di operazioni, quindi probabilmente è più lento del metodo classico per n piccoli, ma più veloce per n grandi...
Grazie
Ciao
S.