Блог пользователя ivplay

The ceil trap (Beginners Only Topics)
Автор ivplay, история, 10 лет назад, По-английски
  • 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.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Ya, good reminder... :)

    → Ответить
  • »
    »
    10 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится -8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +15 Проголосовать: не нравится

    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.

    → Ответить