views:

1733

answers:

10

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;
}
+2  A: 

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.

kwatford
+2  A: 

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-->

Giffyguy
Though I originally suggested that multiplying by 10^p would work, it doesn't (at least not in general). Floating point numbers are inherently imprecise. When you store a value as a floating point, you lose information about the original value. If the F.P. value is 0.4449999, you can not reasonably assume that represents 0.45. Therefore, multiplying to move digits around doesn't actually "fix" anything - it introduces additional imprecision (eg. multiplying by 100, which actually may be stored as 100.0124) that turns out looking like what you expected, but it's not a general solution.
Donnie DeBoer
Good thinking! See my comment on Donnie DeBoer's second answer.
Giffyguy
+2  A: 

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.

Bill Hoag
But that would make it round up no matter what. I think he is trying to round down when appropriate as well.
Giffyguy
Actually, I think this works (don't think it will be fast though). For example, to round to the nearest hundredth, 1.014 would round down to 1.01 (1.014 + .005 = 1.019, truncate to 2 decimal places), but 1.017 would round up to 1.02 (1.017 + .005 = 1.022, truncate to 2 decimal places).
Matt J
+2  A: 

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.

Donnie DeBoer
This is excellent advice as well. Static vars can definitely speed things up when used in the correct context.
Giffyguy
In fact that array is a perfect candidate for "static const"
Giffyguy
static const will cause your array to not exist at all in the final code. The compiler will directly inject the individual constant values when they are used, instead of having to dereference the pointer and perform the pointer arithmetic to access the array.
Giffyguy
Doesn't hurt of course, but it's no guaranteed win either. The compiler/optimzier can already see it's effectively static const anyway.
MSalters
A: 

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?

Arkadiy
I don't think 0.45 can be expressed in binary notation. It's 9/20, and 20 is 2 * 2 * 5. Unless you can get the denominator to be a power of two after reduction, you can't express it in binary.
David Thornley
Perhaps. But printf with %.10f produces 0.4500000000 for 0.45, so 0.4499999934 has to be different.
Arkadiy
One last word:(gdb) p 0.45$33 = 0.45000000000000001
Arkadiy
+1  A: 

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/

Donnie DeBoer
Another excellent point. This is something we have to take into account, considering that floating-point operations need to be avoided if the code is going to run any faster. I generally believe that this is the point where the term "approximation" really takes meaning. What are the chances of the number being so close to .5 that it could round the wrong way? Floating-point numbers are not 100% precise, and there's generally no way to get around that fact. I believe that at this point we just have to assume that it will round correctly 99.9% of the time, and be satisfyed with that statistic.
Giffyguy
+1  A: 

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.

plastic chris
A: 

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.

Adrian McCarthy
A: 

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)

ralu
A: 

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.

James Anderson