Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Comparisons of 0 with 0 rely on integer overflow #148

Closed
thoni56 opened this issue Oct 15, 2017 · 5 comments · Fixed by #151
Closed

Comparisons of 0 with 0 rely on integer overflow #148

thoni56 opened this issue Oct 15, 2017 · 5 comments · Fixed by #151
Labels

Comments

@thoni56
Copy link
Contributor

thoni56 commented Oct 15, 2017

Issue 3 in #135 reported by @KabooHahahein:

First of all, we should not be passing an invalid domain (0) to log10()
Second of all, we should not be casting –Inf to integer then do a subtraction on it. This will cause an overflow.

@thoni56 thoni56 added the bug label Oct 15, 2017
@thoni56 thoni56 changed the title Comparisons of 0 with 0 rely on a integer overflow Comparisons of 0 with 0 rely on integer overflow Oct 15, 2017
@thoni56
Copy link
Contributor Author

thoni56 commented Oct 28, 2017

Some help here, please @KabooHahahein and @d-meiser.

Currently we have the "offending" line

static double accuracy(int figures, double largest) {
    return pow(10, 1 + (int)log10(fabs(largest)) - figures);
}

As largest approaches zero, log10(fabs(largest)) approaches infinity. So what should actually accuracy() return for largest=0? Or shouldn't accuracy() be part of the equation at all if largest is zero, or even near zero?

Do we have an example that exposes this problem in terms of usage? (I understand the "theoretical" problem of overflow here.)

@d-meiser
Copy link
Contributor

@thoni56 thanks for looking into this and the analysis. I'll have to have a look at the code to see how accuracy is used and to understand how it should behave when largest gets small.

@d-meiser
Copy link
Contributor

@thoni56 Here's what I've found so far. The fundamental problem is that we are always doing a relative comparison of the numbers being checked for equality (and similarly in the other constraints). This breaks down for small numbers for fundamental reasons, see e.g. the section "Infernal zero" in https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

The solution is to augment the relative comparison with an absolute comparison. Something like this:

bool equal(float a, float b, int significant_figures, float max_diff)
{
        if (fabs(a - b) < max_diff) return true;
        return max(a, b) - min(a, b) < accuracy(significant_figures, max(fabs(a), fabs(b)));
}

I've added our global significant_figures to the function signature to make explicit what information we need inside this function. When comparing two numbers that are close to zero, the if statement returns true and we never need to evaluate the problematic accuracy.

The problem is that we now need an additional piece of information: max_diff. Unfortunately there is no good generic choice for max_diff. Only the client code knows what "small" means. I think the best we can do is to make a default choice (FLT_EPSILON perhaps) and then provide a function to let the user adjust this number. This would be a backwards compatible change.

If you are OK with this idea I'll go ahead and put together a patch. I'll double check with the boost unit_test framework and gtest to see if this is reasonable. And I'll check what defaults they use for max_diff.

@thoni56
Copy link
Contributor Author

thoni56 commented Oct 30, 2017

Thanks, @d-meiser, sounds like a very good plan!

I've just pushed a branch, double_comparison_corrections, that I had with tests in double_tests.c that exposes the double-issues reported by @KabooHahahein #146 (closed), #147, this (for which there is no test), and #149.

@d-meiser
Copy link
Contributor

Great, thanks. I'll pull that branch with the additional tests.

thoni56 added a commit that referenced this issue Nov 3, 2017
Double comparison corrections which fixes #148 and fixes #149.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants