Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / August 2007

Tip: Looking for answers? Try searching our database.

Discussion of why java.lang.Number does not implement Comparable

Thread view: 
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 Magazines

Get 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 ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.