Optimal code binary case

Question

I am trying to get this output from my code:

but what i get is

This is my code so far:

void optimal(int arrsize) {
  int j;
  int code = 0;
  cout << '0' << endl;
  for (int i = 1; i < arrsize; i++) {
    j = i;
    while (j > 0) {
      code += pow(10, j);
      j--;
    }
    cout << code << endl;
    code = 0;
  }
}

No problem dude, just try next time to present a more readable question :) — nbro, Jan 01 '15 at 23:11

score 4 · Accepted Answer · answered Jan 01 '15 at 23:16

4

Your code is wasting resources through very expensive pow() call. You could achieve same results in optimal way with:

void optimal(int arrsize)
{
    cout<<'0'<<endl;
    for (int i = 1; i < arrsize ; i++)
    {
        for (int j = 1; j < i ; j++)
        {
            cout<<'1';
        }
        cout<<'0'<<endl;
    }
}

answered Jan 01 '15 at 23:16

Predrag Manojlovic

379
5
16

1

you are very right also we can move the first line( cout<<'0'< – Ahmed EL Said Jan 01 '15 at 23:18
Of course. This is just to demonstrate idea and can be modified to suit your needs. Also, it works with very big arrsize. – Predrag Manojlovic Jan 01 '15 at 23:19
But any exact reasons why the algorithm in the question fails?? Despite both inputs in the `pow` function being integers?? – user007 Jan 01 '15 at 23:19
As said by other person here, pow() takes double as input type so we get rounding error and at some point overflow. – Predrag Manojlovic Jan 01 '15 at 23:21
yea.. but in the code in the question, it fails for `i=2`, 10^2 is 100.00000 (some more decimals maybe) But I dont get it how can it get rounded off to 99 (which then later sums uptp 109) – user007 Jan 01 '15 at 23:24
1

Implementation of pow() is not made in a way you expect it to be. As it doesn't work as 10^2 literally. In attempt to explain I'll try to make it simple: it is interpolating to resulting value. Technique is not quite trivial to explain. – Predrag Manojlovic Jan 01 '15 at 23:28
1

@user007: It adds up to 99.999999999999 which is then rounded down. The round-to-nearest solution `int(pow(10,j)+0.5)` works by rounding 100.499999999 down to 100, as you probably expected. – MSalters Jan 02 '15 at 01:31

Jarod42 · Answer 2 · 2015-01-01T23:13:02.703

2

pow is a function for floating point, and you have then rounding error...

you may rewrite your function to something like:

void optimal(int arrsize)
{
    cout << '0' <<endl;
    int code = 0;
    for (int i = 0; i < arrsize ; i++)
    {
        ++code;
        code *= 10;
        cout<< code << endl;
    }
}

live example

edited Jan 01 '15 at 23:13

answered Jan 01 '15 at 23:06

Jarod42

203,559
14
181
302

so what function should i use – Ahmed EL Said Jan 01 '15 at 23:11
@AhmedELSaid: you may create your own function, or change your algorithm. – Jarod42 Jan 01 '15 at 23:14
@AhmedELSaid Do you have a complete random number after `pow(11)`? – nbro Jan 01 '15 at 23:19
2

You will have overflow once result is bigger than `2147483647` (when `int` has 32bit). – Jarod42 Jan 01 '15 at 23:19
1

@AhmedELSaid If you to go further, you should use the @Predrag's solution. Another thing, don't use `endl` but just `'\n'`: http://stackoverflow.com/questions/213907/c-stdendl-vs-n – nbro Jan 01 '15 at 23:21
@Rinzler yes the number may reach pow(512222) thanx for the advice – Ahmed EL Said Jan 01 '15 at 23:25
Any more info about the round off error with the floats?? Still cant understand how can 10.000, 2.000 can round off to 99 (later sums to 109, for i=2) – user007 Jan 01 '15 at 23:30
1

@user007: You may read [differences-in-rounded-result-when-calling-pow](http://stackoverflow.com/questions/17063102/differences-in-rounded-result-when-calling-pow) – Jarod42 Jan 01 '15 at 23:40
If you want to be funny, using `std::oct` (octal) overflows one digit later :) – MSalters Jan 02 '15 at 01:35

Optimal code binary case

2 Answers2