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: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Calcolo Radici n-esime in tempo polinomiale Vs bisezione

Messaggio da modulocomplicato »

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.

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Calcolo Radici n-esime in tempo polinomiale Vs bisezione

Messaggio da Pasquale »

Posso dirti che qualche tempo fa realizzai una routine in Decimal Basic, che definirei abbastanza veloce.
In base all'approssimazione di cui ci si può accontentare ed in rapporto al numero di cifre del radicando,
è possibile apportare variazioni da studiare al momento alle righe 50,60 e 70:

!'ATTENZIONE: se l'intero del radicando è minore di 14 cifre,
!'conviene lavorare con la precisione semplice,
!'mentre da 14 cifre in poi devi utilizzare la doppia precisione,
!'altrimenti la routine lavora male e talmente lenta, che sembra bloccata.

INPUT PROMPT "Inserisci indice della radice ->":N
INPUT PROMPT "Inserisci radicando della radice ->":R

LET a=INT(R)
LET a$=STR$(a)
LET lu=LEN(a$)
IF lu<=13 THEN
LET x=R^(1/N)
print
PRINT "radice";N;"esima di";R;"=";x
print
PRINT x;"^";N;"=";x^N
GOTO 100
END IF

LET x=R
DO
LET x=SQR(x)
IF x^N<=R THEN EXIT DO
LOOP

LET a=x
DO
LET x=2*x
IF x^N>R THEN EXIT DO
LOOP

LET b=x
DO
LET x=(a+b)/2
IF x^N<R THEN
LET a=x
ELSE
LET b=x
END IF
50 LOOP UNTIL ABS(a-b)<0.00000000000000000001

60 LET y=INT(x*10^20)/10^20
PRINT
PRINT x
PRINT
70 PRINT y;"^";N;"=";INT(y^N*10^6)/10^6

100

END
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Rispondi