How to determine if double would be precise enough?

general
,
1

I was trying to solve the problem FTRIP Field Trip. I came to the conclusion that I have to calculate some binomial coefficients C(n,k). But the ranges were high. At the worst case I have to calculate C(1000,500). This obviously will not fit 64 bit int. I could use doubles, but even that will not be precise enough ( or so I thought ). I tried thinking of other solutions that didn’t involve binomial coefficient, but didn’t find any. If only I could calculate C(n,k) with enough precision then problem would be solved.

Then I went to the editorial to see how they handled the situation. They used double. Now I am confused. How will I determine if the double would be precise enough to get me AC? Is it because this problem has special judge that using double leads to AC?

1 Like
2

double range is upto 10^307 and C(1000,500) is around 10^299

For calculating C(1000,500)-1000 choose 500 - Wolfram|Alpha

For c++ ranges refer-http://www.cplusplus.com/doc/tutorial/variables/

Also note in double there is huge precision loss due to limited number of bits.

1 Like
3

I would suggest you to read What Every Computer Scientist Should Know About Floating-Point Arithmetic

1 Like
4

That’s one big article! I read it a bit and discovered few new things, such as why 0/0 gives RE but 0/0.0 gives NAN. Thanks.