C / C ++ arredondando decimais com uma certa precisão, de forma eficiente

Question

Eu estou tentando otimizar o seguinte. O código abaixo faz isso:

Se uma necessidade de precisão 2 dp = 0,775 e eu então a => 0,78

Basicamente, se o último dígito é 5, arredonda para cima o próximo dígito, caso contrário, não.

Meu problema era que 0,45 doesnt rodada para 0,5 com 1 decimalpoint, como o valor é guardado como 0,44999999343 .... e rodadas setprecision-lo para 0,4.

É por isso que setprecision é forçado a ser maior setprecision(p+10) e, em seguida, se ele realmente termina em um 5, adicione a pequena quantidade, a fim de arredondar para cima corretamente.

Uma vez feito isso, ele compara um com corda b e retorna o resultado. O problema é, esta função é chamada de alguns bilhões de vezes, tornando o craw programa. Quaisquer melhores ideias sobre como reescrever / otimizar isso e quais funções no código são tão pesadas na 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

Eu escrevi um sub-rotina raiz quadrada inteiro com nada mais do que uma dúzia de linhas de ASM, sem chamadas de API em absoluto - e ainda só poderia fazer cerca de 50 milhões de SqRoots / segundo (isto foi cerca de cinco anos atrás ...) .

O ponto que eu estou fazendo é que se você estiver indo para milhares de milhões de chamadas, mesmo a tecnologia de hoje vai sufocar.

Mas se você quiser realmente fazer um esforço para acelerá-lo, remover tantos usos da API como humanamente possível. Isso pode exigir que você execute tarefas de API manualmente, em vez de deixar as bibliotecas fazer isso por você. Especificamente, remover qualquer tipo de operação de fluxo. Aqueles são mais lentos do que a sujeira neste contexto. Você pode realmente ter que improvisar lá.

A única coisa que resta a fazer depois que é para substituir o maior número de linhas de C ++ como você pode com ASM costume - mas você vai ter que ser um perfeccionista sobre isso. Certifique-se de que você está aproveitando ao máximo cada ciclo de CPU e registrar - bem como cada byte de cache da CPU e espaço de pilha.

Você pode considerar o uso de valores inteiros em vez de flutuar pontos, uma vez que estas são muito mais amigável-ASM e muito mais eficiente. Você teria que multiplicar o número por 10 ^ 7 (ou 10 ^ p, dependendo de como você decidir formar sua lógica) para mover o decimal todo o caminho para a direita. Então você pode converter com segurança o ponto flutuante para um inteiro básico.

Você vai ter que contar com o hardware do computador para fazer o resto.

<--Microsoft Specific-->
Eu também vou acrescentar que identificadores de C ++ (incluindo as estáticas, como Donnie DeBoer mencionado) estão directamente acessíveis a partir de blocos ASM aninhados em seu código C ++. Isso faz com que ASM em linha uma brisa.
<--End Microsoft Specific-->

Answer 2

Dependendo do que você quer os números para, você pode querer usar números de ponto fixo em vez de ponto flutuante. Uma busca rápida vira para cima este .

Answer 3

Eu acho que você pode apenas adicionar 0,005 para a precisão de centésimos, 0,0005 para milhares, etc. snprintf o resultado com algo como "% 1.2f" (centésimos, milésimos 1.3f, etc.) e comparar as cordas. Você deve ser capaz de mesa-ize ou parametrizar essa lógica.

Answer 4

Você poderia salvar algumas grandes ciclos em seu código postado por apenas fazendo que estática dupla t [], de modo que não é sua atribuição mais e mais.

Answer 5

Tente isto em vez disso:

#include <cmath>

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

É provavelmente mais rápido. Talvez tente inlining-lo tão bem, mas isso dói poder se ele não ajuda.

Exemplo de como 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

O ,4999999999999 foi escolhido por causa da precisão por um c ++ dupla em um sistema de 32 bits. Se você estiver em uma plataforma de 64 bits, você provavelmente vai precisar de mais noves. Se você aumentar os noves ainda mais em um sistema de 32 bits ele transborda e arredonda para baixo em vez de para cima, i. e. 234,00000000000001 fica truncado para 234 em um duplo no (meu) 32 ambiente pouco.

Answer 6

Usando ponto flutuante (uma representação inexata) significa que você perdeu alguma informação sobre o número verdadeiro. Você não pode simplesmente "fix" o valor armazenado no duplo adicionando um valor fudge. Isso pode corrigir certos casos (como .45), mas ele vai quebrar outros casos. Você vai acabar arredondando números que deveria ter sido arredondada para baixo.

Aqui está um artigo relacionado: http://www.theregister.co.uk/2006/08/12 / floating_point_approximation /

Answer 7

Eu estou tomando a adivinhar o que você realmente quer fazer. Eu suspeito que você está tentando ver se uma string contém uma representação decimal de um duplo para alguma precisão. Talvez seja um programa de teste de aritmética e você está tentando ver se a resposta do usuário é "perto o suficiente" para a resposta real. Se for esse o caso, então ele pode ser mais simples para converter a string para um casal e ver se o valor absoluto da diferença entre as duas duplas é de alguma tolerância.

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];
}

Outra possibilidade é para arredondar a resposta primeiro (enquanto ainda é numérico) antes de convertê-lo para uma string.

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 as soluções devem ser mais rápido do que o seu código de exemplo, mas não tenho certeza se eles fazem o que você realmente quer.

Answer 8

Tanto quanto eu ver que você está verificando se um arredondado em pontos p é igual b.

Insted de mudar um a corda, fazer outra maneira e mudança string para o dobro - (apenas multiplicações e addion ou apenas additoins usando pequena mesa) - em seguida subtrair dois números e verificação se a subtracção é no intervalo correcto (se p == 1 => abs (p-a) <0,05)

Answer 9

Old desenvolvedores tempo truque da idade das trevas de libras, Shilling e pence no antigo país.

O truque era para armazenar o valor como um número inteiro fo meias-pennys. (Ou qualquer que seja sua unidade menor é). Então todo o seu arithmatic posterior é simples arithimatic inteiro e arredondando etc vai cuidar de si mesmo.

Assim, no seu caso, você armazenar seus dados em unidades de 200ths de tudo o que você está contando, fazer cálculos inteiros simples sobre esses valores e dividir por 200 em uma varaible flutuador sempre que você deseja exibir o resultado.

Eu impulso beleive faz uma biblioteca "BigDecimal" nos dias de hoje, mas, sua exigência para a velocidade tempo de execução provavelmente excluiria este caso contrário excelente solução.

Answer 10

parece com o que você está tentando fazer não é uma verdadeira arredondamento. 0,45 é realmente 0.45 em notação binária, e 0,44999999343 não é a mesma coisa.

Pode ser que você precisa fazer múltipla arredondamento -. Primeiro a dizer 3 casas decimais, em seguida, para dois, em seguida, para um

A questão é, o que você está tentando realizar? Se o seu critério de correspondência ser

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

em vez disso?