C / C ++ redondeando los decimales con una cierta precisión, de manera eficiente

Question

Estoy tratando de optimizar la siguiente. El código de abajo hace esto:

Si a = 0,775 y necesito de precisión 2 dp entonces a => 0,78

Básicamente, si el último dígito es 5, se redondea hacia arriba al siguiente dígito, de lo contrario no.

Mi problema era que 0,45 ronda doesnt a 0,5 con 1 decimalpoint, como el valor se guarda como ,44999999343 .... y setprecision redondea a 0,4.

Es por eso que setprecision se ve obligado a ser más alta setprecision(p+10) y luego si realmente termina en un 5, añadir la pequeña cantidad con el fin de redondear correctamente.

Una vez hecho esto, se compara una con la cadena B y devuelve el resultado. El problema es que esta función se llama unos mil millones de veces, haciendo que el programa buche. Cualquier mejores ideas sobre cómo reescribir / optimizar este y qué funciones en el código son tan pesadas en la máquina?

bool match(double a,string b,int p) { //p = precision no greater than 7dp

    double t[] = {0.2, 0.02, 0.002, 0.0002, 0.00002, 0.000002, 0.0000002, 0.00000002};

    stringstream buff;
    string temp;

    buff << setprecision(p+10) << setiosflags(ios_base::fixed) << a; // 10 decimal precision
    buff >> temp;

    if(temp[temp.size()-10] == '5')  a += t[p]; // help to round upwards

    ostringstream test;
    test << setprecision(p) << setiosflags(ios_base::fixed) << a;
    temp = test.str();

    if(b.compare(temp) == 0) return true;

    return false;
}

Answer 1

he escrito una subrutina de la raíz cuadrada de enteros con nada más que un par de docenas de líneas ASM, sin llamadas a la API en absoluto - y todavía sólo podía hacer unos 50 millones de SqRoots / segundo (esto fue hace unos cinco años ...) .

El punto que estoy haciendo es que si vas para los mil millones de llamadas, incluso la tecnología de hoy en día se va a ahogar.

Pero si realmente quiere hacer un esfuerzo para acelerarlo, eliminar tantos usos de la API como sea humanamente posible. Esto puede requerir que realice tareas de API de forma manual, en lugar de dejar que las bibliotecas que lo haga por usted. Específicamente, eliminar cualquier tipo de operación de corriente. Esos son más lentas que la suciedad en este contexto. De verdad habrá que improvisar allí.

El único que queda por hacer después de eso es reemplazar la mayor cantidad de líneas de C ++ como puedas con ASM costumbre - pero usted tiene que ser un perfeccionista al respecto. Asegúrese de que está tomando el máximo provecho de cada ciclo de CPU y registra - al igual que todos los bytes de caché de CPU y espacio de pila.

Es posible considerar el uso de valores enteros en lugar de coma flotante puntos, ya que estos son mucho más ASM-amigable y mucho más eficiente. Habría que multiplicar el número por 10 ^ 7 (o 10 ^ p, dependiendo de cómo se decide formar su lógica) para mover el decimal todo el camino a la derecha. Posteriormente, se podría convertir de forma segura el punto flotante en un número entero básica.

Vas a tener que confiar en el hardware de la computadora para hacer el resto.

<--Microsoft Specific-->
También voy a añadir que los identificadores de C ++ (incluyendo los estáticos, como se ha mencionado Donnie DeBoer) son directamente accesibles desde ASM bloques anidados en su código C ++. Esto hace ASM en línea una brisa.
<--End Microsoft Specific-->

Answer 2

En función de lo que desea que los números para, es posible que desee utilizar los números de punto fijo en lugar de coma flotante. Una búsqueda rápida se convierte en imagen este .

Answer 3

Creo que se puede simplemente añadir 0,005 para una precisión de centésimas, 0,0005 por miles, etc. snprintf el resultado con algo como "% 1.2f" (centésimas, milésimas 1.3f, etc.) y comparar las cadenas. Usted debe ser capaz de tabla-ize o parametrizar esta lógica.

Answer 4

Se podría ahorrar algunos ciclos importantes en el código publicado con sólo hacer que la doble t [] estática, por lo que no está asignando una y otra vez.

Answer 5

Tal vez puedas probar:

#include <cmath>

double setprecision(double x, int prec) {
    return 
        ceil( x * pow(10,(double)prec) - .4999999999999)
        / pow(10,(double)prec);
}

Es probable que sea más rápido. Tal vez intente inlining tan bien, pero que podría lastimar si no ayuda.

Ejemplo de cómo funciona:

2.345* 100 (10 to the 2nd power) = 234.5
234.5 - .4999999999999 = 234.0000000000001
ceil( 234.0000000000001 ) = 235
235 / 100 (10 to the 2nd power) = 2.35

El ,4999999999999 fue elegido debido a la precisión para una c ++ doble en un sistema de 32 bits. Si estás en una plataforma de 64 bits es probable que necesite más nueves. Si aumenta de punta en blanco sobre un sistema de 32 bits que se desborda y se redondea hacia abajo en vez de hacia arriba, i. mi. 234.00000000000001 se trunca a 234 en un doble en (mi) entorno de 32 bits.

Answer 6

El uso de punto flotante (una representación inexacta) significa que has perdido alguna información sobre el número real. No se puede simplemente "fijar" el valor almacenado en el doble añadiendo un valor fudge. Eso podría fijar ciertos casos (como 0.45), pero se romperá otros casos. Usted va a terminar redondeando los números que deberían haber sido redondeado hacia abajo.

Aquí hay un artículo relacionado: http://www.theregister.co.uk/2006/08/12 / floating_point_approximation /

Answer 7

Me estoy tomando en suposición de lo que realmente quieren decir que hacer. Sospecho que está tratando de ver si una cadena contiene una representación decimal de un doble a cierta precisión. Quizás es un programa concurso de la aritmética y que está tratando de ver si la respuesta del usuario es "lo suficientemente cerca" a la verdadera respuesta. Si ese es el caso, entonces puede ser más fácil de convertir la cadena en un doble y ver si el valor absoluto de la diferencia entre los dos dobles está dentro de una cierta tolerancia.

double string_to_double(const std::string &s)
{
    std::stringstream buffer(s);
    double d = 0.0;
    buffer >> d;
    return d;
}

bool match(const std::string &guess, double answer, int precision)
{
    const static double thresh[] = { 0.5, 0.05, 0.005, 0.0005, /* etc. */ };
    const double g = string_to_double(guess);
    const double delta = g - answer;
    return -thresh[precision] < delta && delta <= thresh[precision];
}

Otra posibilidad es redondear la respuesta primero (mientras todavía numérico) antes de convertirlo en una cadena.

bool match2(const std::string &guess, double answer, int precision)
{
    const static double thresh[] = {0.5, 0.05, 0.005, 0.0005, /* etc. */ };
    const double rounded = answer + thresh[precision];
    std::stringstream buffer;
    buffer << std::setprecision(precision) << rounded;
    return guess == buffer.str();
}

Ambas soluciones deben ser más rápido que el código de ejemplo, pero no estoy seguro si lo hacen lo que realmente quiere.

Answer 8

Por lo que yo veo que está comprobando si un redondeado en los puntos P es igual a b.

Insted de cambiar una cadena a, hacer otra cadena camino y el cambio de duplicar - (sólo multiplicaciones y addion o sólo additoins utilizando pequeña mesa) - a continuación, sustraer ambos números y comprobar si sustracción está en el rango correcto (si p == 1 => abs (p-a) <0,05)

Answer 9

desarrolladores de tiempo viejo truco de la edad oscura de libras, chelines y peniques en el viejo país.

El truco consistía en almacenar el valor como un número entero fo medias pennys. (O lo que su unidad más pequeña es). Entonces todo su aritmética posterior es sencillo arithimatic número entero y el redondeo, etc va a cuidar de sí mismo.

Así que en su caso se almacenan los datos en unidades de 200ths de lo que usted está contando, hacer los cálculos de enteros simples en estos valores y dividir por 200 en un flotador varaible cada vez que desea mostrar el resultado.

Boost que creo que tendría una biblioteca "BigDecimal" en estos días, pero, su imperativo de celeridad tiempo de ejecución probablemente excluir este excelente solución.

Answer 10

Parece que lo que estamos tratando de hacer no es un verdadero redondeo. 0,45 0,45 es de hecho en notación binaria, y ,44999999343 no es lo mismo.

Puede ser que usted tiene que hacer múltiples redondeo -. Primero en decir 3 lugares decimales, a continuación, a dos, y luego a uno

La pregunta es, ¿qué estás tratando de lograr? Debe ser su criterio de coincidencia

abs(a-b) < 10 ** -p

en lugar?