approssimativo log10 [x^k0 + k1]

Question

Saluti. Sto cercando di approssimare la funzione di

Log10 [x^K0 + k1], dove .21 < K0 < 21, 0 < k1 < ~ 2000 e x è intero < 2^14.

k0 & k1 sono costanti. Ai fini pratici, è possibile assumere k0 = 2,12, k1 = 2660. La precisione desiderata è 5 * 10^-4 errore relativo.

Questa funzione è praticamente identica a Log [x], tranne vicino a 0, dove differisce molto.

Ho già trovato un'implementazione SIMD che è ~ 1,15 volte più veloce di una semplice tabella di ricerca, ma vorrei migliorarla se possibile, cosa che penso sia molto difficile a causa della mancanza di istruzioni efficienti.

L'implementazione SIMD utilizza l'aritmetica a virgola fissa a 16 bit per la valutazione di un polinomio di terzo grado (utilizzo i minimi quadrati). Il polinomio utilizza coefficienti diversi per diversi intervalli di input. Vi sono 8 intervalli e range i spans (64) 2^i a (64) 2^(i + 1). La ragione dietro a ciò è che le derivate di Log [x] scendono rapidamente con x, il che significa che un polinomio si adatta in modo più preciso poiché i polinomi sono esattamente adatti per funzioni che hanno una derivata di 0 oltre un certo ordine.

Le ricerche di tabelle SIMD vengono eseguite in modo molto efficiente con un singolo _mm_shuffle_epi8(). Uso la conversione float di SSE in int per ottenere l'esponente e il significato usati per l'approssimazione a virgola fissa. Ho anche eseguito il pipeline del loop del ciclo per ottenere una velocità di 1.25x, quindi è probabile che ulteriori ottimizzazioni del codice siano improbabili.

Quello che sto chiedendo è se c'è un'approssimazione più efficiente a un livello superiore? Ad esempio:

1. Può questa funzione essere scomposto in funzione con un dominio limitato come log2 ((2^x) * significando) = x + log2 (significando)

quindi eliminando la necessità per gestire diversi intervalli (ricerche di tabelle). Il problema principale che penso sta aggiungendo il termine k1 uccide tutte quelle belle proprietà del log che conosciamo e amiamo, rendendolo impossibile. O è?

1. Metodo iterativo? non la penso così perché il metodo di Newton per log [x] è già un'espressione complicata

2. Sfruttare la località dei pixel adiacenti? - se la gamma degli 8 ingressi si trova nello stesso intervallo di approssimazione, allora posso cercare un singolo coefficiente, invece di cercare coefficienti separati per ciascun elemento. Quindi, posso usare questo come un caso comune veloce e utilizzare un percorso di codice generale più lento quando non lo è. Ma per i miei dati, l'intervallo deve essere ~ 2000 prima che questa proprietà si tenga il 70% delle volte, il che non sembra rendere questo metodo competitivo.

Per favore, dammi un parere, soprattutto se sei un matematico applicato, anche se dici che non si può fare. Grazie.

Answer 1

Una sola osservazione: Potete trovare un'espressione per quanto grande x deve essere in funzione del K0 e K1, in modo tale che il termine x^K0 domina k1 sufficiente per il ravvicinamento:

x^K0 + k1 ~ = x^k0, che consente di valutare approssimativamente la funzione come

k0 * Log (x).

Questo si sarebbe occupato di tutte le x sopra un certo valore.

Answer 2

Dovresti essere in grado di migliorare l'adattamento dei minimi quadrati utilizzando Chebyshev approximation. (L'idea è, stai cercando l'approssimazione la cui peggiore deviazione in un intervallo è minima, i minimi quadrati invece cercano quella la cui differenza quadratica sommata è minima.) Immagino che questo non faccia un'enorme differenza per il tuo problema, ma non sono sicuro - si spera che potrebbe ridurre il numero di intervalli che devi dividere in qualche modo.

Se esiste già un'implementazione rapida di log(x), è possibile calcolare P(x) * log(x) dove P (x) è un polinomio scelto dall'approssimazione di Chebyshev. (Invece di provare a fare l'intera funzione come un polinomio di circa - per avere meno riduzione di gamma.)

Sono un dilettante qui - mi sto solo immergendo perché non ci sono già molte risposte .

Answer 3

Ho letto di recente il modo in cui il modello sRGB comprime i valori di stimolo fisico in valori RGB memorizzati.

è fondamentalmente molto simile alla funzione cerco di approssimare, solo che è definito funzione a tratti:

K0 x, x < 0,0031308

k1 x^0,417 - k2 altrimenti

I è stato detto che l'aggiunta costante in Log [x^k0 + k1] avrebbe dovuto rendere l'inizio della funzione più lineare. Ma questo può essere facilmente ottenuto con un'approssimazione pezzo-saggio. Ciò renderebbe l'approssimazione molto più "uniforme" - con solo 2 intervalli di approssimazione. Questo dovrebbe essere più economico da calcolare poiché non è più necessario calcolare un indice dell'intervallo di approssimazione (registro intero) e fare la ricerca del coefficiente SIMD.

Per ora, concludo che questo sarà l'approccio migliore, anche se non approssima esattamente la funzione. La parte difficile sarà proporre questo cambiamento e convincere le persone a usarlo.