C/C++ rounding up decimals with a certain precision, efficiently

Question

I'm trying to optimize the following. The code bellow does this :

If a = 0.775 and I need precision 2 dp then a => 0.78

Basically, if the last digit is 5, it rounds upwards the next digit, otherwise it doesn't.

My problem was that 0.45 doesnt round to 0.5 with 1 decimalpoint, as the value is saved as 0.44999999343.... and setprecision rounds it to 0.4.

Thats why setprecision is forced to be higher setprecision(p+10) and then if it really ends in a 5, add the small amount in order to round up correctly.

Once done, it compares a with string b and returns the result. The problem is, this function is called a few billion times, making the program craw. Any better ideas on how to rewrite / optimize this and what functions in the code are so heavy on the machine?

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

I wrote an integer square root subroutine with nothing more than a couple dozen lines of ASM, with no API calls whatsoever - and it still could only do about 50 million SqRoots/second (this was about five years ago ...).

The point I'm making is that if you're going for billions of calls, even today's technology is going to choke.

But if you really want to make an effort to speed it up, remove as many API usages as humanly possible. This may require you to perform API tasks manually, instead of letting the libraries do it for you. Specifically, remove any type of stream operation. Those are slower than dirt in this context. You may really have to improvise there.

The only thing left to do after that is to replace as many lines of C++ as you can with custom ASM - but you'll have to be a perfectionist about it. Make sure you are taking full advantage of every CPU cycle and register - as well as every byte of CPU cache and stack space.

You may consider using integer values instead of floating-points, as these are far more ASM-friendly and much more efficient. You'd have to multiply the number by 10^7 (or 10^p, depending on how you decide to form your logic) to move the decimal all the way over to the right. Then you could safely convert the floating-point into a basic integer.

You'll have to rely on the computer hardware to do the rest.

<--Microsoft Specific-->
I'll also add that C++ identifiers (including static ones, as Donnie DeBoer mentioned) are directly accessible from ASM blocks nested into your C++ code. This makes inline ASM a breeze.
<--End Microsoft Specific-->

Answer 2

Depending on what you want the numbers for, you might want to use fixed point numbers instead of floating point. A quick search turns up this.

Answer 3

I think you can just add 0.005 for precision to hundredths, 0.0005 for thousands, etc. snprintf the result with something like "%1.2f" (hundredths, 1.3f thousandths, etc.) and compare the strings. You should be able to table-ize or parameterize this logic.

Answer 4

You could save some major cycles in your posted code by just making that double t[] static, so that it's not allocating it over and over.

Answer 5

Try this instead:

#include <cmath>

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

It's probably faster. Maybe try inlining it as well, but that might hurt if it doesn't help.

Example of how it works:

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

The .4999999999999 was chosen because of the precision for a c++ double on a 32 bit system. If you're on a 64 bit platform you'll probably need more nines. If you increase the nines further on a 32 bit system it overflows and rounds down instead of up, i. e. 234.00000000000001 gets truncated to 234 in a double in (my) 32 bit environment.

Answer 6

Using floating point (an inexact representation) means you've lost some information about the true number. You can't simply "fix" the value stored in the double by adding a fudge value. That might fix certain cases (like .45), but it will break other cases. You'll end up rounding up numbers that should have been rounded down.

Here's a related article: http://www.theregister.co.uk/2006/08/12/floating_point_approximation/

Answer 7

I'm taking at guess at what you really mean to do. I suspect you're trying to see if a string contains a decimal representation of a double to some precision. Perhaps it's an arithmetic quiz program and you're trying to see if the user's response is "close enough" to the real answer. If that's the case, then it may be simpler to convert the string to a double and see if the absolute value of the difference between the two doubles is within some tolerance.

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

Another possibility is to round the answer first (while it's still numeric) BEFORE converting it to a 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();
}

Both of these solutions should be faster than your sample code, but I'm not sure if they do what you really want.

Answer 8

As far as i see you are checking if a rounded on p points is equal b.

Insted of changing a to string, make other way and change string to double - (just multiplications and addion or only additoins using small table) - then substract both numbers and check if substraction is in proper range (if p==1 => abs(p-a) < 0.05)

Answer 9

Old time developers trick from the dark ages of Pounds, Shilling and pence in the old country.

The trick was to store the value as a whole number fo half-pennys. (Or whatever your smallest unit is). Then all your subsequent arithmatic is straightforward integer arithimatic and rounding etc will take care of itself.

So in your case you store your data in units of 200ths of whatever you are counting, do simple integer calculations on these values and divide by 200 into a float varaible whenever you want to display the result.

I beleive Boost does a "BigDecimal" library these days, but, your requirement for run time speed would probably exclude this otherwise excellent solution.

Answer 10

Looks like what you're trying to do is not a real rounding. 0.45 is indeed 0.45 in binary notation, and 0.44999999343 is not the same thing.

May be you need to do multiple rounding - first to say 3 decimal places, then to two, then to one.

The question is, what are you trying to accomplish? Should your match criterion be

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

instead?