Cómo manejar la multiplicación de números próximos a 1

Question

Tengo un montón de números de punto (Java dobles), la mayoría de los cuales están muy cerca de 1 flotante, y tengo que multiplicarlos juntos como parte de un cálculo más grande. Necesito hacer esto mucho .

El problema es que mientras que los dobles Java tienen ningún problema con un número como:

0.0000000000000000000000000000000001 (1.0E-34)

no pueden representar algo como:

1.0000000000000000000000000000000001

Como consecuencia de esta pierdo precisión rápidamente (el límite parece estar alrededor 1.000000000000001 en dobles de Java).

He considerado simplemente almacenar los números con 1 resta, así que por ejemplo 1.0001 podría almacenarse como 0.0001 - pero el problema es que al multiplicarlos juntos de nuevo tengo que añadir al menos 1 y en este punto que pierda precisión

Para hacer frente a este que podría utilizar BigDecimals para realizar el cálculo (convertir a BigDecimal, añadir 1,0, luego se multiplica), y luego volver a convertir a los dobles después, pero tengo serias preocupaciones acerca de las implicaciones de rendimiento de esta.

Puede alguien ver una manera de hacer esto que evita el uso de BigDecimal?

Editar para mayor claridad : Esto es para un filtro de colaboración a gran escala, que emplea un algoritmo de optimización de descenso de gradiente. La precisión es un problema porque a menudo el filtro de colaboración está tratando con números muy pequeños (tales como la probabilidad de que una persona al hacer clic en un anuncio de un producto, que puede ser de 1 en 1000, o 1 en 10.000).

La velocidad es un problema porque el filtro de colaboración debe estar capacitado en decenas de millones de puntos de datos, si no más.

Answer 1

Sí: porque

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

En su caso, x y y son muy pequeñas, por lo x*y va a ser ahora más pequeño - demasiado pequeña para influir en los resultados de sus cálculos. En lo que a usted respecta,

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

Esto significa que puede almacenar los números con 1 sustraído, y en lugar de multiplicar, simplemente sumarlas. Siempre y cuando los resultados son siempre mucho menor que 1, que van a ser lo suficientemente cerca de los resultados matemáticamente precisas que no se preocupan por la diferencia.

editar : Sólo se dio cuenta: se dice más de ellos están muy cerca de 1. Es evidente que esta técnica no funcionará para los números que no están cerca de 1 - que es decir, si x y y son grandes. Pero si uno es grande y uno es pequeño, todavía podría funcionar; sólo se preocupan por la magnitud de la x*y producto. (Y si ambos números no están cerca de 1, sólo puede uso regular de multiplicación double Java ...)

Answer 2

Tal vez usted podría utilizar logaritmos?

logaritmos convenientemente reducen la multiplicación de adición.

Además, para cuidar de la pérdida inicial de precisión, existe el log1p función (por lo menos, existe en C / C ++), que devuelve log (1 + x) sin ninguna pérdida de precisión. (Por ejemplo log1p (1e-30) devuelve 1e-30 para mí)

A continuación, puede utilizar expm1 para obtener la parte decimal del resultado real.

Answer 3

No es este tipo de situación es exactamente lo BigDecimal para?

Editado para añadir:

"Por el penúltimo párrafo, yo preferiría evitar BigDecimals si es posible por razones de rendimiento." - cordura

"La optimización prematura es la raíz de todos los males" - Knuth

Hay una solución simple prácticamente hecho a la medida para su problema. Usted está preocupado que podría no ser lo suficientemente rápido, por lo que desea hacer algo complicado que pensar será más rápido. La cita Knuth se abusa a veces, pero esto es exactamente la situación que estaba advirtiendo. Escribirlo la forma más sencilla. Pruébalo. El perfil it. Ver si es demasiado lento. Si es después empezar a pensar en maneras de hacer que sea más rápido. No agregue todo este complejo, el código de error adicional propensas hasta que se sabe que es necesario.

Answer 4

Dependiendo de donde los números están viniendo y cómo se los está utilizando, es posible que desee utilizar números racionales en lugar de flotadores. No es la respuesta correcta para todos los casos, pero cuando es la respuesta correcta no hay realmente ninguna otra.

Si racionales no encajan, me adhiero a la respuesta logaritmos.

Editar en respuesta a tu edición:

Si se trata de números que representan las tasas de respuesta bajas, hacen lo que hacen los científicos:

• representarlos como el exceso / déficit (normalizar la parte 1.0)
• Escala ellos. Pensar en términos de "partes por millón" o lo que sea apropiado.

Esto dejará que se trata de un número razonable de cálculos.

Answer 5

Su pena señalar que se está probando los límites de su hardware en lugar de Java. Java utiliza el punto flotante de 64 bits en su CPU.

Le sugiero que probar el rendimiento de BigDecimal antes de asumir que no será lo suficientemente rápido para usted. Todavía se puede hacer decenas de miles de cálculos por segundo con BigDecimal.

Answer 6

Como señala David, que sólo puede añadir los desplazamientos hacia arriba.

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

Sin embargo, parece arriesgada para elegir a abandonar el último término. no lo hacen. Por ejemplo, intente lo siguiente:

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

¿Qué es (1 + x) (1 + y) (1 + z) * (1 + w)? En doble precisión, me sale:

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

ans =

      1.00004231009302

Sin embargo, ver qué sucede si sólo hacemos la aproximación simple aditivo.

1 + (x + y + z + w)

ans =

            1.00004231

Hemos perdido los bits de orden inferior que pueden haber sido importantes. Esto sólo es un problema si algunas de las diferencias con respecto a 1 en el producto son al menos sqrt (EPS), donde EPS es la precisión que se está trabajando.

Tal vez puedas probar:

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

resultado = f (x, y);

resultado = f (resultado, z);

resultado = f (resultado, w);

1 + resultar

ans =

      1.00004231009302

Como se puede ver, esto nos lleva de vuelta al resultado de doble precisión. De hecho, es un poco más precisa, ya que el valor interno de resultado es 4.23100930230249e-05.

Answer 7

Si realmente necesita la precisión, usted tendrá que usar algo como BigDecimal, incluso si es más lento que el doble.

Si realmente no necesita la precisión, tal vez podría ir con la respuesta de David. Pero incluso si se utiliza una gran cantidad multiplicaciones, podría ser cierta optimización prematura, por lo BIGDECIMAL podría ser el camino a seguir de todos modos

Answer 8

Cuando se dice "la mayoría de los cuales están muy cerca de 1", ¿cuántos exactamente?

Tal vez usted podría tener una implícita desplazamiento de 1 en todos sus números y sólo el trabajo con las fracciones.