Come gestire la moltiplicazione dei numeri vicino a 1

Question

Ho un po 'di numeri in virgola (Java raddoppia), la maggior parte dei quali sono molto vicino a 1 galleggiante, e ho bisogno di moltiplicare loro insieme come parte di un calcolo più grande. Ho bisogno di fare questo molto .

Il problema è che, mentre raddoppia Java non hanno alcun problema con un numero come:

0.0000000000000000000000000000000001 (1.0E-34)

non possono rappresentare qualcosa di simile:

1.0000000000000000000000000000000001

Di conseguenza di questo perdo precisione rapidamente (il limite sembra essere intorno 1,000000000000001 per il doppio del Java).

Ho considerato solo memorizzare i numeri con 1 sottratto, così per esempio 1.0001 potrebbero essere memorizzati come 0,0001 -, ma il problema è che a moltiplicarsi di nuovo insieme devo aggiungere 1 ed a questo punto perdo precisione

Per far fronte a questo ho potuto utilizzare BigDecimals per eseguire il calcolo (convertire in BigDecimal, aggiungere 1.0, quindi moltiplicare), e poi riconvertire raddoppia dopo, ma ho gravi preoccupazioni circa le implicazioni sulle prestazioni di questo.

Chiunque può vedere un modo per farlo che evita usando BigDecimal?

Modifica per chiarezza : si tratta di un filtro di collaborazione su larga scala, che impiega un algoritmo di ottimizzazione discesa del gradiente. La precisione è un problema perché spesso il filtro collaborativo che fare con numeri molto piccoli (come ad esempio la probabilità di una persona clic su un annuncio per un prodotto, che può essere 1 nel 1000, o in 1 10000).

La velocità è un problema perché il filtro di collaborazione deve essere addestrato su decine di milioni di punti di dati, se non di più.

Answer 1

Sì: perché

(1 + x) * (1 + y) = 1 + x + y + x*y

Nel tuo caso, x e y sono molto piccole, in modo da x*y sta per essere molto più piccolo - troppo piccolo per influenzare i risultati del vostro calcolo. Quindi, per quanto ti riguarda,

(1 + x) * (1 + y) = 1 + x + y

Questo significa che è possibile memorizzare i numeri con 1 sottratto, e invece di moltiplicare, basta sommare. Fino a quando i risultati sono sempre molto meno di 1, saranno abbastanza vicino per i risultati matematicamente precisi che non si preoccupano la differenza.

Modifica : appena notato: si dice più di loro sono molto vicino a 1. Ovviamente questa tecnica non funziona per i numeri che non sono vicino a 1 - che è, se x e y sono grandi. Ma se uno è grande e uno è piccolo, potrebbe ancora funzionare; vi interessa soltanto l'entità del x*y prodotto. (E se entrambi i numeri non sono vicino a 1, si può solo uso regolare moltiplicazione Java double ...)

Answer 2

Forse si potrebbe usare logaritmi?

logaritmi riducono convenientemente moltiplicazione di aggiunta.

Inoltre, per prendersi cura della perdita iniziale di precisione, v'è la funzione log1p (almeno, esiste in C / C ++), che restituisce log (1 + x) senza alcuna perdita di precisione. (Per esempio log1p (1e-30) restituisce 1e-30 per me)

Quindi è possibile utilizzare expm1 per ottenere la parte decimale del risultato effettivo.

Answer 3

Non è questo tipo di situazione esattamente quello BigDecimal è per?

A cura di aggiungere:

"Per il penultimo comma, preferirei evitare BigDecimals, se possibile, per motivi di prestazioni." - sanità mentale

"ottimizzazione prematura è la radice di tutti i mali" - Knuth

C'è una soluzione semplice praticamente su ordinazione per il vostro problema. Siete preoccupati che potrebbe non essere abbastanza veloce, così si vuole fare qualcosa di complicato che pensare sarà più veloce. La citazione Knuth viene abusato a volte, ma questo è esattamente la situazione che stava mettendo in guardia contro. Scrivilo il modo più semplice. Provalo. Il profilo it. Vedere se è troppo lento. Se si tratta di poi cominciare a pensare a modi per renderlo più veloce. Non aggiungere tutto questo complesso, codice aggiuntivo soggetto ad errori fino a quando si sa che è necessario.

Answer 4

A seconda di dove i numeri sono provenienti da e come si sono in uso, si consiglia di utilizzare razionali, invece di carri allegorici. Non è la risposta giusta per tutti i casi, ma quando si è la risposta giusta non c'è davvero nessun altro.

Se razionali non si adattano, io condivido la risposta logaritmi.

Modifica in risposta alla tua modifica:

Se avete a che fare con i numeri che rappresentano i tassi di risposta bassi, fanno ciò che gli scienziati fanno:

• le rappresentano come l'eccesso / deficit (normalizzare la parte 1.0)
• li scala. Pensare in termini di "parti per milione", o tutto ciò che è appropriato.

Questo vi lascerà che fare con i numeri ragionevoli per i calcoli.

Answer 5

È importante notare che si sta testando i limiti del proprio hardware, piuttosto che Java. Java usa la virgola mobile a 64 bit nella CPU.

Vi suggerisco di testare le prestazioni di BigDecimal prima di assumere che non sarà abbastanza veloce per voi. È ancora possibile fare decine di migliaia di calcoli al secondo con BigDecimal.

Answer 6

Come David fa notare, si può semplicemente aggiungere gli offset in su.

(1 + x) * (1 + y) = 1 + x + y + x * y

Tuttavia, sembra rischioso scegliere di abbandonare l'ultimo termine. Non farlo. Ad esempio, provate questo:

x = 1e-8 y = 2e-6 z = 3e-7 w = 4e-5

Ciò che è (1 + x) (1 + y) (1 + z) * (1 + w)? In doppia precisione, ottengo:

(1 + x) (1 + y) (1 + z) * (1 + w)

ans =

      1.00004231009302

Tuttavia, vedere cosa succede se dobbiamo solo fare il semplice approssimazione additivo.

1 + (x + y + z + w)

ans =

            1.00004231

Abbiamo perso i bit di ordine basso che possono essere state importanti. Questo è solo un problema se alcune delle differenze dal 1 nel prodotto sono almeno sqrt (EPS), dove eps è la precisione si sta lavorando.

Prova a modificare:

f = @ (u, v) u + v + u * v;

risultato = f (x, y);

risultato = f (risultato, z);

risultato = f (risultato, w);

1 + Risultato

ans =

      1.00004231009302

Come si può vedere, questo ci torna al risultato doppia precisione. In realtà, è un po 'più preciso, in quanto il valore interno del risultato è 4.23100930230249e-05.

Answer 7

Se si ha realmente bisogno la precisione, si dovrà usare qualcosa come BigDecimal, anche se è più lento di doppio.

Se non si ha realmente bisogno la precisione, si potrebbe forse andare con la risposta di David. Ma anche se si utilizza un sacco moltiplicazioni, potrebbe essere un po 'di ottimizzazione prematura, così BigDecimal potrebbe essere la strada da percorrere in ogni caso

Answer 8

Quando si dice "la maggior parte dei quali sono molto vicino a 1", quanti, esattamente?

Forse si potrebbe avere un implicito scostamento di 1 in tutti i vostri numeri e lavorare solo con le frazioni.