For decimals, EQUAL? should be transitive.

Siskin-Bot commented 4 years ago

Submitted by: Ladislav

This may be a surprising finding for some people, but here are the arguments why non-transitive equal? leads to trouble:

lesser-or-equal? should be transitive for it to be a linear order on decimals. If it weren't transitive, sorting algorithms would not work correctly using it. (To see why nontransitivity is a problem, check #2251 and #2218.)
greater-or-equal? should be transitive for it to be a linear order on decimals. If it weren't transitive, existing sorting algorithms would not work correctly using it. (The same reason as above.)
equal? should be equivalent to the logical conjunction of lesser-or-equal? and greater-or-equal?. (See #2256), and, since both should be transitive, their conjuction should be transitive as well.

^{Imported from: https://github.com/rebol/rebol-issues/issues/2259}

Comments:

Ladislav added the Type.wish on Feb 8, 2016

Ladislav commented on Feb 11, 2016:

Rebol [
    File: %aeq.r
    Author: "Ladislav Mecir"
    Purpose: {
        Transitive approximate equality for decimals, prototype.
        Uses rounding to the nearest multiple of (tol + tol + 1)
        Units in the Last Place (ULP).
        TOL is the given tolerance in ULP.
    }
]

; rounding tolerance in ULP
; adjust to experiment
; tolerance 5 yields approximate equality
; that is at most as (but usually less) tolerant as the current EQUAL?
tol: 5

; corresponds to max decimal
max-ULP: to integer! #{7FEFFFFFFFFFFFFF}

max-rounded: max-ULP - (max-ULP // (tol + tol + 1))
round-boundary: max-rounded - tol

min-int: to integer! #{8000000000000000}

round-ulp: func [
    {Round to the nearest multiple of (tol + tol + 1) ULP}
    a [decimal!] {the decimal number to round}
    /local was-negative?
] [
    ; convert to ULP
    a: to integer! to binary! a

    ; transform negative values
    if was-negative?: negative? a [
        ; negate
        a: a xor min-int
    ]

    ; round, making sure to not get out of 64-bit IEEE 754 binary FP range
    a: either round-boundary <= a [
        max-rounded
    ] [
        a: a + tol
        a - (a // (tol + tol + 1))
    ]

    ; transform negative values
    if all [positive? a was-negative?] [
        ; negate
        a: a xor min-int
    ]

    a
]
ae?: func [
    {Are A and B approximately equal?}
    a [decimal!]
    b [decimal!]
] [
    ; this is integer comparison
    equal? round-ulp a round-ulp b
]

Hostilefork added the Ren.important on Jan 29, 2018

Oldes commented 2 years ago

@ladislav should this be implemented as natives? Or just make equal? working internally like the prototype?

Oldes commented 2 years ago

And isn't the current code good enough? https://github.com/Oldes/Rebol3/blob/22b8224e58b2c1ef4c7a2c878fc321772fd4c727/src/core/t-decimal.c#L95-L116

Oldes commented 2 years ago

I think that the sorting issue may be demonstrated on:

>> sort [1 9007199254740992 9007199254740993 9007199254740992.0 9007199254740993.0]
== [1 9007199254740992 9007199254740993 9.00719925474099e15 9.00719925474099e15]

>> sort reverse [1 9007199254740992 9007199254740993 9007199254740992.0 9007199254740993.0]
== [1 9.00719925474099e15 9.00719925474099e15 9007199254740992 9007199254740993]

Oldes commented 2 years ago

Useful reading on the topic: https://codewords.recurse.com/issues/one/when-is-equality-transitive-and-other-floating-point-curiosities

Oldes / Rebol-issues

For decimals, EQUAL? should be transitive. #2259

Comments: