post

Add Epsilon Before Casting Double to Integer!

Problem: Given a real number in exactly two digits after the decimal point, and another integer. Print their product, rounded down to the nearest integer.

You may start to code this way:

double a;
int b;
cin >> a >> b;
int c = a * b;
cout << c << endl;

Do you think this is correct? Well, almost. Now, try this input:

0.94 8700

What will the output be?

You pick a calculator and it says “8178”. If you also answer “8178” to this problem, then you are wrong.

Why? Because the multiplication is not done in exact; there will be a slight error. If you print (a * b) in fifteen digits after the decimal point, you will likely get this output:

8177.999999999999091

which is less than 8178, therefore, rounded down to 8177 when it is cast.

This annoying pitfall happened to me in Codeforces Beta Round #81, Problem A. This problem was supposed to be the easiest problem in the set, however, there were only about one fourth of the solutions passing the system test. Almost all failed solutions got hacked with this rounding error case.

So, the solution is either to parse manually the two digits after the decimal point, or add an epsilon (a very small value) to the result:

double a;
int b;
cin >> a >> b;
int c = a * b + 1e-8;   // epsilon = 10^-8
cout << c << endl;

And you will get the correct result.

So, as the title says: add an epsilon before casting doubles to integers.

As a programmer, this is important to know. Has this case ever happened to you? If yes, do you have a more elegant solution?

About Ashar Fuadi

Ashar Fuadi is a competitive programmer from University of Indonesia. He loves to code, especially for TopCoder SRM, Codeforces, and ICPC.
Follow Ashar on Google+ and Twitter.

Comments

  1. anonymous says:

    0.94 * 8700 = (94/100) * (87 *100) = 94 * 87 = 8178
    Why “8178” answer is wrong? I don’t get it

    • Code the solution, and it will print 8177. Try that. 🙂

    • I think u’ve made a mistake here :
      “You pick a calculator and it says 8178?. If you also answer 8178? to this problem, then you are wrong.”

      from that sentence one would imply you say the correct answer was not 8178.

      But from your reply here, I think what you really want to say is 8178 is correct, but the program will print 8177 because of slight error.

    • The correct answer for the output of the program is 8177. The *real* correct answer is 8178 😀

  2. Hai, in mathematics it should be 0.94 x 8700 is 8178, why when we print the answer is 8177.999999999999091 ?

    I dont understand.

    • Because there is a slight error when computer multiplies 0.94 (in binary) with 8700 (in binary), as multiplication in floating points is done in quite complex way.

  3. how do we define epsilon value ? is it double minimal value ?

    is it always plus epsilon, not negative epsilon ?

  4. Ali Jaya Meilio says:

    In programming world, floating point number is represented as bits.
    Double is a 64 bits floating point number.

    it’s called “floating” because the decimal point (binary point) can floating around and changed the precision. It contrasts with fixed point number.

    Double has 1 bit for sign (positive negative), 11 bits for exponent, and 52 bits for significand / mantissa.

    It’s arranged like this
    seeeeeeeeeeemmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

    So if we translate each component to integer, the sign have range from 0 to 1, the exponent has range from 0 to 2^11-1 (2047), and the mantissa has range from 0 to 2^52.
    We call the integer representation of sign with S, the exponent with E, and the mantissa with M.

    so the real double representation is
    value = (-1)^S * M * 2^(E-1023)

    The sign, if it has value of 0, the value will be positive ((-1)^0 = 1), if it has value of 1, the value will be negative ((-1)^1 = -1).

    The mantissa is the precision value, and 2^(E-1023) is the one who change the binary point.

    To understand easily, we can change the base from 2 to 10.
    If the real value defined as this
    value = (-1)^S * M * 10^(E-1023)

    Say we have value 356, so the representation is S = 0, M = 356, and E = 1023.
    If we have value 3.56, the representation is S = 0, M = 356, and E = 1021.
    and -35600, the representation is S = 1, M = 356, and E = 1025.

    Quite easy isn’t it?

    And the multiplication come easier… say we have value A and B
    A = (-1)^Sa * Ma * 2^(Ea – 1023)
    B = (-1)^Sb * Mb * 2^(Eb – 1023)
    So if we have C = A * B, then the actual C can be calculated as this
    C = A * B
    C = (-1)^Sa * Ma * 2^(Ea – 1023) * (-1)^Sb * Mb * 2^(Eb – 1023)
    C = (-1)^(Sa+Sb) * (Ma * Mb) * 2^(Ea + Eb – 2026)
    So we can say
    Sc = Sa + Sb
    Mc = Ma * Mb
    Ec = Ea + Eb – 1023

    It’s all integer operation no floating point evolved… Not that complex huh?

    And as you can see, if the value doesnt overflow (Ma * Mb doesn’t exceed 2^52-1, if it does, then we must change the exponent with lost of precision), the precision maintained.

    So if the Ma and Mb small enough, it doesn’t lost precision.

    So why in the example it’s lost it precision?, because we write in the input as decimal, but in the computerized version it need to be binary point (binary with decimal if you can say), so it translate from decimal to binary point and this where it lost the precision.

    So we lost precision when the compiler translate from decimal to binary point, and the multiplication doesn’t lost the precision if the mantissa is small enough, but the translation from decimal to binary can make the mantissa so big, so it can lost the precision during multiplication…

    Sorry for the long post :v… I kinda bored and need something to do :v

  5. _jarvis_ says:

    but if we do the following ,
    double a=0.94;
    int x=8700;
    cout<<a*8700;

    why do we get the correct answer

  6. _jarvis_ says:

    and even in this case too we get the *real* correct answer,

    double a=0.94;
    int x=8700;
    double c=a*x;
    cout<<c<<endl;

    is there a way we can predict that there would be or a possibility of a faulty answer ?

Speak Your Mind

*