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?

You should never include internal standard library headers. In your case, `#include ` instead. Why do you call `cin.tie` and `ios_base::sync_with_stdio`? See [YAGNI](https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it) principle. — Ivan Aksamentov - Drop, Jul 18 '15 at 09:57
@Drop I included cin.tie and ios_base::sync_with_stdio to make my program faster and included it in both of the programs. It has got nothing to do with change in values I suppose. — Gaurav Jain, Jul 18 '15 at 09:59
@Drop Read about it here: http://abhisharlives.blogspot.in/2012/06/really-fast-io-methods-for-programming.html and get to know about it for yourself. :P — Gaurav Jain, Jul 18 '15 at 10:05
The first version of program gives me expected `5888896` on Windows + VS2013 as well as MinGW GCC 5.1.0. What compiler, compiler version, standard library, standard library version and OS do you use? — Ivan Aksamentov - Drop, Jul 18 '15 at 10:06
@Drop Just get my first solution accepted on codeforces and you will get errors as I got. And then get the second one accepted. And look for which test cases did the first one fail. btw I use windows 7(64 bit) + codeblocks — Gaurav Jain, Jul 18 '15 at 10:09
I don't know what is codeforce and which toolchain they use. Does your compiler shipped with codeblocks gives you expected result? — Ivan Aksamentov - Drop, Jul 18 '15 at 10:15
Have you tried to remove non-standard includes and super-fast but useless io? — Ivan Aksamentov - Drop, Jul 18 '15 at 10:17
Remember, `pow` returns type `double`, and the problem is geared towards integer arithmetic. Just like when people do things like `double d = 0.1; if (d == 0.1)` and get unexpected behavior, you're going to enter a world of pain when mixing floating and fixed point arithmetic or comparing doubles directly. — Cloud, Jul 26 '15 at 17:41
@Dogbert But here I am comparing discrete values in while loop and that should not be a problem and the thing you mentioned is not unexpected. It is due to the fact that floating point or doubles are stored as binary no.s and are not infinitely accurate. — Gaurav Jain, Jul 27 '15 at 07:16
@GauravJain This question might provided a bit more insight. http://stackoverflow.com/questions/9704195/why-pow10-5-9-999-in-c In your problem, you are summing floating- and fixed-point values: `s+=(n-pow(10,i)+1);`. You never want to do this unless you are dead certain of the result. In signal processing, the floating point value is often converted to fixed point and stored in `Qm.n` format or similar (https://en.wikipedia.org/wiki/Q_%28number_format%29). This problem arises a lot in homework assignments where one must sum a bunch of doubles, but sort them first, or the result is wrong. — Cloud, Jul 27 '15 at 14:11

score 2 · Accepted Answer · answered Jul 26 '15 at 18:06

2

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.

answered Jul 26 '15 at 18:06

Michael Karcher

3,803
1
14
25

Thanks! Can you kindly suggest me some reference where I can validate this? – Gaurav Jain Jul 27 '15 at 07:11
1

The C Standard (at least the draft in n1124) says in chapter 5.2.4.2.2(characteristics of float types), paragraph 5: "The accuracy [...] of the library functions in [...] is implementation-defined.", so it does not guarantee you any precision of `pow`. While it most likely is not `99.9`, it might be something like `99.99999999999999`. – Michael Karcher Jul 27 '15 at 20:27
1

Also, chapter 6.3.1.4 ("Conversions: Real floating and integer") says in paragraph 1: "When a finite value of real floating type is converted to an integer type except _Bool", the fractional part is discarded (i.e. the value is truncated to zero)". – Michael Karcher Jul 27 '15 at 20:33
@ Michael Karcher Went through the reference. Learnt something new. Thanks! – Gaurav Jain Jul 28 '15 at 11:23

Shreevardhan · Answer 2 · 2015-07-18T10:30:27.103

1

You may not need pow here. This works as expected and is faster too.

#include <iostream>
typedef unsigned long long ull;
using namespace std;

ull count(ull n) {
    ull i = 0;
    for (; n; ++i) n /= 10;
    return i;
}

int main() {
    ull n;
    cin >> n;
    ull digits = count(n);
    ull ans = digits * (n + 1);
    for (ull i = 0, j = 1; i < digits; ++i, j *= 10)
        ans -= j;
    cout << ans;
    return 0;
}

All testcases passed on codeforces.com

edited Jul 18 '15 at 10:30

answered Jul 18 '15 at 10:01

Shreevardhan

12,233
3
36
50

If I cast it to long it outputs 5888898 whereas the correct answer is 5888896 and I achieved it by making my own pow function. BTW thanks. :) – Gaurav Jain Jul 18 '15 at 10:04
@Sreevardhan Maybe its coz I compiled it on codeblocks. But again I tried to get it accepted on codeforces and again(after the edit you suggested) it didn't pass the pretests. – Gaurav Jain Jul 18 '15 at 10:12
@GauravJain Updated. Thanks – Shreevardhan Jul 18 '15 at 10:43

score 0 · Answer 3 · answered Jul 26 '15 at 17:33

You just need to multiply pow(10,i-1) with 0.1. That will do the work you needed.

#include <iostream>
#include <cmath>
using namespace std;
int digit_calc(long long num);
long long digit_counter(long long num, int digit);
int main()
{
    long long num,digit,total;
    cin>>num;
    digit=digit_calc(num);
    total=digit_counter(num, digit);
    cout<<total<<endl;
    return 0;
}
int digit_calc(long long num){
    int digit=0;
    while(num){
        digit++;
        num=num/10;
    }
    return digit;
}
long long digit_counter(long long num, int digit){
    long long sup,net,total=0;
    while(num){
        sup=0.1*(pow(10,digit)-1);
        net=num-sup;
        total=total+(net*digit);
        num=sup;
        digit--;
    }
    return total;
}

It passed all test cases on codeforce.

Unexpected output of c++ program

3 Answers3