Stimare la radice quadrata

StackOverflow https://stackoverflow.com/questions/3722975

Domanda

Le scrivo un'applicazione per iPhone che ha bisogno di calcolare la radice quadrata di un numero di circa 2000 volte ogni 1/30 di secondo. sqrt () funziona bene su un computer, ma il frame rate scende a circa 10 FPS su un iPhone o iPad, e ho già ottimizzato il resto del codice. Ho sentito dire che questo può essere accelerato in modo drammatico stimando la radice quadrata, ma non riesco a trovare alcun codice per fare questo. Ho solo bisogno di uno o due decimali di precisione. Qualche suggerimento su come fare questo, o altri modi per accelerare le cose fino sarebbe apprezzato.

Grazie!

È stato utile?

Soluzione

Come precisa volete che il vostro preventivo di essere? Se sai quanto vicino si desidera che il preventivo sia al reale sqrt il di Newton Metodo è tuo amico.

Non si conosce il campo di valori che vengono passati a sqrt? Se è così si può fare ad un look up table che viene precalcolata all'avvio (o anche leggere dal disco in fase di avvio a seconda di ciò che si rivela essere più veloce). Trovare il più vicino nella tabella per l'input e si ottiene la vostra stima.

Altri suggerimenti

A meno che tu in realtà necessità la radice quadrata, confronta i valori al quadrato piuttosto che i valori grezzi e la radice quadrata.

squadratura è molto più veloce (e più accurato) che prendere una radice quadrata, se avete solo bisogno confronti. Questo è il modo in cui la maggior parte dei giochi fanno.

Non si conosce il campo di valori che si sta tentando di trovare la radice quadrata di? Diciamo che sono valori che vanno da 0 a 10. È quindi possibile precalculate un array: 

sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10

Poi durante il runtime si prende il numero che si desidera che lo sqrt di, convertito che in un numero intero (così per esempio 3.123 diviene 3) e l'uso che, come un indice (3) per cercare il valore precalcolato.

Naturalmente, se si desidera più fine risoluzione si può solo aumentare il numero di elementi nella matrice.

Prima di tutto, siete certi che radice quadrata è in realtà il collo di bottiglia? Hai profilata? 2000 radici quadrate ogni 1/30 di secondo in realtà non è poi così tanti, anche su un telefono cellulare. La documentazione ARM cita 33 cicli per una radice quadrata precisione singola e 60 cicli per doppia precisione; un processore a 600MHz può fare 10 milioni radici quadrate al secondo (di più se l'istruzione viene pipeline a tutti).

Se avete profilato, e radice quadrata è davvero il collo di bottiglia, si vorrà usare l'istruzione NEON vrsqrte.f32. Questa istruzione è abbastanza veloce e ti dà i circa reciproche radici quadrate di quattro numeri in virgola mobile contemporaneamente. È quindi possibile utilizzare le istruzioni per ottenere vmul.f32 approssimative radici quadrate (anche se per molti usi il reciproco è più utile rispetto alla radice piazza stessa).

Forse questo è per te:
veloce inversa radice quadrata
Se questo metodo non fornisce la precisione che vi serve ci sono anche un sacco di altri metodi iterativi in ??cui è possibile scegliere più o meno precisa tra velocità e precisione:
metodi per il calcolo della radice quadrata

La modifica più semplice si può fare su un iPhone è quello di utilizzare sqrtf () al posto di sqrt (). Singolo matematica float precisione è molto più veloce di doppia precisione, in particolare sui dispositivi di 3GS epoca e più recenti.

Se necessario la radice quadrata di calcolare un triangolo Pitagora (sqrt (x * x + y * y)), ed entrambi X e Y sono non negativo, quindi molto veloce approssimazione cioè 

max(x,y) + min(x,y)*0.333

Questo è un errore massimo di 5,7%. Attenzione per ramo misprediction in min () e Max () però.

Se si dispone di un "normale" float positivo o doppia, e non un int, e si desidera utilizzare un metodo di look-up table, si possono fare due distinte up tabella di look, uno per l'esponente (ri-polarizzato), e uno per pochi bit della mantissa (shift e maschera estrazione campo di bit), e quindi moltiplicare l'aspetto due tavolo fino risultati insieme.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top