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

[Lew]

I considered that in another branch of this thread.


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.

 

[Patricia Shanahan]

I considered that in another branch of this thread.


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

 

[Michael Jung]

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
you either are taking but shouldn't or aren't taking but should
here.

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.

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)?

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

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?

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.

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]

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.

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 +. 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*...

 

[Twisted]

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.

 

[Twisted]

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]

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.

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

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]

Will Groovy (a scripting language running on the JVM and needing its
jar file) make applets?

 

[Twisted]

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

 

[Twisted]

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?

 

[Michael Jung]

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.

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.

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

 

[Michael Jung]

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]

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]

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.

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

 

[Twisted]

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]

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.

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]

Michael Jung ([email protected]) wrote:
: > 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.

: 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

 

[Sideswipe]

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]

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

 

[Sideswipe]

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.