fix comparisons between Float64 and Int64

[JeffBezanson]

We currently promote to Float64, which gives the wrong answer in cases like these:

julia> float64(2^60) == (2^60+1)
true

julia> float64(2^60) < (2^60+1)
false

[StefanKarpinski]

Actually, I forgot that I hadn't actually fixed isequal yet. Currently it uses the hack of comparing hashes. This is wrong. Need to just fix == and then get rid of the hash comparison. The solution is that for floats that are smaller than typemax(Int64) we convert the float to integer and then compare rather than converting both to floats. For floats that are too big to be stored as integers, we can just return false immediately.

[JeffBezanson]

I worked on this a bit and prototyped by writing C functions.

For equality, I believe it works just to cast both ways:

int eq_f64_i64(double f, int64_t i)
{
    return (f == (double)i) && ((int64_t)f == i);
}

If f is out of int range, the first one will fail. If it's in range but you have a non-integer, the second one will fail. The corner case is when f==2^63 and i==typemax(Int64). Then the first check actually passes, but I think we can rely on (int64_t)f giving 0 or typemin(Int64), thereby failing.

This is what I have for less than:

int lt_f64_i64(double f, int64_t i)
{
    if (i <= DBL_MAXINT && i >= -DBL_MAXINT)
        return (f < (double)i);
    return (f <= (double)S64_MIN) || (f < (double)S64_MAX && (int64_t)f < i);
}

int lt_i64_f64(int64_t i, double f)
{
    if (i <= DBL_MAXINT && i >= -DBL_MAXINT)
        return ((double)i < f);
    return (f >= (double)S64_MAX) || (f > (double)S64_MIN && i < (int64_t)f);
}

The operators are carefully picked to take the float representations of the extreme int values into account.
If we have this as an intrinsic, the code generator can reduce this to just the first case when we have a small integer literal.

[StefanKarpinski]

These look good. We should also add unit tests for the corner cases.

[JeffBezanson]

For completeness, here are the ones for uint64:

int lt_f64_u64(double f, uint64_t i)
{
    if (i <= (uint64_t)DBL_MAXINT)
        return (f < (double)i);
    // NOTE: (double)U64_MAX is greater than U64_MAX.
    return (f < 0) || (f < (double)U64_MAX && (uint64_t)f < i);
}

int lt_u64_f64(uint64_t i, double f)
{
    if (i <= (uint64_t)DBL_MAXINT)
        return ((double)i < f);
    return (f >= (double)U64_MAX) || (f >= 0 && i < (uint64_t)f);
}

[StefanKarpinski]

Don't we also need eq_f64_u64, which I presume can be written in C as this:

int eq_f64_u64(double f, uint64_t i)
{
    return (f == (double)i) && ((uint64_t)f == i);
}

[StefanKarpinski]

I was going to say that we didn't need these anymore since we seem to have decided to implement isequal that differentiated types, but I guess we still need it for ==, etc.

[JeffBezanson]

Yes.

[StefanKarpinski]

Ok, I'm working on implementing these intrinsics right now.

[StefanKarpinski]

Doesn't this work:

lt_f64_i64(x::Float64, y::Int64) = int64(x) < y || x < float64(y)

?

[JeffBezanson]

Very close, but it gets this case wrong:

julia> int64(2.0^63) < typemax(Int64)
true

[StefanKarpinski]

Seems right to me:

julia> int64(2.0^63)
-9223372036854775808

[JeffBezanson]

huh?

[StefanKarpinski]

That's how we convert 2.0^63 to an Int64. As far as I can tell, it's the conversion that's problematic, not the comparison. Unless I'm missing something here.

[JeffBezanson]

2^63 is not representable as an Int64.

[StefanKarpinski]

Your example above was int64(2.0^63) < typemax(Int64). Did you mistype? What are we talking about here? I know that 2^63 is one too large to be represented as an Int64. So as far as I can tell your example this one is not actually relevant. Arguably we should convert 2.0^63 to an Int64 differently, but that's a different issue.

[StefanKarpinski]

So that counter-example, as far as I can tell is bogus. However, the comparison NaN < 0 is a real problem. As far as I can tell, all NaNs get converted to typemin(Int64), however, which I think means that defining things in terms of >= may actually work.

[JeffBezanson]

I was just substituting values into your lt_f64_i64 function:

lt_f64_i64(x::Float64, y::Int64) = int64(x) < y || x < float64(y)

let x = 2.0^63
let y = typemax(Int64)

so the function would attempt

int64(2.0^63) < typemax(Int64) || 2.0^63 < float64(typemax(Int64))

and the first part is true, so it returns true, but x is not less than y.

[StefanKarpinski]

But not for Uint64:

julia> uint64(NaN)
9223372036854775808

That's really an awful number for NaN to convert to. It's literally right in the middle of the range of valid Uint64 values.

[StefanKarpinski]

Ok, now I see what you're saying. Guess I need to figure out how to emit a conditional in LLVM's C++ API.

[JeffBezanson]

In Stefan's commit 61fe3b9.

[StefanKarpinski]

Can we close this now? I think it's all fixed, no? I should probably write some more tests, however.