JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Representation of Integers and Reals Tutorial Green Zone/Red Zone
 Green Zone/Red Zone | Reply
 Re: Green Zone/Red Zone (response to post by Ryan) | Reply Ok, now before the next operation of rounding, lets talk a bit more about what the green zone, red zone theory means about the philosophy of using floating point numbers. Lets say do a calculation and mathematically the end result should be exactly 1. That's all fine and dandy, but in the real world we'll end up with a number with a green zone and a red zone. Lets assume that the green zone has 7 digits. So the question is, what actual value can the stored data have? Well, the answer to the question is easy, because we can just put the highest and lowest values for the red zone:`1.0000000999 to 0.9999999000`Namely, the stored number can never be more that 1e-7 away from the value of 1. In fact this value, 1e-7 is quite special. Special enough to give it a name, epsilon (the name comes from mathematicians practice of calling a small positive number by the same greek letter). Also note that the only thing special about the actual number "1e-7" is that in this case the green zone happens to be 7 digits, if your green zone has a different size, then your epsilon should too (TopCoder usually wants you to have an epsilon of 1e-9). Why is the epsilon important? Because we know from the green zone/red zone arguments the validity of this important fact:true value - epsilon < stored value < true value + epsilonThis is just a restatement of what the possible stored values are. But really if you think about it, that question isn't the one we usually want to ask. In fact we know the stored value; just check the contents of the variable you're using. The question is, what is the true value? If you fiddle around with the previous inequalities and try to solve them for the true value, then you'll end up with this similar fact:stored value value - epsilon < true value < stored value + epsilonNow there are two notable things about this equation. The first is that the true value is never epsilon away from the stored value. This should be obvious because the stored value should be less than a small amount away from the true value. But the second thing is more important. If we know the stored value then we know a range of values that the true value lies in. We don't know the true value exactly, but we have the set of possible values it could be. This is the whole reason for using epsilon in floating point comparisions, because if the ranges of two variables overlap, then the two values could be equal.Ok, now that that's through, back to the point of rounding. Let's say we want to round the variable x to the nearest integer less than or equal to x. For a simple first look, assume that x contains the exact value (before you realized that floating point computations were exact you assumed this exact same thing, so think of this as your code before learning the magic that is floating point). Well, you say, this is a simple task. This is just truncation, which is what casting to an integer does. (int) x is the desired value! Well, this is not quite so. Why? look above. If the true value of x is exactly 1 then x could be as low as 0.9999999000. When this number gets truncated it's going to go straight down to 0, be dead wrong, and get you that exact score in the SRM. The cure is plain and simple, just add epsilon to x before you do the cast. This way if x is anywhere near an actual integer(and so we must assume that the true value of x is that integer), then it will be gauranteed to get rounded to the right place. On the other hand if x is not close to any integer, then adding epsilon won't change the result.
 Re: Green Zone/Red Zone (response to post by Ryan) | Reply Thank you for the great explanation Ryan! So if you round down you should do something like (int)(x+1e-9). If you round up you do (int)(x-1e-9). Is this correct?How do you know what epsilon will be? Consider my previous example (see other post). In 3^35, how do you know that the answer will be off by 3?This made me think a bit more. So green zone means the digit is 100% correct, red means there is 50% its wrong. I guess yellow means that there is 25% its wrong. I wonder if there is a hardware architecture that lets you extract this information quickly? Ie. I want a function like accuracy(digit) that tells me what the % accuracy that digit has.
 Re: Green Zone/Red Zone (response to post by aussie) | Reply Yeah, you're right. I guess I should add 9:15 PM to the list of times when I shouldn't post. The correct form of the ceiling operation is:```(int)(x+1-epsilon) ```