Finding the next largest number for any given number format
Hello. I am writing some java code to model open and closed intervals, as well as a few other areas to do with set theory.
More specifically, I have written a class that models a range of numbers. The class is generic in that it allows any subclass of Number for its lower and upper bounds, and then delgates the task of comparison and checking equality to a Comparator<Number>. This object is really the powering core of the class, since it gets to decide which classes of number it will compare, which it will throw an exception for when asked to compare, how it manages comparison between floating-point and integer numbers (if at all), and so on.
My main trouble comes when detecting if two ranges have a non-empty set as their intersection ( a method called 'intersects(NumberRangeother)' ). The trouble is that it is not sufficient to determine if a bound of this NumberRange lies within the bounds ofother. This obviously applies to integers, but likewise to floating point numbers too, since a bit pattern and the next largest bit pattern exhibit the same behaviour as two adjacent integers.
Example:
(2, 4) Intersection (3, 5) = ?- although 3 is an element of (2,4), the two ranges do not intersect.
In order to check that NumberRangeother intersects NumberRangethis, I would need to check that either the first number inthis, or the last number inthis, lies within the bounds ofother. So effectively I need to convert an open interval to a closed interval. Since there is no way to model an infinite set of numbers on a computer, anyway, I should be able to treat doubles and floats as integer types: increase the lowerBound of an open interval by one to turn it into the corresponding closed interval. This would require some sort of method capable of increasing the significand by one, modifying the exponent if need be, etc. Is there any such method, in the core java API? I had a look through Double and Float and could not find any. I don't espcially wish to have to code this myself, since I tend to make mistakes when doing complicated bitwise calculations.
Thanks
[2190 byte] By [
fragorla] at [2007-10-2 13:57:34]
> Example:
> (2, 4) Intersection (3, 5) = ?- although 3 is an
> element of (2,4), the two ranges do not intersect.
?
Apparently your definition of an intersection differs from the one I know:
A = range (2,4) = {2,3,4}
B = range (3,5) = {3,4,5}
A ∩ B = range (3,4)
I also am a bit confused how the subject of your thread applies to your question.
>?
>Apparently your definition of an intersection differs from the one I know:
>A = range (2,4) = {2,3,4}
>B = range (3,5) = {3,4,5}
>A ∩ B = range (3,4)
You have me worried now. Do you not use a round bracket to denote an interval exclusive of an endpoint, and a square bracket to denote one inclusive of an endpoint? For example:
(2,4) = {3}
[2,4] = {2,3,4}
[2,4) = {2,3} // half open interval
Assuming 2 and 4 are elements of Z.
At any rate, this is what I was meaning. Therefore (2,4) ∩ (3,5) = ?br>
> I also am a bit confused how the subject of your thread applies to your question.
Ok.
Supposing I have a range of Number objects, which I am trying to represent in a java class.
R = [a, b]
( note the square brackets - a closed interval )
I want to include a java method for taking the complement of this set of numbers. Suppose R is a range of java Integer types. The complement of R would be
[ Integer.MIN_VALUE, a ) Union ( b, Integer.MAX_VALUE ]
( note that there are round brackets and square brackets )
My class has to have a way of representing closed as well as open bounds, if I am to implement a complement method.
Now supposing I wanted to find if two arbitrary ranges interesected, ie had a non-zero intersection (I know you know this, I am just being explicit in case I am not being clear enough). I need to implement some sort of algorithm in this intersects(Range other) method. All I can do is check other's lower and upper bounds against this's lower and upper bounds.
Returning to the complement method for a moment, there are two ways I could go about it. Firstly, I could return
[MinValue, a-1] Union [b+1, MaxValue]
or
[MinValue, a) Union (b, MaxValue]
In the first instance, I would have no logic in my class for describing closed/open endpoints. All Ranges would be closed. In the second instance, I would have to have two booleans in the class, one to say if the upper bound was excluded, one to say if the lower bound was excluded.
The first approach would then only work for java Numbers of an integer type: Short, Long, Integer (not bothering with Byte). This is because, by adding or subtracting 1 from the upper and lower bounds, I am implicitly assuming that b+1 is the next greatest Number from b, and a-1 is the next lowest Number from a. Plainly this is not the case with floating point numbers.
However, a similar problem happens with floating point numbers. Assume there is some form of floating point number that is represented in decimal, and has a significand just four 4 places long. Now imagine the scenario
( 0.01002, 0.01004 ) ∩ ( 0.01003, 0.01005 )
Again, this is the empty set. Similarly,
( 1 002 000, 1 004 000 ) ∩ ( 1 003 000, 1 005 000 )
is also the empty set.
Just like integer types, floating point types can only represent a fixed amount of numbers. However, for floating point types, the next largest number is not n+1 (like it is for all integer types), rather it is the significand of the number + 1 (with an adjustment to the exponent as well if the significand was 111111111...)
So, back to finding the intersection. I am given two sets of Number objects:
[a, b) and (c, d]. Do they intersect?
Algorithm: first, check c is contained in the range [a, b), or that b is contained in (c, d] (the two statements are equivalent). This is necessary but not sufficient. To check for sufficiency, we must also ensure that c is not the next largest Number from b.
For integer types: check c != b + 1
For floating point types, ?
My title was 'Finding the next largest number for any given number format'. I think this sums up my question pretty well: I need some sort of way of finding out the next biggest (and next smallest) number, for any given number format that gets passed to this Range class. I have had a long, long think about it, and I keep arriving at the conclusion that I need this piece of information about whatever number format I am representing, no matter what, if I am to implement all of these methods correctly. However, nothing would make me happier than finding that this is not the case.
Btw, do you have a reference of mathematical character codes, ie the one that gave you ∩? I'd be very grateful.
Thanks, fragorl
> You have me worried now. Do you not use a round bracket
> to denote an interval exclusive of an endpoint, and a
> square bracket to denote one inclusive of an endpoint?
Don't worry, your absolutely right. I read your post too quickly
and thought you meant by (m,n) an Object NumberRange from m to n
rather than an interval.
> However, a similar problem happens with floating point
> numbers. Assume there is some form of floating point number
> that is represented in decimal, and has a significand just
> four 4 places long. Now imagine the scenario
>
> ( 0.01002, 0.01004 ) ∩ ( 0.01003, 0.01005 )
>
> Again, this is the empty set.
Now you treat those doubles the same as integers. I'd say you end
up with (0.01003, 0.01004) because there lie an infinite number of
elements within that interval.
But if you say that it results in an empty set, the number 0.0001 is the
same as the number 1 in the set N. Correct?
> My title was 'Finding the next largest number for any given number format'.
> I think this sums up my question pretty well: I need some sort of way of
> finding out the next biggest (and next smallest) number, for any given
> number format that gets passed to this Range class. I have had a long,
> long think about it, and I keep arriving at the conclusion that I need
> this piece of information about whatever number format I am representing,
> no matter what, if I am to implement all of these methods correctly.
> However, nothing would make me happier than finding that this is not
> the case.
Something like this?
_
||
| + Number implements Comparable<Number> |
|_|
||
| - number: BigDecimal|
| - unity: BigDecimal|
|_|
||
| + Number(num: String): << constr >>|
| - Number(BigDecimal n, BigDecimal u): << constr >> |
| + compareTo(other: Number): int|
| + next(): Number|
| + number(): BigDecimal|
| + previous(): Number|
| - setUnity(num: String): void |
| + toString(): String|
|_|
__
||
| + NumberRange|
|__|
||
| - begin: Number |
| - end: Number|
| - beginIncluded: boolean|
| - endIncluded: boolean|
|__|
||
| + NumberRange(b: Number, e: Number, bi: boolean, ei: boolean): << constr >> |
| + begin(): Number|
| + beginIncluded(): boolean |
| + end(): Number |
| + endIncluded(): boolean|
| + intersect(other: NumberRange): NumberRange|
| - isWithinRange(number: Number): boolean|
| + toString(): String|
|__|
For example: if you input the number 0.01003, the unity for this number
would be 0.0001. Inputting a whole number then the unity would be 1.0.
And the next() and previous() methods would look like this:
public Number next() {
BigDecimal nextBD = number.add(unity);
Number nextNum = new Number(nextBD, unity);
return nextNum;
}
public Number previous() {
BigDecimal previousBD = number.subtract(unity);
Number previousNum = new Number(previousBD, unity);
return previousNum;
}
> Btw, do you have a reference of mathematical character codes, ie
> the one that gave you ∩? I'd be very grateful.
No, I'm afraid not. You can use a couple of them, such as ∩ (ALT+239)
from the extended ASCII chart:
http://www.cdrummond.qc.ca/cegep/informat/Professeurs/Alain/files/ascii.htm
but the sign for a set union, for example, isn't in there.
Many students/scientists use LaTeX for displaying mathematical characters,
use Google to find out more on the subject.
> Thanks, fragorl
I hope it was of help to you.
Regards,
Bart.
I don't honestly see any point in modeling an essentially continuous topological property like open and closed intervals in a discrete space like the floats, but if you want it, here is a candidate for a function that does something like what you want. Just search for the smallest increment that actually increases the number.
static double nextLarger(double a){
double dx = 1.0;
double c;
while((a+dx) == a) dx *= 2.0;
c = dx;
while((a+c) > a){ dx = c; c /= 2.0;}
return (x+dx);
}
For the record, this code will fail if a is the maximum value for the double. Either the first while loop will run forever or the code produces a Nan or something. You might want to guard that.
@Prometheuzz:
>> However, a similar problem happens with floating point
>> numbers. Assume there is some form of floating point number
>> that is represented in decimal, and has a significand just
>> four 4 places long. Now imagine the scenario
>>
>> ( 0.01002, 0.01004 ) ∩ ( 0.01003, 0.01005 )
>>
>> Again, this is the empty set.
>
>Now you treat those doubles the same as integers. I'd say you end
>up with (0.01003, 0.01004) because there lie an infinite number of
>elements within that interval.
>But if you say that it results in an empty set, the number 0.0001 is the
>same as the number 1 in the set N. Correct?
Well, sort of. It is not so much 0.0001, or any other number, that behaves the same as the number 1 in N, rather it is the first bit of the significand that does. I think this is what you meant anyhow. What number that first bit represents depends, of course, on the sign and the exponent.
@All
I not specifically trying to model a continuous space of numbers using some floating point type; this is not my goal. What I am trying to do is write a generic class which models a range/interval/call it what you will of either continuous or discrete, comparable types.
I started off using Number, as that was the highest level of abstraction I could think of when I started, for a type that could be considered to have a range (:P). I then looked on the internet for various other Range / Interval / (variations on the above names) classes. This turned up the obvious-in-hindsight observation that any type which can be compared can be though of as having a range. This leads to either a Range of Comparables, or even more abstractedly, a Range of any type that you can supply a Comparator for.
I was trying to think of types that would actually be continous, or whether it would turn out that every comparable java object broke down into a discrete range. Then I realised that Strings are a good, simple example of a continuous, comparable type. For any two, nonequal Strings (a and c, with c > a), you can always find a third (b) such that a < b < c, by adding an extra character on to the end of 'a'.
e.g.
a = "J", c = "K", b = "JA"
and so on. So really, this example applies to lots of things. Basically, any type that can annex (when constructed) an undefined amount of memory will exhibit continuous behaviour (correct me if that's wrong). BigDecimal is another example (as you pointed out in your UML schematic, Prometheuzz).
@Prometheuzz:
Thanks for that UML; it pretty much encapsulates what I am talking about, except that I should abstract even further now (I guess that was obvious from the start; I didn't realise it however). A Range Object should be supplied with 3 sets of things now:
1.) A Comparator capable of comparing the type of Object which the Range is a range of. Alternatively, there could be a constructor without this which uses Comparables instead of Objects.
2.) Objects representing upper and lower bounds, and booleans to say whether they are excluded or included. (Exceptions will be thrown if the Comparator cannot handle the types supplied).
3.) In addition to the Comparator, an instance of another interface which specifies a.) if the given Object type will form a discrete or continous range, and b.) if discrete, it implements those next() and previous() methods you discussed as part of your Number object.
I might call this a 'DiscreteOrContinuousSpecifier', or something. :P
What do you think?
@marlin314:
Thanks for that code as well; it will come in handy when specifying an instance for part 3.) above that takes care of doubles.
> Thanks for that UML; it pretty much encapsulates what
> I am talking about, except that I should abstract
> even further now (I guess that was obvious from the
> start; I didn't realise it however).
>
> [snip]
>
> What do you think?
For you particular application, that sounds ok.
Good luck.
Alright. Cheers for the help.fragorl
