Yes, a double has 53 (effective) bits of precision, which is a range of 2^53 = just under 1e16. But your code requires 1e18 (1e12 / 1e-6) (this is a quick and dirty way to look at it).
Basically the problem is that at the high end of that range, the distance between consecutive doubles is larger than 1e-6, so your condition won't be satisfied unless l == r (and if you coded binary search in the usual way, that probably can't happen). Extended precision (long double) usually has at least a 64-bit mantissa (depends on your compiler though, e.g. MSVC++'s long double is the same as double last I checked) which will probably work in this case. Alternatively, reduce your required tolerance (the problem does state that a *relative* difference of 10^-6 is acceptable -- or you can use the fact that the answer is always half an integer to set a tolerance of 0.5). On May 21, 1:01 pm, bychance <[email protected]> wrote: > I uses these code to do binary search: > > l=0; > r=1e12; > while(fabs(l-r)>1e-6) > { > //some code > > } > > but it stucked with large data in my local PC. > I also doesn't work in Code Jam Africa and Arabia 2011 Online > Competition Problem C Radio Receiver. > > I saw the code from the first place of today's match. > He uses this line of code instead: > > REP(i,100){ > > means iterates for 100 times. > 1e15/2^100<1e-6, so it fit the precious. > > I'm wondering that is it caused by the precious of float number > operations? -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
