ivplay's blog

The ceil trap (Beginners Only Topics)
By ivplay, history, 9 years ago, In English
  • I fell into a very interesting situation today , while solving CF — 599D.
  • say long long a = 1000000000000000363,b= 91
  • I wrote long long c = ceil(a*1.0/b) thinking (long * double) / double should be perfect double and ceil(double) — should work out.
  • I was expecting correct answer, c = 10989010989010993, but it produced c= 10989010989010994 , 1 more than the actual — result!!!! Damn to the precision issue.

  • Lesson :

    • Option 1 : Study lot lot and lot about your compiler and how it manages precision while both implicit and explicit cast.
    • Option 2 : Use your own ceil function like this
  • template inline T ceil(T numerator ,T denominator)
  • {
    • return (numerator+denominator-1)/denominator;
  • }

  • Moral : Avoid fraction as much as you can.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Yes, doing (num + den - 1) / den is what I always do. You only have to be careful with overflow if working with very big numbers, in which case you should do return num%den == 0 ? num/den : num/den + 1. The last option is more expensive because of the modulo operation, so I only use it in case of possible overflow.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya, good reminder... :)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not necessarily slower due to modulo. On x86 div instruction returns both quotient and reminder, so modulo operation comes for free as you need to do division anyway. GCC does this optimization. Only additional cost comes from the conditionally adding + 1. It can be compiled to something like this:

    (quot, rem) = DIV(num, den)
if (quot) rem++;
return rem;

    On other architectures reminder can be obtained by doing multiplication of division result. In either case it is not as expensive as doing completely unrelated modulo operation.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any specific problem where overflow occurs? People also suggest the same in binary search. If some problem related to that?

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

Doubt has been cleared.

I have edited this comment because some people find it inappropriate.

If you are still curious you can check the 1st version of this comment.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I assume you want somebody to give you a hack for problem A of the most recent educational round. I'm not sure about rules regarding collaboration for hacks but this seems very sketchy. In any case you can just wait until the round is over, and then view the hacks.

    Also, there's basically no point in hacking at this stage. The ceil hack tests will be added to system tests so any solution you'd be able to hack would just FST anyways.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Thanks buddy for replying. I searched over some more blogs and got the answer to my doubt. Also I know that hack tests are added in the final test set and me hacking every single solution involving ceil function make no sense. It was just for knowledge purpose. I really appreciate the fact that you respect codeforces' rules and so does I.

      I myself once encountered the same problem while using ceil function in some round (may be educational) and I could not find the exact reason at that time. That time I only understood that ceil function should be avoided.

      Just because of the last educational round I knew that some people are going to land on this blog :-) so I asked my doubt.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Yeah right. Always assume malicious intent.

      I landed here because my solution got hacked and not because I want to hack anybody.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        I realize that I did come off a bit rude in my original comment and I'm sorry about that.

        But my point about the ongoing hacking phase still stands.

        → Reply