Java Forum / General / August 2007
Discussion of why java.lang.Number does not implement Comparable
Sideswipe - 26 Jul 2007 22:37 GMT So, I have read the SDN entry of why Number does not implement Comparable http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4414323
And while I agree with their thinking I disagree with their approach.
Not all Numbers are 'Comparable' such as NaN (which is one of their motivational cases). However, when you look up the behavior of compareTo() in Float -- no such special condition exists for the case of NaN
While some numbers are not comparable, I argue that the numbers used in Java (with the exception of NaN) are comparable. So, Double d = 10.12 and Integer x = 11 ARE comparable. X is clearly larger.
For me, it seems that a better approach would be to have Number implement Comparable in the class signature but not actually DO the implementation. That way, in the event of NaN and such, implementing methods can simply throw exceptions (which seems far more appropriate than what Float.compareTo(Float.NaN) produces now -- which is
int result = new Float(10).compareTo(Float.NaN); System.out.println(result);
-1
Only special number cases are not comparable.
Thoughts, anyone? I fully realize I may bring out the worst in people with this question
Christian Bongiorno http://christian.bongiorno.org
Sideswipe - 27 Jul 2007 00:15 GMT I have a follow-up to my own question: Perhaps what is in order is to have an intermediary class like: "public class RealNumber extends Number implements Comparable" -- and in the event where the are non- definable comparisons, throw an exception. Then, you can have Imaginary Numbers and allow the rest of us to work with numbers as we naturally understand them.
Patricia Shanahan - 27 Jul 2007 05:19 GMT > I have a follow-up to my own question: Perhaps what is in order is to > have an intermediary class like: "public class RealNumber extends > Number implements Comparable" -- and in the event where the are non- > definable comparisons, throw an exception. Then, you can have > Imaginary Numbers and allow the rest of us to work with numbers as we > naturally understand them. I'm not sure it is that easy even for RealNumber classes. Suppose two classes X and Y each represent a subset of the real numbers. For example, X represents unresolved surds based on rationals exactly, so that 5+sqrt(2/3) would be a possible X value. Y represents some other subset of the real numbers, such as the trig functions of integer numbers of degrees, so that sine(30) is exactly representable as a Y.
There is a total order on (X union Y), because every element corresponds to some real number, and the real numbers have a total order.
However, determining the order between an X and a Y may not be trivial. If the X and Y have different values, calculating out the binary expansion of each until there is a difference will determine their order. However, that approach does not tell you how to detect exact equality between an X and a Y.
Patricia
Twisted - 27 Jul 2007 11:15 GMT > However, determining the order between an X and a Y may not be trivial. > If the X and Y have different values, calculating out the binary > expansion of each until there is a difference will determine their > order. However, that approach does not tell you how to detect exact > equality between an X and a Y. Seems you know a fair bit of higher maths from your recent posting history here!
I'd suggest the following:
* First, sorting a NaN in some arbitrary but consistent way, e.g. NaN < -inf < -10 < -1 < 0 < 1 < 10 < inf, allows well-defined behavior and makes collections of floats that may include NaNs safe to put into e.g. a TreeSet. So I'm not sure I disagree with Float's implementation of this behavior. * Second, Patricia's detecting-exact-equality issue with representations of irrational numbers:
- You can usually determine algebraically whether they are equal or not. For example nearly every sine is transcendental and the finite set of algebraic sines is well-known. Also e^x is transcendental for all rational x except 0, so far as I am aware, and ln x for rational x != 1 (these mirror one another); log(a) b with rational a and b when b is not a rational power of a (by definition!)... - Nonetheless you may not always be able to, and even when you are algebraically sure they're unequal it may be unobvious which is smaller without computing a ridiculously long initially-identical portion of their binary expansions. In these cases a consistent but arbitrary ordering is better than none. - Often you *will* be able to decide order algebraically, by taking an inverse func of both sides of an appropriately-contrived inequality with an undecided relational operator in the middle, whose correct value is easily decided from the result of this and which is either the same as or reversed from the correct inequality for the original numbers. This works for any monotonic func (e.g. exp, ln, any log, hyperbolic sine and inverse hyperbolic sine, square root and inverse hyperbolic cosine (pick one branch)) and other funcs have a symmetry that lets you convert to a smaller domain on which the funcs are monotonic (almost every trig function, quadratics, hyperbolic cosine)
Michael Jung - 28 Jul 2007 12:38 GMT > > However, determining the order between an X and a Y may not be trivial. > > If the X and Y have different values, calculating out the binary [quoted text clipped - 6 lines] > e.g. a TreeSet. So I'm not sure I disagree with Float's implementation > of this behavior. That wont really help, because you will lose certain features of comparing. Throwing an Arithmetic exception is probably better. Working with the two infinities in Java is already somewhat awkward.
> * Second, Patricia's detecting-exact-equality issue with > representations of irrational numbers: > > - You can usually determine algebraically whether they are equal or > not. No. Depending on what you do, solutions to these problems are unknown. Suppose I have numbers representing the first (smallest) real root of polynomials., i.e. N(a,b,c) represents the smallest real root of x^3 - ax^2 - bx - c. Now tell me how N(.1,-.2,1) compares to N(.2,.3,-2)? (While this problem may be solvable, you should get the picture.)
Michael
Twisted - 28 Jul 2007 16:02 GMT > > * First, sorting a NaN in some arbitrary but consistent way, e.g. NaN > > < -inf < -10 < -1 < 0 < 1 < 10 < inf, allows well-defined behavior and [quoted text clipped - 4 lines] > That wont really help, because you will lose certain features of > comparing. Explain please.
> > - You can usually determine algebraically whether they are equal or > > not. > > No. Do not bluntly contradict me in a public forum.
> Depending on what you do, solutions to these problems are unknown. There's an equation that can in principle be solved to see if they are equal. In practise it will be difficult with big enough (degree 5 or more) polynomials and various transcendental functions. In many cases, you know one is algebraic and the other transcendental and therefore they must be unequal.
Those known to be unequal can be expanded in binary until you know which is smaller, and you know it will take finite time. Those known to be equal can be treated as such. The remaining ones can be expanded in binary up to a point and in the majority of cases you'll quickly find one is less than the other. Only ones close enough together and difficult to tackle analytically remain. The policy with them might be to give them an arbitrary but deterministic ordering perhaps based on class and internal representation, or hashCode, or something.
Even ones known to be equal that are not equals() should be treated in that last way to fit the contract of Comparable...unless equals() should work "properly" across all Number subclasses.
It is admittedly a complex issue. Perhaps leaving it up to those mixing types to convert them manually and then compare them (e.g. an Integer and a Double by converting the Integer to another Double first) is best after all.
Patricia Shanahan - 28 Jul 2007 16:54 GMT >>> * First, sorting a NaN in some arbitrary but consistent way, e.g. NaN >>> < -inf < -10 < -1 < 0 < 1 < 10 < inf, allows well-defined behavior and [quoted text clipped - 11 lines] > > Do not bluntly contradict me in a public forum. Shrug. Different people have different preferences, so it is hard for writers to keep track. I'm here to learn, as well as to pass on any relevant insights I have, so if someone disagrees with me I *want* them to say so, simply and directly. I won't be offended as long as they explain their reasoning, so that I can either be convinced and learn, or be able to explain why I disagree with their reasoning.
>> Depending on what you do, solutions to these problems are unknown. > [quoted text clipped - 3 lines] > you know one is algebraic and the other transcendental and therefore > they must be unequal. I think you may be underestimating the difficulties of dealing with general real numbers. In many cases we can calculate the value to any required finite number of decimal, or binary, places. That is enough to give the order for two unequal values, but not enough to ever be able to declare equality.
Even if a class represents values of some transcendental function there can be some points at which the function has an algebraic solution. For example, consider the sines of angles that can be expressed as rational numbers of degrees. sin(30), sin(45), and sin(60) are exact solutions to quadratic equations.
One could write a comparator between sines and quadratic equation solutions by special casing angles that are exact multiples of three degrees, and then calculating the binary expansions of the other values until there is a difference.
However, to make Number implement Comparable we would need a general approach to comparing that does not depend on writing special code for every pair of Number subclasses.
Here's a challenge for those who want to make Number implement Comparable<Number>. Write the API documentation for the compareTo method. Tell me what I have to do if I am writing a new Number subclass in order to conform to the contract.
Patricia
Twisted - 28 Jul 2007 18:24 GMT > Even if a class represents values of some transcendental function there > can be some points at which the function has an algebraic solution. For > example, consider the sines of angles that can be expressed as rational > numbers of degrees. sin(30), sin(45), and sin(60) are exact solutions to > quadratic equations. To clarify, when I said above that transcendental and algebraic were unequal I meant individual numbers where one's known to be transcendental and the other algebraic.
The trig values that are algebraic are well-characterized aren't they? So knowing which are not transcendental is not impossible.
> However, to make Number implement Comparable we would need a general > approach to comparing that does not depend on writing special code for [quoted text clipped - 4 lines] > method. Tell me what I have to do if I am writing a new Number subclass > in order to conform to the contract. The simplest most general way is to convert to BigDecimal and punt to BigDecimal.compareTo, with precision decided by something (perhaps something new) in the way of a MathContext-like entity. It couldn't be passed to the compareTo method obviously so it would have to be a threadlocal or something (a singleton would cause problems if distinct threads did simultaneous math and wanted distinct precisions).
Ones that don't compare equals() have to be treated as distinct, so give a nonzero compareTo, and I think objects of different Number direct-subclasses never compare equals(). If they all have sensible implementations of hashCode() too, the thing to do would be:
In class Foo, see if the argument is also a Foo. If so, use a suitable comparison within Foos. Otherwise, get BigDecimal versions at the context-determined precision and compare those. If nonzero return the result. If zero compare the hashCodes. If nonzero return the result. If still zero ... should be damned rare, but I dunno what. :) Actually forget hash codes; in the case the arguments are of different Number direct-subclasses just use the lexical ordering of a.getClass().toString() and b.getClass().toString(), which should be different. Using a locale-independent collation!
But I think at this point the best thing is probably to leave things as is, and users of mixed Number types can convert to a common type manually to do comparisons. Implementing Number.compareTo(Number) in general is only warranted if people are liable to be stuffing a heterogeneous mix of Numbers into a TreeMap as keys or something. And since they all implement hashCode sensibly, so far as I'm aware, HashMap is probably the better choice for that anyway, leaving cases where you want a collection (e.g. TreeSet) to iterate over a heterogeneous mix in sorted order. For that a wrapper suffices:
public class NumberWrapper implements Comparable<NumberWrapper> { private Number delegate; private int bigDecimalDigitPrecision; // obvious constructor and getNumber() // obvious hashCode punts to delegate // obvious equals returns false if arg not a NumberWrapper, // then unwraps both and punts to delegates public int compareTo (NumberWrapper nw) { if (delegate.getClass().equals(nw.delegate.getClass())) { // Insert suitably clever use of reflection to call // delegate.compareTo(nw.delegate) with both cast to // the appropriate subclass. Making the above if // trigger if delegate classes differ but have // common ancestor deeper than Number left as an // exercise for the reader. return ... } BigDecimal t1 = // May need reflection here too, or for // Sun to put a bigDecimalValue(precision) in Number BigDecimal t2 = // Ditto, with nw.delegate int result = t1.compareTo(t2); if (result != 0) return result; return delegate.getClass().toString().compareTo( nw.delegate.getClass().toString()); } }
The major issues apparent are: * The wrapper will heavily need reflection, somewhat less if Number were changed non-drastically. Adding bigDecimalValue(precision) to Number would go a long way. Adding a compare(Number) that may throw if the class isn't the same would help enormously. * The wrappers can hold the precision to use, but may act up if ones with different precisions were mixed. * OTOH not using the wrappers seems to require either hard-coding the precision (evil!) or using a ThreadLocal (slow!)
Fortunately I think putting heterogeneous Numbers into a sorted collection is really damn rare.
Patricia Shanahan - 28 Jul 2007 19:01 GMT ...
>> However, to make Number implement Comparable we would need a general >> approach to comparing that does not depend on writing special code for [quoted text clipped - 11 lines] > threadlocal or something (a singleton would cause problems if distinct > threads did simultaneous math and wanted distinct precisions). This could lead to some very strange effects. You could have two numbers, x and z, that are different according to the comparison rules for their own class, but that match to the Number comparison precision.
x.compareTo(z) would be non-zero. However, there could be a third Number, y, of a different Number subclass, such that y.compareTo(x) and y.compareTo(z) are both zero.
> Fortunately I think putting heterogeneous Numbers into a sorted > collection is really damn rare. The killer argument for not having Number implement Comparable.
If a given Number subclass has a reasonable total order it can implement its own intra-class comparison. For example, Double implements Comparable<Double>, and BigDecimal implements Comparable<BigDecimal>.
If there is a need, and a good implementation, for a total order on a collection containing a couple of different Number subclasses, one could write a Comparator that handles that combination of classes, using appropriate special rules.
I think this approach deals with all the real cases, without opening up the general Number comparison can of worms.
Patricia
Michael Jung - 28 Jul 2007 22:52 GMT > > > * First, sorting a NaN in some arbitrary but consistent way, e.g. NaN > > > < -inf < -10 < -1 < 0 < 1 < 10 < inf, allows well-defined behavior and [quoted text clipped - 4 lines] > > comparing. > Explain please. Typically: if a>0 then 0<-a.
> > > - You can usually determine algebraically whether they are equal or > > > not. > > > > No. > > Do not bluntly contradict me in a public forum. I gave an explanation. Otherwise Patricia gave an appropriate reply.
> > Depending on what you do, solutions to these problems are unknown. > There's an equation that can in principle be solved to see if they are > equal. In practise it will be difficult with big enough (degree 5 or > more) polynomials and various transcendental functions. In many cases, > you know one is algebraic and the other transcendental and therefore > they must be unequal. For one, we are ordering, not checking for equality alone. You might possibly find an intricate way of comparing the smallest real roots of uneven polynomials (arbitrary degree). Take results of other functions that are not easily computed, but have interesting features to make them Numbers in a Java sense. Transcendental and algebraicness doesn't have anything to do with it.
> Those known to be unequal can be expanded in binary until you know > which is smaller, and you know it will take finite time. This assumes that they can be computed in this way. You may also consider extremely huge (factored) numbers, which in theory can be compared and computing it is totally unfeasible.
> Only ones close enough together and difficult to tackle analytically > remain. The policy with them might be to give them an arbitrary but > deterministic ordering perhaps based on class and internal > representation, or hashCode, or something. As Patricia has pointed out this leads to counterintuitive results and basically makes the whole comparing business obsolete.
Michael
Twisted - 29 Jul 2007 04:06 GMT > > > > * First, sorting a NaN in some arbitrary but consistent way, e.g. NaN > > > > < -inf < -10 < -1 < 0 < 1 < 10 < inf, allows well-defined behavior and [quoted text clipped - 6 lines] > > Typically: if a>0 then 0<-a. I don't know where to begin in trying to figure out what kind of drugs you either are taking but shouldn't or aren't taking but should here. :P
> > > > - You can usually determine algebraically whether they are equal or > > > > not. [quoted text clipped - 4 lines] > > I gave an explanation. I said something and your response was a blunt "No", which is rude.
> > There's an equation that can in principle be solved to see if they are > > equal. In practise it will be difficult with big enough (degree 5 or [quoted text clipped - 3 lines] > > For one, we are ordering, not checking for equality alone. You forgot that the main issue was in fact the "checking for equality" part. Comparing binary expansions of known-unequal numbers eventually and fairly trivially yields their order.
> This assumes that they can be computed in this way. You may also consider > extremely huge (factored) numbers, which in theory can be compared and > computing it is totally unfeasible. A number represented as a product of factors? Those are dead *easy*. Even if you don't first multiply them to get a plain BigInteger or whatever. You can estimate magnitude and know x < 10^y < this product for instance in many cases. Comparing them to each other can start with dropping common factors and comparing only what's left, especially easy if your internal representation is the prime factorization.
[snip remainder of attack]
This bickering is pointless. Have you nothing more constructive to do than try to tear down other people here?
Patricia Shanahan - 29 Jul 2007 04:33 GMT ...
>> For one, we are ordering, not checking for equality alone. > > You forgot that the main issue was in fact the "checking for equality" > part. Comparing binary expansions of known-unequal numbers eventually > and fairly trivially yields their order. Actually, there are two problems. I've been focusing on the sub-case in which, for each operand, there is a feasible, efficient algorithm for generating the next block of digits of the decimal expansion. Even in that case, the problem of equality checking remains.
The other case is where is no efficient decimal expansion algorithm. Either there is no algorithm at all, or it takes too much time and/or space to run it. It think that is the case Michael Jung is pursuing.
>> This assumes that they can be computed in this way. You may also consider >> extremely huge (factored) numbers, which in theory can be compared and [quoted text clipped - 7 lines] > especially easy if your internal representation is the prime > factorization. The devil is in the word "huge". In this context I would treat it as meaning "too big for brute force to be practical".
Patricia
Twisted - 29 Jul 2007 16:03 GMT > The other case is where is no efficient decimal expansion algorithm. > Either there is no algorithm at all, or it takes too much time and/or > space to run it. It think that is the case Michael Jung is pursuing. I considered that in another branch of this thread.
> The devil is in the word "huge". In this context I would treat it as > meaning "too big for brute force to be practical". That's why I suggested non-brute-force methods such as canceling common factors.
Lew - 29 Jul 2007 17:09 GMT >> The other case is where is no efficient decimal expansion algorithm. >> Either there is no algorithm at all, or it takes too much time and/or [quoted text clipped - 7 lines] > That's why I suggested non-brute-force methods such as canceling > common factors. Wouldn't those common factors only be findable through conceivably very long-running algorithms? If you have a fast technique to factor very large numbers then no cryptographic scheme is safe from you, is it?
I interpreted Patricia's remark to refer to the difficulty of finding the common factors.
 Signature Lew
Twisted - 30 Jul 2007 04:11 GMT > >> The other case is where is no efficient decimal expansion algorithm. > >> Either there is no algorithm at all, or it takes too much time and/or [quoted text clipped - 10 lines] > Wouldn't those common factors only be findable through conceivably very > long-running algorithms? If you'd bothered to read the whole thread you'd know that that particular remark came up in the context of numbers with already-known factorizations. :P
Patricia Shanahan - 29 Jul 2007 17:17 GMT >> The other case is where is no efficient decimal expansion algorithm. >> Either there is no algorithm at all, or it takes too much time and/or [quoted text clipped - 7 lines] > That's why I suggested non-brute-force methods such as canceling > common factors. If there happen to be common factors, by all means consider canceling them as an optimization, but to provide a general capability we would have to deal with pairs that have no common factors.
Patricia
Twisted - 30 Jul 2007 04:25 GMT > If there happen to be common factors, by all means consider canceling > them as an optimization, but to provide a general capability we would > have to deal with pairs that have no common factors. Ludicrous. Comparing large integers of known digit-sequence (in any base) is easy*. First ignore sign and any leading zeros, and compare magnitude. Is one longer than the other? Then it's bigger. No? Then is the most-significant digit higher or lower? If so you have your answer. If not are the second digits unequal? Etc. At the end, if both numbers were negative you flip the answer over. At the very start if they had opposite signs the positive one is larger and you immediately have the answer. -- This works for integers represented in straightforward ways.
* On modern architectures, base 2147483648 is probably best and I'm fairly sure it is what BigInteger uses -- comparing 31-bit words of the binary representation as unsigned Java ints in other words. (31- bit words being used because bit 31 of a 32-bit word is needed to hold a carry when performing arithmetic. I know for certain that JScience's LargeInteger is in fact implemented this way.)
Integers represented as factorizations can use common-factor elimination to get smaller numbers with no common factors, which can then be used to compute a digit sequence. But first heuristic methods can be used, e.g. each factor replaced with the next higher power of 10 and in another copy the next lower, and the base-ten log of the number thus bracketed between two known limits; if one range doesn't overlap the other you know right away which number is bigger. They probably will overlap, but it's better to use the smaller base of 2 anyway on a computer. No doubt there are other methods for anyone with the time, inclination, and ingenuity to find them (of which right now I lack the first two).
Integers like someone brought up earlier represented as (2^(m-1) + 2^(n +1))(2^k) ... are best converted into a sparse binary representation with only a few bits set, and then are susceptible to the above digit- sequence comparison method in base 2. One can represent the example by making a sparse binary for bit m-1, another for n+1, and another for k, oring the first two and left-shifting by k. Or having a SparseBinaryInteger with addition and multiplication methods. Multiplication takes each bit in one argument and uses it to left shift a copy of the other, and those copies are then added together to get the result. Adding finds pairs of identical bits and removes one while shifting the other left one position until no more identical pairs can be found, and then ors what's left to get the answer. SparseBinaryInteger is a natural representation for numbers of the form noted above.
Patricia Shanahan - 30 Jul 2007 04:54 GMT >> If there happen to be common factors, by all means consider canceling >> them as an optimization, but to provide a general capability we would [quoted text clipped - 9 lines] > have the answer. -- This works for integers represented in > straightforward ways. I agree that two numbers expressed as digit strings are easy to compare.
> * On modern architectures, base 2147483648 is probably best and I'm > fairly sure it is what BigInteger uses -- comparing 31-bit words of > the binary representation as unsigned Java ints in other words. (31- > bit words being used because bit 31 of a 32-bit word is needed to hold > a carry when performing arithmetic. I know for certain that JScience's > LargeInteger is in fact implemented this way.) Correct in principle. BigInteger actually uses 2**32 as base, rather than 2**31. It deals with carry, as well as int signedness, by using long temporaries.
> Integers represented as factorizations can use common-factor > elimination to get smaller numbers with no common factors, which can [quoted text clipped - 7 lines] > the time, inclination, and ingenuity to find them (of which right now > I lack the first two). I agree that there are a lot of special cases that can be simplified. I'm still concerned about worst case performance.
Patricia
Casey Hawthorne - 30 Jul 2007 05:52 GMT Will Groovy (a scripting language running on the JVM and needing its jar file) make applets? -- Regards, Casey
Twisted - 30 Jul 2007 08:54 GMT On Jul 30, 12:52 am, Casey Hawthorne <caseyhHAMMER_T...@istar.ca> wrote:
> Will Groovy (a scripting language running on the JVM and needing its > jar file) make applets? This seems intended to be a completely new thread. It has a new subject line with no Re: or (was Re: Foo), and it's completely irrelevant to Number and Comparable. Why was it posted as a reply to Patricia's message regarding integer math?
Twisted - 30 Jul 2007 08:52 GMT > Correct in principle. BigInteger actually uses 2**32 as base, rather > than 2**31. It deals with carry, as well as int signedness, by using > long temporaries. I had a hack once at making a bignum int type in some algol-derivative once, which had a 64-bit type. I found that using 32-bit chunks produced problems with multiplication. I can't remember exactly what they were though...
Michael Jung - 29 Jul 2007 10:47 GMT > > > > > * First, sorting a NaN in some arbitrary but consistent way, e.g. NaN > > > > > < -inf < -10 < -1 < 0 < 1 < 10 < inf, allows well-defined behavior and [quoted text clipped - 8 lines] > you either are taking but shouldn't or aren't taking but should > here. :P I assume you can correct the mistyping. The point remains valid.
> You forgot that the main issue was in fact the "checking for equality" > part. Comparing binary expansions of known-unequal numbers eventually > and fairly trivially yields their order. See below and Patricia's answer.
> > This assumes that they can be computed in this way. You may also consider > > extremely huge (factored) numbers, which in theory can be compared and [quoted text clipped - 6 lines] > especially easy if your internal representation is the prime > factorization. You have a good algorithm at hand that compares (2^(2^n)-2^(2^m-1))(2^(2^n)+2^(2^m+1)) and 2^(2^(n+1))-2^(2^(m+1)-1)? Note that this has two parameters only and IS easy. But if I know your algorithm, I'll add some more in there to break it. (n,m > 10^6) I am not a number cruncher, but be sure that there are non-trivial problems in that domain.
Three points against forcing comparability on numbers:
1. Checking for equality may be non-trivial, let alone ordering. Let alone computational.
See above.
2. For some numbers comparability may be pointless.
The complex numbers have been mentioned, but there are numbers naturally embedded into the reals, where you don't want that. Consider the numbers {0,1,2} with typical addition/multiplication all done with the remainder operation. This (e.g.) means -1 = 2. Ordering them is senseless.
3. Some comparability operations are counterintuitive, when embedded into the standard ones.
Suppose you have the positive reals and compare them via integer part, i.e. "x gt y <=> int(x) > int(y)". That still has nice properties, possibly sufficient for your purposes, may be more easy to compute (see above), etc. However several numbers are equal, which you wouldn't naturally consider so. E.g. x eq y does not imply 2*x eq 2*y.
Some of these arguments side in with the argument that you need to be able to supply comparability with arbitrary number implementations thereby getting even more counterintuitive results, since basically you are restricted to the interface methods of Number when comparing with other numbers.
Michael
Patricia Shanahan - 29 Jul 2007 14:36 GMT ...
> Some of these arguments side in with the argument that you need to be able to > supply comparability with arbitrary number implementations thereby getting > even more counterintuitive results, since basically you are restricted to the > interface methods of Number when comparing with other numbers. ...
This brings out one assumption I have been making silently, that one or more abstract helper methods could be added to Number, requiring them to be implemented in every concrete subclass of Number.
For example, if a solution were based on generating digits of the decimal expansion:
public abstract Iterator<Byte> digitIterator();
where the digitIterator result supplies successive digits of the decimal expansion.
The conclusion I have reached, based on the discussion, is that there is no set of methods that could be implemented in all reasonable subclasses of Number that would be sufficient to implement Comparable<Number> in a meaningful, useful way.
Patricia
Twisted - 29 Jul 2007 16:11 GMT > The conclusion I have reached, based on the discussion, is that there is > no set of methods that could be implemented in all reasonable subclasses > of Number that would be sufficient to implement Comparable<Number> in a > meaningful, useful way. I happen to think it is probably better to expect users of heterogeneous Numbers to manage conversion for intercomparison themselves. I'm not sure quite how I got stuck having to defend the possibility of doing it directly with compareTo() in (Real)Number, and I wouldn't mind not being hounded on the matter any further. It's possible; it's probably not at all easy and would require lots of special compare code in each subclass; it would likely be hackish and kludgy in places; and it's better off avoided. 'Nuff said.
Twisted - 29 Jul 2007 16:09 GMT > > > Typically: if a>0 then 0<-a. > > I don't know where to begin in trying to figure out what kind of drugs > > you either are taking but shouldn't or aren't taking but should > > here. :P > > I assume you can correct the mistyping. The point remains valid. There was a point? If NaNs are in your calculation it's already gone haywire. At least it won't outright blow up if they get into a TreeSet this way. If you want to throw on NaN you want to do so as soon as a NaN is produced, and if not, you want NaN to have well-defined (if perhaps strange) semantics.
> You have a good algorithm at hand that compares > (2^(2^n)-2^(2^m-1))(2^(2^n)+2^(2^m+1)) and 2^(2^(n+1))-2^(2^(m+1)-1)? Those aren't pure factorizations; they have additions and subtractions in them. We were discussing numbers represented like 2^a3^b5^c...
Please don't try to change the playing field out from under the players in the middle of the game; that's considered cheating. :)
> 2. For some numbers comparability may be pointless. > > The complex numbers have been mentioned Hence why quite early we'd all agreed that a RealNumber subclass would be a better target for making comparable.
> but there are numbers naturally > embedded into the reals, where you don't want that. Consider the numbers > {0,1,2} with typical addition/multiplication all done with the remainder > operation. This (e.g.) means -1 = 2. Ordering them is senseless. And they are not, contrary to your claim, "naturally embedded into the reals". If you think there's any kind of homomorphism from the reals onto any finite field you need to get your head examined.
> 3. Some comparability operations are counterintuitive, when embedded into the > standard ones. [quoted text clipped - 4 lines] > However several numbers are equal, which you wouldn't naturally consider so. > E.g. x eq y does not imply 2*x eq 2*y. That is the sort of comparison you perform explicitly on floor(x) or round(x) or something, rather than make the natural compareTo() order of a type. And so irrelevant here.
Michael Jung - 29 Jul 2007 18:44 GMT > > > > Typically: if a>0 then 0<-a. [last inequality should be 0>-a] > > > I don't know where to begin in trying to figure out what kind of drugs [quoted text clipped - 3 lines] > There was a point? If NaNs are in your calculation it's already gone > haywire. That was the point. If you got NaNs in your calculations, you've gone haywire, so why go the extra mile to compare it (and possibly keep the problem hidden)?
> > You have a good algorithm at hand that compares > > (2^(2^n)-2^(2^m-1))(2^(2^n)+2^(2^m+1)) and 2^(2^(n+1))-2^(2^(m+1)-1)? > Those aren't pure factorizations; they have additions and subtractions in > them. We were discussing numbers represented like 2^a3^b5^c... No, we are not. We are talking about big numbers which presumably have big factors, not those for which we have a factor representations at hand.
> Please don't try to change the playing field out from under the players in > the middle of the game; that's considered cheating. :) FWIW; the playing field is "all numbers are (reasonably) comparable", not "factor represented numbers are comparable".
> > 2. For some numbers comparability may be pointless. > > > > but there are numbers naturally embedded into the reals, where you don't > > want that. Consider the numbers {0,1,2} with typical > > addition/multiplication all done with the remainder operation. This > > (e.g.) means -1 = 2. Ordering them is senseless.
> And they are not, contrary to your claim, "naturally embedded into the > reals". If you think there's any kind of homomorphism from the reals onto > any finite field you need to get your head examined. Well, I could crack this here as you did with the inequality. You are talking about field-homomorphisms from the Reals onto any finite field. Not hard to find.
But you are building up straw men. Naturally embedded means homomorphism to you?
> > 3. Some comparability operations are counterintuitive, when embedded into > > the standard ones. [quoted text clipped - 6 lines] > round(x) or something, rather than make the natural compareTo() order > of a type. And so irrelevant here. You seem to be missing the point. Of course, you can do a compare with other operations than compareTo. Obviously, all the fancy number handling can be done without extending Number or using Java for that matter.
Michael
Twisted - 30 Jul 2007 04:10 GMT > That was the point. If you got NaNs in your calculations, you've gone haywire, > so why go the extra mile to compare it (and possibly keep the problem hidden)? If you believe NaNs should be detected early, then you believe that NaNs should not even exist, and instead that the JVM should throw a NotANumberException RuntimeException whenever a NaN would otherwise occur instead.
If NaNs shouldn't exist, then the issue of comparing them is moot. If they should, then the issue arises and some consistent ordering needs to be used.
> We were discussing numbers represented like 2^a3^b5^c... > > No, we are not. Yes we are. You said numbers represented as factors earlier. You can't now go and claim to have been talking about something completely different in order to "prove" yourself "right"; that's cheating. :P
> Well, I could crack this here as you did with the inequality. You are talking > about field-homomorphisms from the Reals onto any finite field. Not hard to > find. There are no embeddings that make sense. There's no subset of the real numbers that looks like a copy of any finite field. The closest you get is (-1,1) under * is isomorphic to F^2 under +. :P There are certainly no nontrivial let alone one-to-one ring homomorphisms from any cyclic ring of integers modulo any m into the reals, because the reals have no elements other than 0 of finite order under addition, among other reasons. Without those you don't have an embedding. These sorts of things go with complex numbers as Numbers but not RealNumbers and it's really "RealNumber implements Comparable" under discussion here, and has been since the first time complex numbers were brought up.
> But you are building up straw men. Naturally embedded means homomorphism to > you? Have you got some other definition? Other than "some of the elements are named the same"?
The only relationship present is that the cyclic rings are quotient rings of the ring of integers, a subring of the field of rationals, a subfield of the reals in turn. So there are homomorphisms one way but not the other aside from the trivial, and it's more like you can "embed" the integers, in a lossy fashion, in these cycles.
As for the higher-dimensional finite fields you can just forget about even trying.
[remainder of attack post snipped]
Isn't Sunday supposed to be the start of a new week? I'd hoped that would mean Saturday was the last day of Pick-on-Twisted Week.
At least if it's actually Pick-on-Twisted Month, there's only about two days left in *that*...:P
Michael Jung - 30 Jul 2007 18:13 GMT [...]
> > > We were discussing numbers represented like 2^a3^b5^c... > > No, we are not. > Yes we are. You said numbers represented as factors earlier. You can't > now go and claim to have been talking about something completely > different in order to "prove" yourself "right"; that's cheating. :P A quote:
:> This assumes that they can be computed in this way. You may also consider :> extremely huge (factored) numbers, which in theory can be compared and :> computing it is totally unfeasible. : A number represented as a product of factors? Those are dead *easy*. You said the latter. And we've discussing this moot point since then.
> > But you are building up straw men. Naturally embedded means homomorphism to > > you?
> Have you got some other definition? Other than "some of the elements > are named the same"? We have the integers being naturally embedded in the reals. I don't suppose you consider that just a naming coincidence.
> Isn't Sunday supposed to be the start of a new week? I'd hoped that > would mean Saturday was the last day of Pick-on-Twisted Week. Well you know now that I embed Z_7 into the reals...
Michael
Twisted - 31 Jul 2007 02:04 GMT > [...] > > > > We were discussing numbers represented like 2^a3^b5^c... [quoted text clipped - 7 lines] > :> extremely huge (factored) numbers, which in theory can be compared and > :> computing it is totally unfeasible. Yes. Obviously, numbers represented as a factorization might be unfeasible to multiply out to a plain BigInteger type representation, but the factorization can also be taken advantage of in comparing them.
> We have the integers being naturally embedded in the reals. I don't suppose > you consider that just a naming coincidence. We don't have any embedding homomorphisms from any integers-modulo-N ring into the reals other than the trivial one (they all map to zero). :P Their addition groups can be embedded nontrivially into the complex-numbers-under-multiplication group, and that's about it.
> Well you know now that I embed Z_7 into the reals... Not and keep Z_7's properties. For example, there's no nonzero element of the reals under addition that's of order dividing 7, so nothing you can map Z_7's 1 onto but zero, and as that's a generator of Z_7 it follows that the entire embedding has to be trivial.
You can certainly get Z_7 as a factor, but that's something else entirely than an embedding.
Michael Jung - 30 Jul 2007 21:15 GMT [...]
> You are talking about field-homomorphisms from the Reals onto any finite > field. Not hard to find. [...]
Since this is not of any importance to the discussion proper, I'd like to correct myself separately. It was supposed to read "any homomorphisms" instead of "field-homomorphisms". Depending on what properties you want to preserve these are not hard to find. Field-homomorphisms on the other hand are one of those that do not exists:-)
Michael
Patricia Shanahan - 30 Jul 2007 21:48 GMT > I have a follow-up to my own question: Perhaps what is in order is to > have an intermediary class like: "public class RealNumber extends > Number implements Comparable" -- and in the event where the are non- > definable comparisons, throw an exception. Then, you can have > Imaginary Numbers and allow the rest of us to work with numbers as we > naturally understand them. I think we have hashed over the general RealNumber case quite thoroughly. I would like to raise a different possibility which I think captures the spirit of that idea while dodging the problems we have been discussing.
Suppose there were an ExtendedBigDecimal with the following properties:
1. Its value set is the union of BigDecimal and the Double infinities and NaNs.
2. It is Comparable<ExtendedBigDecimal>, with natural order for number to number comparisons, and the Double.compareTo rules for infinities and NaNs.
Then I think every value in the java.lang and java.math concrete Number subclasses is exactly convertible to ExtendedBigDecimal, with the ExtendedBigDecimal compareTo consistent with the Number class' compareTo.
Suppose also there were an interface, EBDNumber, that has a single abstract method:
ExtendedBigDecimal convertToEBD();
and EBDNumber also extended Comparable<EBDNumber>
The comparison would be implemented by the Number subclass compareTo methods not giving up after finding the other object is of a different class. First it would check for it also implementing EBDNumber, and if so convert both numbers to ExtendedBigDecimal and use its compareTo.
Two questions:
1. Does this make any sense?
2. Would the mixed type comparisons it would support be sufficiently useful to justify the cost.
Note that it would not help with e.g. general rational number arithmetic. 1/3, in a rational number package, would not be exactly convertible to ExtendedBigDecimal.
Patricia
Twisted - 31 Jul 2007 02:09 GMT > Note that it would not help with e.g. general rational number > arithmetic. 1/3, in a rational number package, would not be exactly > convertible to ExtendedBigDecimal. Sure it would -- if, that is, ExtendedBigDecimal instances could be built to any choice of radix, such as 3. ;)
Michael Jung - 31 Jul 2007 20:32 GMT > Suppose there were an ExtendedBigDecimal with the following properties: > [quoted text clipped - 31 lines] > arithmetic. 1/3, in a rational number package, would not be exactly > convertible to ExtendedBigDecimal. As I see it, it all boils down to, for what purpose we extend Number. We have already seen that we lose all extensions of number that don't want to/should be compared, such as the complex, finite subsets, etc.
So, if I design a number class that should be internally comparable, would I want this to be comparable to ExtendedBigDecimal?
Say, I like fractions a lot and have "class Fractions { BigDecimal nominator; BigDecimal numerator; }" with lots of funky methods. I can even compare them. Would I bother to write a method that converts (literally) a fraction of my numbers to EBDs. What do I do with the rest?
Michael
Malcolm Dew-Jones - 31 Jul 2007 22:56 GMT : > Suppose there were an ExtendedBigDecimal with the following properties: : > [quoted text clipped - 31 lines] : > arithmetic. 1/3, in a rational number package, would not be exactly : > convertible to ExtendedBigDecimal.
: As I see it, it all boils down to, for what purpose we extend Number. We have : already seen that we lose all extensions of number that don't want to/should : be compared, such as the complex, finite subsets, etc.
: So, if I design a number class that should be internally comparable, would I : want this to be comparable to ExtendedBigDecimal?
: Say, I like fractions a lot and have "class Fractions { BigDecimal nominator; : BigDecimal numerator; }" with lots of funky methods. I can even compare : them. Would I bother to write a method that converts (literally) a fraction of : my numbers to EBDs. What do I do with the rest?
: Michael Yes, and other perfectly reasonable examples could be invented in which comparisons could not necessarily be made at all.
Imagine an astronomy application that compares the timing of events. A star explodes and later events like a dust cloud are caused by the explosion and the timing of the events can be compared. But the timing of events outside of some "local" region of the original star cannot be compared to the first star at all, it has no meaning.
Or numbers that represent survey distances on the earth. Depending on the geometric models and the distances involved, some measurements cannot be compared to one another.
$0.10
Owen Jacobson - 27 Jul 2007 02:22 GMT > So, I have read the SDN entry of why Number does not implement > Comparablehttp://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4414323 [quoted text clipped - 9 lines] > in Java (with the exception of NaN) are comparable. So, Double d = > 10.12 and Integer x = 11 ARE comparable. X is clearly larger. How would you implement Number#compareTo(Number n) in such a way that it imposes a total ordering on *all* objects that satisfy the Number type, including user-supplied Number subclasses? There is nothing in either the JLS or the JRE to prevent you from adding new Number subclasses -- say you have your own arbitrary-precision decimal class that's 4x as fast as Sun's for operations you care about[1] that also extends Number?
Comparable's contract is only thoroughly satisfiable when the implementation is closed to extension, either by being final or by being pacakge-visible or less with known subclasses.
[1] Contrived, but valid, example
Eric Sosman - 27 Jul 2007 03:15 GMT > So, I have read the SDN entry of why Number does not implement > Comparable [quoted text clipped - 6 lines] > compareTo() in Float -- no such special condition exists for the case > of NaN What compare() implementation do you suggest for
public class Complex extends Number { private final double real; private final double imag; ... }
... or would you prefer to say that a complex number cannot be a Number?
 Signature Eric Sosman esosman@ieee-dot-org.invalid
Sideswipe - 01 Aug 2007 21:58 GMT Actually, what I had in mind was this:
public abstract class Number implements Comparable .... // dont actually implement compareTo()
public class Float extends Number {
public int compareTo(Object otherNumber) { if(otherNumber == Float.NaN) throw new ArithmaticException("NaN is not comparable"); if(otherNumber instanceof Integer) return this.floatValue() - ((Integer)otherNumber).intValue(); }
}
This is not the slickest example, but that's what I had in mind. And, yes, the specific case is that I have a mixed collection of Numbers that I need to order. What I argue for is to let all the subclasses sort their own comparison problems out. I can see from further postings that the issue is contentious enough to simply allow Sun's implementation to stand.
Patricia Shanahan - 01 Aug 2007 23:13 GMT > Actually, what I had in mind was this: > [quoted text clipped - 19 lines] > postings that the issue is contentious enough to simply allow Sun's > implementation to stand. Remember that you can sort using a Comparator<Number>. All you need is a total order that makes sense in your context, among the things you expect to find in your collection. You can limit it to the types you intend to mix. If you don't expect to see a NaN, you can throw an exception if you hit one.
Patricia
Oliver Wong - 27 Jul 2007 16:01 GMT > So, I have read the SDN entry of why Number does not implement > Comparable [quoted text clipped - 26 lines] > Thoughts, anyone? I fully realize I may bring out the worst in people > with this question I'm siding with Sun on this one. I think since, Java 1.5, none of the classes in the standard library simply implement Comparable. Instead, they may implement Comparable<Integer>, or Comparable<Float>, etc. Typically, for a given class Foo, if it implements Comparable, it does so in the form of Comparable<Foo>.
So it follows that if Number were to implement Comparable, it would do so in the form of Comparable<Number>. Which means that any instance of Number must be comparable to any other instance of Number.
In particular, that means that there must exist code in the Integer class to allow it to be comparable to Double, in addition to all the other possible combinations. Since Number is not final, end-users can generate their own subclass of Number, and know Integer would have to someone add code so that it becomes comparable to those user defined classes.
Contrast that with the current situation, where Integer implements Comparable<Integer>, and the Integer class itself is final. Now, the code in Integer only needs to take care of comparing itself against other Integers, and it doesn't have to worry about user-defined subclasses, since Integer is final.
If ever you need to compare an Integer to a Double, it is usually straightforward to convert the Integer into a Double, and then compare the resulting Double against the original Double.
- Oliver
Sideswipe - 01 Aug 2007 21:42 GMT Wow, I am not sure if I should be thanks for asking such a good question (I consider my question good because it seriously flushes out the reasoning of Number not implementing Comparable) or if I should be chastened for opening up a flame war. My understanding of number theory is collegiate for sure, but I appreciate the generous commentary.
Patricia Shanahan - 01 Aug 2007 21:57 GMT > Wow, I am not sure if I should be thanks for asking such a good > question (I consider my question good because it seriously flushes out > the reasoning of Number not implementing Comparable) or if I should be > chastened for opening up a flame war. My understanding of number > theory is collegiate for sure, but I appreciate the generous > commentary. I think you should be thanked. I know I have a clearer view of the subject now than when the thread started.
Each poster is responsible for whatever words they choose to type, every time they write an article. Nobody can force someone else to flame.
Thank you!
Patricia
Eric Sosman - 02 Aug 2007 03:05 GMT > [...] > Each poster is responsible for whatever words they choose to type, every > time they write an article. Nobody can force someone else to flame. "Temptation, O Temptation! Were we, I pray, intended To shun, whate'er our station, Your fascination splendid? Or fall, whene'er we view you, Head over heels into you?"
 Signature Eric Sosman esosman@ieee-dot-org.invalid
Patricia Shanahan - 02 Aug 2007 03:24 GMT >> [...] >> Each poster is responsible for whatever words they choose to type, every [quoted text clipped - 6 lines] > Or fall, whene'er we view you, > Head over heels into you?" comp lang java newsgroups many questions and answers some pointless flaming
Patricia
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|