Calcolo Radici n-esime in tempo polinomiale Vs bisezione

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
modulocomplicato
Livello 4
Livello 4
Messaggi: 114
Iscritto il: lun ott 01, 2012 4:30 pm

Calcolo Radici n-esime in tempo polinomiale Vs bisezione

Messaggio da modulocomplicato » 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.

Rispondi