Arithmetic functions rational/1 and rationalize/1

General
23

IMHO the Common Lisp (incongruent) coercion for non comparison arithmetical binary operator is a design mistake and should not followed (also their rationale for this choice seems incorrect as accuracy is clearly preserved with arbitrary precision rationals): to use a type that is a superset of operand types is clearly the best option.

24

Don’t think I have much more to say on this subject so I’m going to generate a couple of PR’s before moving on.

The first PR fixes a couple of bugs in libbf/bf_gmp.*, improves compatibility with GMP, and adds a few additional functions from GMP that are required to implement mathematically correct comparisons. I don’t think there’s anything controversial in this PR.

The second PR replaces the current version of cmpNumbers in pl-gmp.c with a mathematically correct version. It can be accepted, rejected, or used to build a fork for additional testing. The new version has been restructured into a 4x4 switch statement whose cases call one of ten simple compare functions based on argument type. (I think @jan suggested a similar structure for untangling ar_pow in an earlier thread.) This should make it simple to modify individual cases whenever a final decision is made, assuming a change in the status quo is desirable.

25

Merged the fixes and additions to bf_gmp.[ch]. As for the rest, converting floats to rationals may be mathematically the right thing to do, but I’m not at all convinced it is a good idea. It is solely based on the mathematical properties of floats, disregarding the conceptual role they play in computation.

I’m curious as to whether there are practical use cases for using rational/1. I could find one for rationalize/1: convert monetary amounts to rationals before performing lossless computation on them. I think that for any monetary amount you can write down as a float without loosing precision because the float is too large (i.e., those floats for which write(F) reproduces the input), rationalize/1 produces a rational number that is equal to the “intended” amount. So, rationalize(0.10) is 1r10, which is what you want, while rational(0.1) is 3602879701896397r36028797018963968 which is clearly not what you want (in this domain). Of course, we should support decimal floats to deal with this. FYI, dealing with monetary computations is what brought rationals to SWI-Prolog.

26

IMHO the problem is due to the fact that we are aggregating rationals and integers in the same class:

Although we have

?- 1.0 = 1.
false.

we have e.g.

?- 1 = 2r2.
true.

This shows that three different kinds of number (machine integers, arbitrary precision integers and rationals) are considered as belonging to the same class and can silently change their internal nature so leading to unexpected results and/or slow down.

Consider as an example 0.1 + 1: if we consider the 1 as belonging to the class above then we should do the math in the supertype of both (i.e. rational) and then we should get 39631676720860365r36028797018963968.

If instead we separate integer and rational in two distinct classes (so that 1 = 2r2 is false) we can have a more “natural” supertype similar to other languages without unexpected results and slow down.

integer + float → float (loss some)
integer + rational → rational (loss less)
float + rational → rational (loss less)

27

SWI-Prolog has only two numeric types: rationals and floats. And, indeed, rationals come at various internal representations, mostly to make the most common ones small and fast: small integers.

So, we get A is 1 + 0.1 + 1r1 and the result is some weird rational. SWI-Prolog’s thinking is “if you got a float, you lost something”. That is almost always true as floats typically result from measurements on continuous scales or the involvement of functions over reals. The few precise floats are normally decimal types that cannot be represented properly using binary floats and thus you also lost something. The reverse is also true: “if you have a rational the result is exact”. That is quite useful in logic programming because identity is key in logic. Identity holds for rationals, but not for floats as the result of many computations that are supposed to have the same value do not result in the same float. SWI-Prolog’s arithmetic ensures these relations.

Now there are two escapes. One is if you prefer performance over exactness you can cast one of the operands to float. All subsequent computation happens in floats and at the end you know the result is an approximation.

On the other hand you can cast a float to a rational and preserve preciseness. Only, except for rationalize/1 on monetary amounts, I never came across any use case where this made sense.

2 Likes
28

Please can we stick to comparison. I have never suggested converting a float to a rational for use in evaluating arithmetic expressions; only for the purpose of comparing numeric values. Comparisons are just tests; per se they don’t change the value of anything. There may be a second order effect, e.g., in sorting, but I struggle to find an example where this matters as long as it’s repeatable. I also don’t relate to “disregarding the conceptual role they play in computation.” In what “conceptual role” would it be acceptable/useful that 2^1024 =:= inf is true and 10^16-1 < 1e16 is false?

I’m curious as to whether there are practical use cases for using rational/1.

I’m not sure I can come up with a practical use case for either of the functions rational or rationalize, and I’m not suggesting anything be changed in mixed mode arithmetic. All I want to do is compare numbers of any type in a mathematically correct and consistent way. (See examples above.) Coming up with a mathematically correct arithmetic system based on just rationals, while conceivable, is opening up a “can of worms” (IMO).

And I have no issue with any of this. I really think this is what most users would expect (if they thought about it). But I don’t think this conflicts with the goal of mathematically correct comparison of floats and rationals.

29

So does CommonLisp, but @abramobagnara claims this should be considered a design flaw. Having different promotion rules for comparison and other arithmetic functions indeed appears dubious to me.

It makes a claim that IMO cannot be justified. It would also lead to

?- I is 10^16, F is 1e16, I1 is I-1, F1 is F-1, I1 < F1.
true.

So, comparing 10^16-1 and 1e16 is “too close to call”. At least, that is one view and I think a view that is more consistent with how the rest of the system distinguished between floats and rationals.

If you want to compare as rationals, why not simply write

?- rational(Expr1) op rational(Expr2).

Using optimized arithmetic the difference shouldn’t be impressive.

30

I don’t think he ever claimed that comparing a float and rational as rationals in CommonLisp was a design flaw, but I could be wrong.

But not to me, because comparison is just a test that theoretically doesn’t require promotion (and possible error).

Not so (whatever “too close to call” means); only that F1 is F-1 is imprecise due to floating point roundoff error. The meaning of 10^16-1 < 1e16 is pretty clear to me, and it’s false.

Because I would expect Expr1 op Expr2 to come up with the correct answer independent of the type of numbers Expr1 and Expr2 are. Same as if I was comparing floats and integers; why would you expect users to write explicit type conversions in that case (float(Expr1) op float(Expr2))?

Anyway, we can agree to disagree. If the PR is rejected, I’ll just continue to workaround this “bug” but I wouldn’t be surprised if someone else trips over it at some point.

31

Just to clarify, although I’m definitely against to have different promotion rule depending on operators, I am definitely not against to mimic other languages that don’t want to mess with dangerous conversion, just like other languages. e.g. in Javascript:

$ node
Welcome to Node.js v16.18.1.
Type ".help" for more information.
> 10000000000000000n == 1e16
true
> 10000000000000000n + 1n == 1e16 + 1
false
> 10000000000000000n - 1e16
Uncaught TypeError: Cannot mix BigInt and other types, use explicit conversions

A possibility in this direction is prohibiting in SWI-Prolog to have mixed arithmetic involving floating types (leaving comparison always possible, of course) and for all the rest to promote to common supertype.

If really we want to please everyone (that is said to be recipe for nothing good, but who knows :slight_smile: ) we might have a settings for mixed precision arithmetic operators involving float, with three states:

  • raise an exception
  • promote to float
  • promote to rational
32

Another reason I currently can’t use this is because inf as a floating point value doesn’t convert to a rational (generates an error). But I can’t think of any reason why I shouldn’t be able to compare a rational to inf - the result should always be <.

Perhaps a useful discussion, but one which I would like to keep separate from comparison semantics.

33

I can. Float Inf merely means “cannot represent such a large value”, which means it can be anything between 1^1024 and mathematical infinity. Comparing that to a rational > 1^1024 can IMO only say “I don’t know”. Float comparison gets the closest float representation and decides floats are equal if these representations are the same. Considered this way, two floats comparing equal merely states that the values are the same given the limitations of floats and thus we cannot conclude one is larger than the other.

I fear we will not agree on this. If there will ever be consensus in the Prolog community I’ll reconsider. So far, these ideas violate with the ISO standard (granted, because SWI-Prolog doesn’t do integers any longer) as well as with my ideas to keep floats and rationals separated.

Having a flag to decide is an option. I don’t like flags and I doubt it is worth the trouble. If the implications are small enough I might accept this way out.

35

Apparently this intuition doesn’t hold :frowning: We get

?- A is rational(0.000000000000000001).
A = 1298074214633707r1298074214633706907132624082305024.
?- A is rationalize(0.000000000000000001).
A = 1/999999999999999872.
?- 1 / 1000000000000000000 =:= 0.000000000000000001.
true.

So, rationalize keeps its promise to produce the smallest possible denominator. Apparently that is not always enough to get human “pretty” denominator.

36

Hard to find agreement when a basic issue is the meaning of infinity. Needless to say I disagree with this definition. The value infinity means infinity and there are an infinite number of real values between the largest finite float and infinity; the value inf is not that set.

I would claim that all the numeric values we’ve been talking about are subsets of extended reals (includes the values ±infinity). The set of extended reals is strictly ordered and compare is defined in terms of that order. If your set of representable numeric values is not strictly ordered, it should be well documented somewhere that that’s the case.

But ISO only defines a small subset of numeric values under consideration, which I don’t think is contentious(?). At this point I don’t see any “consensus in the Prolog community”, or even a process, so where is the violation?

I also don’t see how you can enforce keeping floats and rationals separate without introducing significant incompatibility issues. And why would you want to keep them separate? A specific example: the clpBNR interval arithmetic system represents a real with the tuple (L,H) where the bounds L and H can be any numeric value, so mixed mode arithmetic is a basic requirement. It’s really not about the separate worlds of precise vs. imprecise computation. In any case that should be a user decision (mechanisms vs.policy).

I don’t know about other Prolog systems, but if you want an example of mixed type arithmetic, again see GMP, specifically mpz_cmp_d and mpq_cmp_d. JavaScript and CommonLisp are two other supporting examples from this thread and I suspect more could be found. I would suggest that SWIP is the outlier in this regard, but if other similar examples could be found, I would be more sympathetic to your point of view.

No flags please; optionally wrong is still wrong IMO. Better to consistently deal with the devil you know.

39

Talking floats, yes. We have the highest representable float and Inf, which represents anything higher. If we introduce unbounded integers (or rationals) into the picture things get different. In your view we can do

?- A is 2.0^2000,
   B is 2^3000,
   B < A,
A is 1.0Inf
B = 2460463844322...

That may under some interpretation of arithmetic be correct. I still claim that whatever real world problem this is modeling, the above result is considered wrong. Ok, equal is also wrong. I think less so though. Floats are involved and identity under floats means that the two expressions, each round to the same nearest float. Float identity thus merely means “to close to call”.

SWI-Prolog has no integers (as a type) so Rat op rational(Float) also holds for integers where ISO is explicit that the comparison is float(Int) op Float. So this is a violation. @abramobagnara offered having 2r1 next to 2. That would solve that problem. It also comes with its disadvantages so it is not an easy decisions to make.

Not in your view. I won’t repeat myself

And it also provides mpf_cmp_z. The docs are not explicit what this means. Anyway, GMP is a set of building blocks against typed numbers where you specifically have to decide what to do when rather than let the system decide how to deal with mixed types.

JavaScript has no rationals as base type. CommonLisp handles comparison and arithmetic different. ECLiPSe Prolog does as SWI. Possibly because they didn’t consider it carefully, but the system is fairly advanced when it comes to handling numeric data and I think it is not unlikely they did think about it. Is Joachim listening? All Prolog systems I tried with unbounded integers follow the ISO rule here.

As the notion of identity is prevalent in logic programming and rationals can express this accurately while floats can not, silent translation of floats to rationals is IMO a bad move. The fact that nobody came up with a use case why one ever would like to do the explicit conversion in an application strengthens this idea. You probably disagree that identity doesn’t work with floats. It depends on your viewpoint. I consider this violated by

 ?- 1 =:= 1 + 0.1 + 0.1 - 0.2.
 false.

You can of course claim that 0.1 and 0.2 stand for precise rationals with a slightly different value that what is written down and thus the result is indeed false.

What I mean by identity is possibly best illustrated by the fragment below. In the ideal world this should work for Angle = pi/2.

    ...
    Cos is cos(Angle),
    on_con(Cos).

on_cos(0.0) :- ...

A flag is as far as it can get 
 That float should probably affect the generic “promote to same type” function.

41

If all you have is 64 bit integers (ISO?), then you really have no choice but float(Int) cmp_op Float (although even that isn’t correct over the whole integer/rational range since a double mantissa is only 53 bits). And as soon as you replace ISO integers with rationals you’ve “violated ISO”; haven’t you?

And so you’ve chosen different semantics than that chosen by the GMP community. That’s fair enough, but hardly a compelling argument. I’m also not sure where mpf_cmp_z fits in because multi-precision floats aren’t at issue here. But I’d be willing to bet it produces mathematically correct results, as do all the other compare functions.

Perhaps, but that just makes the float(Int) cmp_op Float less compelling since almost all unbounded integers as well as well as a subset of 64 bit integers do not map precisely to floats for comparison purposes.

And all the other languages cited so far with unbounded integers (applies to all of the simple examples so far) do not follow the ISO rule. Here’s another: Python, (from: 6. Expressions — Python 3.12.0 documentation)

  • Numbers of built-in numeric types (Numeric Types — int, float, complex) and of the standard library types fractions.Fraction and decimal.Decimal can be compared within and across their types, with the restriction that complex numbers do not support order comparison. Within the limits of the types involved, they compare mathematically (algorithmically) correct without loss of precision.

(Emphasis is mine.) Note that Python int’s are unbounded and there are no built-in rationals, but "Fraction"s and "decimal"s are part of the standard library subject to this definition. Using https://www.online-python.com/

# Online Python - IDE, Editor, Compiler, Interpreter

print(2**1024 < float('inf'))
print(10**16-1 < 1e16)
print(10**16 == 1e16)
print(10**16+1 > 1e16)

produces:

True
True
True
True


** Process exited - Return Code: 0 **
Press Enter to exit terminal

So a lot to unpack here. Nowhere have I argued for silent translation of floats to rationals. I’ve only argued for mathematically correct comparison between a float value and a value of a different numerical type. The only visible result is true (succeed) and false (fail). It’s pretty well known that floating point arithmetic is mathematically incorrect in general, so if by “identity” you mean numerical equivalence after evaluating floating point expressions, then I totally agree identity doesn’t (in general) work with floats.

And due to this “bug” I do have a use case for explicit conversion. A “real” value domain can represented by an interval with an lower bound L and an upper bound H. Whne a domain narrows three cases have to addressed based on mathematically correct comparison:

  • L > H - empty domain, fail.
  • L =:= H - point value, unify with “real” variable
  • L < H - new domain bounds, update domain

Resolution of these cases is performance sensitive since it’s potentially done several times within a interval arithmetic primitive within a fixed point iteration. But I really wanted to drive this discussion based on general merit rather than my specific use case.

But isn’t it clear that:

?- X is 1 + 0.1 + 0.1 - 0.2, X =\= 1.
X = 1.0000000000000002.

Are you really trying to hide the fact that floating point conversions and calculations are imprecise by adapting a fuzzy definition of identity?

One can debate the merits of turfing floating point in favour of rational arithmetic, but that’s specifically not my argument. Numeric value promotion isn’t necessary for mixed type comparison, although it’s often easier to explain it in those terms. (I really think the standard writers did a disservice by specifying an implementation detail rather than just semantics.)

Again this involves floating point evaluation so it’s unsound and I don’t expect mathematical laws and axioms to apply. FWIW, in clpBNR (which strives for mathematical correctness over extended reals):

?- {Cos is cos(pi/2)}, Cos = 0.0.
Cos = 0.0.

?- {0.0 =:= cos(pi/2)}.
true.

?- {1 =:= 1 + 0.1 + 0.1 - 0.2}.
true.

This behaviour results from floats truly being intervals. In the “world of curly brackets arithmetic” identity, as well as other mathematical properties (associativity, distributivity) apply.

I think this disagreement has little hope of resolution; nobody is really fond of flags. And since comparison keeps getting conflated with evaluation (wrongly IMO), let me propose the following alternatives:

  1. Add compare(E1,E2) arithmetic function which does mathematically correct comparison and evalutes to -1 (E1 < E2), 0 (E1 =:= E2), or 1 (E1 > E2). Expression evaluation is unchanged from current semantics so if you use floats, it is what it is. (A variation is to add mathematically correct compare operators but that seems less “user friendly”.)

  2. Add a predicate arith_compare(Op,N1,N2) analagous to term compare (compare/3). Op is one of <, =:=, or ‘>’.

  3. Change the existing compare/3 predicate to compare numbers “correctly”. This might be the least obtrusive unless someone is actually depending on ordering based on mathematically incorrect compare.

I think I prefer 1. particularly as it is subject to arithmetic optimization (?).

43

ISO doesn’t say anything about the integer range except that it is described by the Prolog flags min/max_integer or the Prolog flag bounded being false, i.e. the ISO does consider unbounded integers. AFAIK there is no notion of rational numbers (I know they have been discussed, but never made it to the standard).

That is an interesting proposal. Thanks. I can live with (1) or (2). Possibly there are better names. Changing compare/3 is not an option as SWI-Prolog’s standard order is indirectly connected to <, < and =:=. A possible other name is rcompare, analogous to rdiv?

44

As I see it, the problem with unbounded integers is that converting them to floats for comparison is even less valid given the size of the float mantissa (53 for doubles)., e.g., for 32 bit integers, a double is adequate. That’s why I have an issue with defining an implementation which depends on an unspecified bit size, rather than the semantics of compare.

As I said, I prefer an arithemtic function (1), since it’s subject to optimization and it’s pretty simple to define a version of (2) using (1). Two followup issues:

  1. What to do with nan’s. I would suggest returning nan if the float_undefined flag 's value is nan and generating an error if it’s error.

  2. What comparison semantics do max and min use - if not mathematically correct, I think additional functions which are mathematically correct are warranted for consistency.

I’m open to alternative function names. I would interpret an “r” qualifer as real, rather than rational, and maybe using a suffix should be considered e.g., compare_r, max_r, min_r. If you prefer camel case compareR, etc.

45

For the record, from Common List Recipes, pp 101:

However, what if some arguments are rational and some are floating point? One could argue that rational numbers are (infinitely) more precise and should thus “win.” But this is not what happens. To make life easier for implementors, something like
(* 2 2d0)
will evaluate to 4.0D0 and not to 4 So, you should keep in mind that when you’re working with rationals because of their precision, one floating-point number will suffice to “taint” the result.

Funnily, the one exception to this rule are comparison functions, where in mixed situations the floats are first converted by means of RATIONAL (see above). This can lead to seemingly strange results, like
(< 6/7 (float 6/7))
being true in Lisps with IEEE floats (see Recipe 4-6).

1 Like