radice quadrata di rilevamento del valore mobile

Question

Ho un ciclo di controllo in esecuzione ad alta frequenza e ho bisogno di calcolare una radice quadrata per ogni ciclo. Le funzioni tipiche della radice quadrata funzionano bene ma richiedono un tempo eccessivo. Dal momento che il valore che sto prendendo la radice quadrata di non cambia troppo in ogni ciclo, vorrei trovare una radice quadrata iterativa che convergerà e quindi traccia il risultato corretto. In questo modo ho potuto fare una singola iterazione ad ogni passo temporale, piuttosto che molti.

Il problema è che probabilmente tutti i metodi di radice quadrata iterativi che ho visto avranno esito negativo quando l'input sta cambiando. In particolare sembra che ci saranno problemi quando l'input va a zero e poi aumenta nuovamente - i metodi non amano iniziare con un'ipotesi di zero.

Il mio intervallo di input è 0-4,5 e ho bisogno di una precisione di circa 0,01, quindi l'utilizzo di un incremento/decremento di 0,01 potrebbe richiedere troppo tempo - voglio che converga principalmente in 10 cicli o meno.

FYI Sto usando il punto fisso 16/32 bit l'ingresso è 16 bit q12. È su un microcontrollore quindi non mi interessa usare 1K per una tabella di ricerca. Il codice viene generato anche da un modello simulink e le loro funzioni di ricerca tabella sono piuttosto piene di overhead.

C'è una buona soluzione a questo?

Answer 1

È possibile utilizzare uno scatto del metodo Halley. Ha convergenza cubica e pertanto dovrebbe essere abbastanza preciso se il valore si muove leggermente:

x_{n+1} = x_n * (x_n^2 + 3Q)/(3 x_n^2 + Q) 

Questo converge cubcially a sqrt(Q).

Riferimento: http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm

Answer 2

l'intervallo 0-4,5 è abbastanza piccolo. Con una precisione di 0,01, sono solo 450 i possibili calcoli. Potresti calcolarli tutti in fase di compilazione come costanti e fare semplicemente una ricerca durante il runtime.

Answer 3

Suggerirei di utilizzare una tabella di ricerca, se si conoscono in anticipo gli intervalli con cui si ha a che fare. Genera un array o una tabella hash (a seconda della lingua in cui stai lavorando) con il livello di precisione necessario e fai riferimento a questo quando hai bisogno delle tue radici.

Answer 4

Ho provato un secondo ordine di espansione di Taylor su sqrt(x) e passare il seguente risultato

se y=sqrt(x) e sai y_c = sqrt(x_c) già allora:

t = x-3*x_c; 
y = (12*x_c*x_c-t*t)/(8*y_c*y_c*y_c); 

Maggiore x è il migliore è l'approssimazione. Nel caso peggiore con x_c=0.01 e x=0.02, il risultato risulta 0.1375 rispetto al risultato reale di sqrt(0.02)=0.1414 o una differenza di 0.0039 che è inferiore a 0.01.

Ho provato il codice con C# e ho visto un costante 33% speedup vs Math.Sqrt().