c++ - name - meta title html
¿En qué orden se deben agregar flotadores para obtener el resultado más preciso? (11)
Esta fue una pregunta que me hicieron en mi reciente entrevista y quiero saber (en realidad no recuerdo la teoría del análisis numérico, así que por favor ayúdenme :)
Si tenemos alguna función, que acumula números de coma flotante:
std::accumulate(v.begin(), v.end(), 0.0);
v es un std::vector<float> , por ejemplo.
¿Sería mejor ordenar estos números antes de acumularlos?
¿Qué orden daría la respuesta más precisa?
Sospecho que ordenar los números en orden ascendente realmente reduciría el error numérico, pero desafortunadamente no puedo probarlo yo mismo.
PD. Me doy cuenta de que esto probablemente no tiene nada que ver con la programación del mundo real, solo que es curioso.
Creo que puedes hacerlo mejor que ordenar los números antes de acumularlos, porque durante el proceso de acumulación, el acumulador se hace cada vez más grande. Si tiene una gran cantidad de números similares, comenzará a perder precisión rápidamente. Esto es lo que sugeriría en su lugar:
while the list has multiple elements
remove the two smallest elements from the list
add them and put the result back in
the single element in the list is the result
Por supuesto, este algoritmo será más eficiente con una cola de prioridad en lugar de una lista. Código C ++:
template <typename Queue>
void reduce(Queue& queue)
{
typedef typename Queue::value_type vt;
while (queue.size() > 1)
{
vt x = queue.top();
queue.pop();
vt y = queue.top();
queue.pop();
queue.push(x + y);
}
}
conductor:
#include <iterator>
#include <queue>
template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type
reduce(Iterator begin, Iterator end)
{
typedef typename std::iterator_traits<Iterator>::value_type vt;
std::priority_queue<vt> positive_queue;
positive_queue.push(0);
std::priority_queue<vt> negative_queue;
negative_queue.push(0);
for (; begin != end; ++begin)
{
vt x = *begin;
if (x < 0)
{
negative_queue.push(x);
}
else
{
positive_queue.push(-x);
}
}
reduce(positive_queue);
reduce(negative_queue);
return negative_queue.top() - positive_queue.top();
}
Los números en la cola son negativos porque la top produce el mayor número, pero queremos la más pequeña . Pude haber proporcionado más argumentos de plantilla a la cola, pero este enfoque parece más simple.
El tipo más simple que mejora la precisión es ordenar por el valor absoluto ascendente. Eso permite que los valores de magnitud más pequeños tengan la posibilidad de acumularse o cancelarse antes de interactuar con valores de magnitud mayores que podrían provocar una pérdida de precisión.
Dicho esto, puede hacer mejor al rastrear múltiples sumas parciales que no se superponen. Aquí hay un documento que describe la técnica y presenta una prueba de precisión: www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps
Ese algoritmo y otros enfoques para la suma exacta de coma flotante se implementan en Python simple en: http://code.activestate.com/recipes/393090/ Al menos dos de ellos se pueden convertir trivialmente a C ++.
En cuanto a la clasificación, me parece que si espera una cancelación, los números deben agregarse en orden descendente de magnitud, no de forma ascendente. Por ejemplo:
((-1 + 1) + 1e-20) dará 1e-20
pero
((1e-20 + 1) - 1) dará 0
En la primera ecuación, se cancelan dos números grandes, mientras que en el segundo el término 1e-20 se pierde cuando se agrega a 1, ya que no hay suficiente precisión para retenerlo.
Además, la suma por parejas es bastante decente para sumar muchos números.
Esto no responde completamente a su pregunta, pero una cosa inteligente es ejecutar la suma dos veces, una con el modo de redondeo "redondear hacia arriba" y otra con "redondear hacia abajo". Compara las dos respuestas, y sabes / cómo / inexactas son tus resultados, y si por lo tanto necesitas usar una estrategia de suma más inteligente. Desafortunadamente, la mayoría de los idiomas no hacen que cambiar el modo de redondeo de coma flotante sea tan fácil como debería ser, porque las personas no saben que es realmente útil en los cálculos diarios.
Eche un vistazo a la aritmética Interval donde hace todas las matemáticas como esta, manteniendo los valores más altos y más bajos sobre la marcha. Lleva a algunos resultados interesantes y optimizaciones.
Existe una clase de algoritmos que resuelve este problema exacto, sin la necesidad de ordenar o reordenar los datos .
En otras palabras, la suma se puede hacer de una sola vez sobre los datos. Esto también hace que dichos algoritmos sean aplicables en situaciones donde el conjunto de datos no se conoce de antemano, por ejemplo, si los datos llegan en tiempo real y la suma en ejecución debe mantenerse.
Aquí está el resumen de un artículo reciente:
Presentamos un novedoso algoritmo en línea para la suma exacta de una secuencia de números de coma flotante. Por "en línea" nos referimos a que el algoritmo necesita ver solo una entrada a la vez, y puede tomar una secuencia de entrada de longitud arbitraria de tales entradas mientras requiere solo memoria constante. Por "exacto" queremos decir que la suma de la matriz interna de nuestro algoritmo es exactamente igual a la suma de todas las entradas, y el resultado devuelto es la suma redondeada correctamente. La prueba de corrección es válida para todas las entradas (incluidos los números no normalizados pero el desbordamiento intermedio del módulo), y es independiente del número de sumandos o del número de condición de la suma. El algoritmo necesita asintóticamente solo 5 FLOP por summand y, debido al paralelismo de nivel de instrucción, se ejecuta solo aproximadamente 2-3 veces más lento que el obvio y rápido pero "tonto recuento recursivo ordinario" cuando el número de sumandos es mayor que 10,000 . Por lo tanto, hasta donde sabemos, es el algoritmo conocido más rápido, preciso y con mayor capacidad de memoria. De hecho, es difícil ver cómo un algoritmo más rápido o uno que requiera significativamente menos FLOP podría existir sin mejoras de hardware. Se proporciona una aplicación para una gran cantidad de sumandos.
Fuente: Algoritmo 908: suma exacta en línea de flujos de punto flotante .
Para IEEE 754 de precisión simple o doble o números de formato conocidos, otra alternativa es usar una matriz de números (aprobada por la persona que llama, o en una clase para C ++) indexada por el exponente. Al agregar números en la matriz, solo se agregan los números con el mismo exponente (hasta que se encuentre una ranura vacía y se almacene el número). Cuando se solicita una suma, la matriz se suma de menor a mayor para minimizar el truncamiento. Ejemplo de precisión simple:
/* clear array */
void clearsum(float asum[256])
{
size_t i;
for(i = 0; i < 256; i++)
asum[i] = 0.f;
}
/* add a number into array */
void addtosum(float f, float asum[256])
{
size_t i;
while(1){
/* i = exponent of f */
i = ((size_t)((*(unsigned int *)&f)>>23))&0xff;
if(i == 0xff){ /* max exponent, could be overflow */
asum[i] += f;
return;
}
if(asum[i] == 0.f){ /* if empty slot store f */
asum[i] = f;
return;
}
f += asum[i]; /* else add slot to f, clear slot */
asum[i] = 0.f; /* and continue until empty slot */
}
}
/* return sum from array */
float returnsum(float asum[256])
{
float sum = 0.f;
size_t i;
for(i = 0; i < 256; i++)
sum += asum[i];
return sum;
}
ejemplo de doble precisión:
/* clear array */
void clearsum(double asum[2048])
{
size_t i;
for(i = 0; i < 2048; i++)
asum[i] = 0.;
}
/* add a number into array */
void addtosum(double d, double asum[2048])
{
size_t i;
while(1){
/* i = exponent of d */
i = ((size_t)((*(unsigned long long *)&d)>>52))&0x7ff;
if(i == 0x7ff){ /* max exponent, could be overflow */
asum[i] += d;
return;
}
if(asum[i] == 0.){ /* if empty slot store d */
asum[i] = d;
return;
}
d += asum[i]; /* else add slot to d, clear slot */
asum[i] = 0.; /* and continue until empty slot */
}
}
/* return sum from array */
double returnsum(double asum[2048])
{
double sum = 0.;
size_t i;
for(i = 0; i < 2048; i++)
sum += asum[i];
return sum;
}
Probé el ejemplo extremo en la respuesta proporcionada por Steve Jessop.
#include <iostream>
#include <iomanip>
#include <cmath>
int main()
{
long billion = 1000000000;
double big = 1.0;
double small = 1e-9;
double expected = 2.0;
double sum = big;
for (long i = 0; i < billion; ++i)
sum += small;
std::cout << std::scientific << std::setprecision(1) << big << " + " << billion << " * " << small << " = " <<
std::fixed << std::setprecision(15) << sum <<
" (difference = " << std::fabs(expected - sum) << ")" << std::endl;
sum = 0;
for (long i = 0; i < billion; ++i)
sum += small;
sum += big;
std::cout << std::scientific << std::setprecision(1) << billion << " * " << small << " + " << big << " = " <<
std::fixed << std::setprecision(15) << sum <<
" (difference = " << std::fabs(expected - sum) << ")" << std::endl;
return 0;
}
Obtuve el siguiente resultado:
1.0e+00 + 1000000000 * 1.0e-09 = 2.000000082740371 (difference = 0.000000082740371)
1000000000 * 1.0e-09 + 1.0e+00 = 1.999999992539933 (difference = 0.000000007460067)
El error en la primera línea es más de diez veces mayor en el segundo.
Si cambio las double s para float en el código anterior, obtengo:
1.0e+00 + 1000000000 * 1.0e-09 = 1.000000000000000 (difference = 1.000000000000000)
1000000000 * 1.0e-09 + 1.0e+00 = 1.031250000000000 (difference = 0.968750000000000)
Ninguna de las respuestas está cerca de 2.0 (pero la segunda está un poco más cerca).
Usando la suma de Kahan (con double s) como describe Daniel Pryden:
#include <iostream>
#include <iomanip>
#include <cmath>
int main()
{
long billion = 1000000000;
double big = 1.0;
double small = 1e-9;
double expected = 2.0;
double sum = big;
double c = 0.0;
for (long i = 0; i < billion; ++i) {
double y = small - c;
double t = sum + y;
c = (t - sum) - y;
sum = t;
}
std::cout << "Kahan sum = " << std::fixed << std::setprecision(15) << sum <<
" (difference = " << std::fabs(expected - sum) << ")" << std::endl;
return 0;
}
Me sale exactamente 2.0:
Kahan sum = 2.000000000000000 (difference = 0.000000000000000)
E incluso si cambio las double s para float en el código de arriba, obtengo:
Kahan sum = 2.000000000000000 (difference = 0.000000000000000)
¡Parece que Kahan es el camino a seguir!
Sobre la base de la respuesta de Steve de ordenar primero los números en orden ascendente, presentaría dos ideas más:
Decide la diferencia en el exponente de dos números por encima de los cuales podrías decidir que perderías demasiada precisión.
Luego agregue los números en orden hasta que el exponente del acumulador sea demasiado grande para el siguiente número, luego coloque el acumulador en una cola temporal y comience el acumulador con el siguiente número. Continúa hasta agotar la lista original.
Repite el proceso con la cola temporal (después de haberlo ordenado) y con una diferencia posiblemente mayor en el exponente.
Creo que esto será bastante lento si tienes que calcular exponentes todo el tiempo.
Tuve un rápido avance con un programa y el resultado fue 1.99903
Su instinto es básicamente correcto, ordenar en orden ascendente (de magnitud) generalmente mejora algo las cosas. Considere el caso donde estamos agregando flotantes de precisión simple (32 bits), y hay mil millones de valores equivalentes a 1 / (1 mil millones), y un valor igual a 1. Si el 1 es primero, entonces la suma vendrá a 1, ya que 1 + (1/1 mil millones) es 1 debido a la pérdida de precisión. Cada adición no tiene ningún efecto en el total.
Si los valores pequeños vienen primero, al menos sumarán algo, aunque incluso entonces tengo 2 ^ 30 de ellos, mientras que después de 2 ^ 25 o así estoy de vuelta en la situación en la que cada uno individualmente no está afectando el total nunca más. Así que todavía voy a necesitar más trucos.
Ese es un caso extremo, pero en general agregar dos valores de magnitud similar es más preciso que agregar dos valores de magnitudes muy diferentes, ya que "descarta" menos bits de precisión en el valor más pequeño de esa manera. Al ordenar los números, agrupa valores de magnitud similar y, al sumarlos en orden ascendente, otorga a los valores pequeños la "posibilidad" de alcanzar acumulativamente la magnitud de los números mayores.
Aún así, si se trata de números negativos, es fácil "burlar" este enfoque. Considere tres valores para sumar, {1, -1, 1 billionth} . La suma aritméticamente correcta es 1 billionth , pero si mi primera suma implica el valor mínimo, entonces mi suma final será 0. De las 6 órdenes posibles, solo 2 son "correctas" - {1, -1, 1 billionth} y {-1, 1, 1 billionth} . Las 6 órdenes dan resultados que son precisos a la escala del valor de mayor magnitud en la entrada (0.0000001% de salida), pero para 4 de ellos el resultado es incorrecto en la escala de la solución verdadera (100% de salida). El problema particular que está resolviendo le dirá si el primero es lo suficientemente bueno o no.
De hecho, puedes jugar muchos más trucos que solo agregarlos en orden ordenado. Si tiene muchos valores muy pequeños, un número medio de valores intermedios y un número pequeño de valores grandes, entonces podría ser más preciso sumar primero todos los pequeños, luego sumar por separado los medianos, sumar esos dos totales juntos, luego agregue los grandes. No es del todo trivial encontrar la combinación más precisa de adiciones de coma flotante, pero para lidiar con casos realmente malos puede mantener una gran variedad de totales acumulados en diferentes magnitudes, agregue cada nuevo valor al total que mejor se adapte a su magnitud, y cuando un total acumulado comienza a ser demasiado grande para su magnitud, agréguelo al siguiente total y comience uno nuevo. Llevado a su extremo lógico, este proceso es equivalente a realizar la suma en un tipo de precisión arbitraria (por lo que haría eso). Pero dada la opción simplista de agregar en orden de magnitud ascendente o descendente, la mejor apuesta es ascender.
Tiene cierta relación con la programación del mundo real, ya que hay algunos casos en los que su cálculo puede ir muy mal si corta accidentalmente una cola "pesada" que consiste en una gran cantidad de valores, cada uno de los cuales es demasiado pequeño para afectar individualmente la suma, o si arroja demasiada precisión de una gran cantidad de pequeños valores que individualmente solo afectan los últimos bits de la suma. En los casos en que la cola es insignificante de todos modos, probablemente no le importe. Por ejemplo, si solo está sumando un pequeño número de valores en primer lugar y solo está usando algunas cifras significativas de la suma.
También hay un algoritmo diseñado para este tipo de operación de acumulación, llamado Kahan Summation , del que probablemente debas estar consciente.
De acuerdo con Wikipedia,
El algoritmo de suma de Kahan (también conocido como suma compensada ) reduce significativamente el error numérico en el total obtenido al agregar una secuencia de números de coma flotante de precisión finita, en comparación con el enfoque obvio. Esto se hace manteniendo una compensación de ejecución separada (una variable para acumular pequeños errores).
En pseudocódigo, el algoritmo es:
function kahanSum(input) var sum = input[1] var c = 0.0 //A running compensation for lost low-order bits. for i = 2 to input.length y = input[i] - c //So far, so good: c is zero. t = sum + y //Alas, sum is big, y small, so low-order digits of y are lost. c = (t - sum) - y //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y) sum = t //Algebraically, c should always be zero. Beware eagerly optimising compilers! next i //Next time around, the lost low part will be added to y in a fresh attempt. return sum
Tus flotadores se deben agregar con doble precisión. Eso le dará más precisión adicional que cualquier otra técnica. Para obtener un poco más de precisión y una velocidad significativamente mayor, puede crear, por ejemplo, cuatro sumas y sumarlas al final.
Si está agregando números de doble precisión, use el doble largo para la suma; sin embargo, esto solo tendrá un efecto positivo en implementaciones donde el doble largo en realidad tiene más precisión que el doble (normalmente x86, PowerPC depende de la configuración del compilador).