Chef_Ka_Baap's blog

can this expression provide wrong output if it can how?
By Chef_Ka_Baap, history, 4 years ago, In English

ceil((double)x/n); x <= 10^12 and n <10^6; can anyone provide a test case or something I got hacked many times but was unable to find a mistake

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I can give you a reason why it can be wrong: because of how doubles are stored (IEEE 754), they might not be accurate, and that can lead to inaccurate result

if you want ceil, then use (x + n - 1) / n

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

    is there any test case to show this i am unable to find one

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

      it fails for bigger number like if you try to do 100000000000000001/100000000000000000 it will give you 1 directly but ceil of this should be 2

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

        but test case allow 10^12 for x and 10^6 for n

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

          You can try stress-testing. I believe ceil() will cause precision error by nature, regardless of the constraints.

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

    but if we give by this method ie (x+n-1)/n then wont it lead to overflows due to addition?

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

      yes

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

      I don't think any problem setter would be that evil.

      Also, if you are afraid of overflow, you can try x / n + (x % n != 0), although it requires more divisions, which is slower and uglier (but I guess it's easier to understand).

      And, __int128 is also an option as well, you can have a look at it.

      → Reply