Unexpected output of c++ program

Question

I was solving http://codeforces.com/problemset/problem/552/B.

In my first attempt I came up with something like:

#include <bits/stdc++.h>
using namespace std;
int digit(long a){
    int i=0;
    while(a){
        a/=10;
        i++;
    }
    return i;
}
int main()
{
    long n;
    long long s=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    int dig=digit(n),i=0;
    while(i<dig){
        s+=(n-pow(10,i)+1);
        i++;
    }
    cout<<s;
    return 0;
}

But for input

1000000

My program outputed

5888895

I was expecting

5888896

In my second try I wrote pow function for myself:

#include <bits/stdc++.h>
using namespace std;
int digit(long a){
    int i=0;
    while(a){
        a/=10;
        i++;
    }
    return i;
}
long long pow1(int a){
    long long s=1;
    while(a--){
        s*=10;
    }
    return s;
}
int main()
{
    long n;
    long long s=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    int dig=digit(n),i=0;
    while(i<dig){
        long long aux=pow1(i);
        s+=(n-aux+1);
        i++;
    }
    cout<<s;


    return 0;
}

And this time it was correct.How can one explain the working behind it?

Answer 1

The problem with the built-in pow function is that is does not work as accurate as your function. pow calculates x to the y as exp(y*log(x)). This generic formula works with all (even non-integral) exponents, and its performance is (mostly) independent on the arguments. The problem with that formula is, that pow(10,2) might be 99.9, which gets truncated to 99 when it is converted to an integer type. Try pow(10,i) + 0.5 to perform proper rounding.