question regarding java puzzlers #2

B

blmblm

[ snip ]
The point of using BigDecimal for printing the exact values of doubles
is that the conversion from double to BigDecimal is never an
approximation.

At least we agree about that. :)?
The results of double operations are defined in terms of two aspects:

1. What would be the exact result of this calculation, if we could store it?

2. Pick a representable value to store based on the answer to question 1.

"Rounding" is the process of reducing the nominal exact result to a round
number that can be stored.

In many cases the exact answer is not needed, and cannot be calculated.
The implementation just has to find out enough about it to get the
rounded answer right.

And we agree here ....

Other comments in my other two replies just now (to Chris Uppal
and Lew).
 
P

Patricia Shanahan

This, I think, is the heart of the problem. You use the word "approximation",
but it's not clear what a value is an approximation /to/. A big decimal,
seeing a double with exact value
0.1000000000000000055511151231257827021181583404541015625
has no way of knowing whether that is an "approximation" to
0.1
or to
0.100000000000000005551115
or, indeed, to
0.100000000000000005551115123125782702118158340454101562500000000001
So what is it going to choose ?

Yes, I thought about that, and you may be right that there's really no
sensible choice other than the one made by the BigDecimal constructor.
It still seems subtly wrong to me, but maybe not more so than any
other choice.
That goes double

! (pun intended?)
when you consider that BigDecimal's /job/ is the precise
representation of numerical values -- it would be inappropriate for it to make
information-loosing guesses about what the programmer "really meant". If you
want to convert doubles to BigDecimals using different rules (which is not in
itself unreasonable), then some of the possible rules are pre-packed for you.
For instance, by using Double.toString(double), and the BigDecimal(String)
constructor, you can convert using the
shortest-sequence-of-decimal-digits-which-maps-to-the-same-floating-point-value
rule (as Patricia has mentioned).

I don't really think that the concept of "approximation" is appropriate here.
There is a sense in which floating point computation can be considered to be
"like" precise computation with a certain amount of random noise added, so that
(like real physical measurements), you only ever have an approximate number,
and -- equally importantly -- you don't know what the true number should be.
That picture is fine as an approximation (;-) but it doesn't really reflect the
semantics of floating point arithmetic.

I think is close to what's underlying my vague sense of unease --
except for the part about "random noise". As you say:
The rules for Java FP are precise and
exact, down to the last bit -- there is no approximation, or error involved at
all[*].

Well, if you add floating-point numbers of different magnitudes,
there is round-off error involved -- possibly a precise and
well-defined error, but error.

Indeed, but generally the objective is to keep the error to a minimum.
For the most frequent operations, the error is the absolute minimum
possible. The rule for dealing with rounding from numbers exactly half
way between two representable numbers is designed to be predictable, but
round half down and half up.
If we programmers want to use floating point values to represent
something other than the specific set of rational numbers defined by the IEEE
format,

Rational numbers with some unusual properties under arithmetic
operations, no? e.g., addition is not always associative.

Given that, I'm inclined to stick with my claim that it's more
sensible to regard floating-point numbers as approximations of
reals than as rationals, even though almost [*] every floating-point
number has associated with it an exact rational value.

[*] Excluding NaN and other "not number" values (+/- Inf?).

Also -0, a double that is useful for representing numbers with tiny
absolute magnitude, but known negative sign. The mathematical rationals
have a single zero, because arbitrarily tiny numbers have rational
representations.
But I may still just not be looking at things from the most useful
or reasonable perspective.

Remember that if you are doing double arithmetic there is no particular
reason to assume that the true value has a short decimal representation.
It is convenient to have a relatively short default conversion to
String, because people prefer short numbers.

Truncating on conversion to BigDecimal would be an arbitrary rounding
error. How many digits would you drop? If the conversion is done exactly
the programmer has control because setScale() can be used to chop off
digits. Generally, rounding error is a BAD THING, not something to do
for the fun of it.

The program at the end of this message calculates sqrt(2) two ways,
using exactly the result of Math.sqrt(2), and rounding it to 17 decimal
places, the most that can be justified for a double of magnitude around 1.0.

The square of the rounded square root is further from 2 than the square
of the raw square root without any rounding.

Raw:
-2.7343234630647692806884916507957232351955020204815893780647684252471663057804107666015625E-16
Rounded: -2.862320485909535225E-16

import java.math.BigDecimal;
import java.math.RoundingMode;

public class SquareRootTest {
public static void main(String[] args) {
test(2);
}

static void test(int square){
BigDecimal bigSquare = BigDecimal.valueOf(square);
double dRoot = Math.sqrt(square);
BigDecimal bigRoot = new BigDecimal(dRoot);
BigDecimal roundedBigRoot =
bigRoot.setScale(17,RoundingMode.HALF_EVEN);
BigDecimal rawError = bigSquare.subtract(bigRoot.multiply(bigRoot));
BigDecimal roundedError =
bigSquare.subtract(roundedBigRoot.multiply(roundedBigRoot));
System.out.println("Raw: "+rawError+" Rounded: "+roundedError);
}
}


Patricia



Patricia
 
C

Chris Uppal

The rules for Java FP are precise and
exact, down to the last bit -- there is no approximation, or error
involved at all[*].

Well, if you add floating-point numbers of different magnitudes,
there is round-off error involved -- possibly a precise and
well-defined error, but error.

Not really. The rules are precise, and as long as the implementation follows
the rules then there is -- by definition -- no error involved. Any more than
there is any roundoff /error/ in:
(int)(3.14159)

Rational numbers with some unusual properties under arithmetic
operations, no? e.g., addition is not always associative.

I prefer to think of it as that the definition of floating point operators is
not what one might naively expect, and is no more than /similar/ to the
definitions of the corresponding operations on the reals (or rationals). That
awkward fact is a large part of the reason why floating point numbers should be
avoided except under somewhat special circumstances. (Such as: precision not
required; FP-sophisticated programmer available; program correctness optional
;-), and so on.)

Given that, I'm inclined to stick with my claim that it's more
sensible to regard floating-point numbers as approximations of
reals than as rationals, even though almost [*] every floating-point
number has associated with it an exact rational value.

[*] Excluding NaN and other "not number" values (+/- Inf?).

But I may still just not be looking at things from the most useful
or reasonable perspective.

I'm certainly not claiming that it's not a /useful/ perspective, but it isn't
the /only/ perspective, and it isn't the most /correct/ perspective. It may
well be an ideal perspective from which to think about some properties of some
expressions of some algorithms (especially if all the numbers have similar
absolute magnitudes, or where the divergences from "pure" arithmetic can be
modelled as noise), but it's worthwhile having a different perspective
available into which you can "flip" either as a check, or when the other seems
to be failing altogether.

-- chris
 
B

blmblm

The rules for Java FP are precise and
exact, down to the last bit -- there is no approximation, or error
involved at all[*].

Well, if you add floating-point numbers of different magnitudes,
there is round-off error involved -- possibly a precise and
well-defined error, but error.

Not really. The rules are precise, and as long as the implementation follows
the rules then there is -- by definition -- no error involved. Any more than
there is any roundoff /error/ in:
(int)(3.14159)

I think we're using "error" to mean different things here.
I prefer to think of it as that the definition of floating point operators is
not what one might naively expect, and is no more than /similar/ to the
definitions of the corresponding operations on the reals (or rationals).

I think I'm starting to get your point here. ("Finally"?)
That
awkward fact is a large part of the reason why floating point numbers should be
avoided except under somewhat special circumstances. (Such as: precision not
required; FP-sophisticated programmer available; program correctness optional
;-), and so on.)

Pretty much agreed. I think if you're doing the kind of "number
crunching" that seems to make up a lot of scientific computing, you
probably can't get acceptable performance without using floating
point. But to get results that are meaningful, *someone* should
have the kind of expertise needed to understand how the limitations
of floating point affect the calculations.
Given that, I'm inclined to stick with my claim that it's more
sensible to regard floating-point numbers as approximations of
reals than as rationals, even though almost [*] every floating-point
number has associated with it an exact rational value.

[*] Excluding NaN and other "not number" values (+/- Inf?).

But I may still just not be looking at things from the most useful
or reasonable perspective.

I'm certainly not claiming that it's not a /useful/ perspective, but it isn't
the /only/ perspective, and it isn't the most /correct/ perspective. It may
well be an ideal perspective from which to think about some properties of some
expressions of some algorithms (especially if all the numbers have similar
absolute magnitudes, or where the divergences from "pure" arithmetic can be
modelled as noise), but it's worthwhile having a different perspective
available into which you can "flip" either as a check, or when the other seems
to be failing altogether.
 
B

blmblm

[ snip ]
The rules for Java FP are precise and
exact, down to the last bit -- there is no approximation, or error involved at
all[*].

Well, if you add floating-point numbers of different magnitudes,
there is round-off error involved -- possibly a precise and
well-defined error, but error.

Indeed, but generally the objective is to keep the error to a minimum.
For the most frequent operations, the error is the absolute minimum
possible. The rule for dealing with rounding from numbers exactly half
way between two representable numbers is designed to be predictable, but
round half down and half up.
Sure.
If we programmers want to use floating point values to represent
something other than the specific set of rational numbers defined by the IEEE
format,

Rational numbers with some unusual properties under arithmetic
operations, no? e.g., addition is not always associative.

Given that, I'm inclined to stick with my claim that it's more
sensible to regard floating-point numbers as approximations of
reals than as rationals, even though almost [*] every floating-point
number has associated with it an exact rational value.

[*] Excluding NaN and other "not number" values (+/- Inf?).

Also -0, a double that is useful for representing numbers with tiny
absolute magnitude, but known negative sign. The mathematical rationals
have a single zero, because arbitrarily tiny numbers have rational
representations.

That too. (I knew I'd leave something out but was too slack to look
up the IEEE standard to get a complete list .... )
Remember that if you are doing double arithmetic there is no particular
reason to assume that the true value has a short decimal representation.
It is convenient to have a relatively short default conversion to
String, because people prefer short numbers.

Truncating on conversion to BigDecimal would be an arbitrary rounding
error. How many digits would you drop? If the conversion is done exactly
the programmer has control because setScale() can be used to chop off
digits. Generally, rounding error is a BAD THING, not something to do
for the fun of it.

Well, sure, but ....

I would have guessed, without thinking about at any length, that
since each floating-point number floatNum can be thought of as
representing a range of real numbers (a small interval containing
the exact value of the representation), it would be possible to
choose a value decimalNum in that range that could be expressed
in base 10 with a number of significant digits appropriate for the
number of bits of mantissa, and that converting a string representation
of decimalNum to floating point would yield floatNum again. Your
experiment below, though, suggests that maybe this isn't possible,
or that's it's trickier than it seems.
The program at the end of this message calculates sqrt(2) two ways,
using exactly the result of Math.sqrt(2), and rounding it to 17 decimal
places, the most that can be justified for a double of magnitude around 1.0.

I'm speculating that you chose 17 because it's one more than the 16
that (according to a quick Google search) represents the approximate
number of decimal significant figures a double can represent. True?
The square of the rounded square root is further from 2 than the square
of the raw square root without any rounding.

Raw:
-2.7343234630647692806884916507957232351955020204815893780647684252471663057804107666015625E-16
Rounded: -2.862320485909535225E-16

So obviously (?) rounding to 17 places doesn't give the kind of
reversible float-to-short-decimal conversion I tried to describe
earlier. I wonder whether this means that it just isn't possible,
or whether 17 is not the right number of digits to keep.

Huh. I don't really have the time and inclination to think this
through carefully, so if I'm starting to try the experts' patience,
I hope they/you will bail out.
import java.math.BigDecimal;
import java.math.RoundingMode;

public class SquareRootTest {
public static void main(String[] args) {
test(2);
}

static void test(int square){
BigDecimal bigSquare = BigDecimal.valueOf(square);
double dRoot = Math.sqrt(square);
BigDecimal bigRoot = new BigDecimal(dRoot);
BigDecimal roundedBigRoot =
bigRoot.setScale(17,RoundingMode.HALF_EVEN);
BigDecimal rawError = bigSquare.subtract(bigRoot.multiply(bigRoot));
BigDecimal roundedError =
bigSquare.subtract(roundedBigRoot.multiply(roundedBigRoot));
System.out.println("Raw: "+rawError+" Rounded: "+roundedError);
}
}
 
P

Patricia Shanahan

I'm speculating that you chose 17 because it's one more than the 16
that (according to a quick Google search) represents the approximate
number of decimal significant figures a double can represent. True?

Yes, I wanted to err on the side of keeping data.
So obviously (?) rounding to 17 places doesn't give the kind of
reversible float-to-short-decimal conversion I tried to describe
earlier. I wonder whether this means that it just isn't possible,
or whether 17 is not the right number of digits to keep.

BigDecimal does have a valueOf(double) method that uses the Double
toString representation of the double. That should be reversible. The
number of digits depends on the double.

Patricia
 
B

blmblm

Yes, I wanted to err on the side of keeping data.

(Sorry about the delay in responding -- I started this subthread
and don't want to just abandon it midstream, but apparently my
interest in thinking hard about the issues is limited .... )

I guess I'm wondering whether you erred far enough -- that is,
whether it would have been more appropriate to use 18. But I'm
too slack to do the kind of careful analysis that would be needed
BigDecimal does have a valueOf(double) method that uses the Double
toString representation of the double. That should be reversible. The
number of digits depends on the double.

And in fact using valueOf(double) in your test program gives a more
accurate answer. Below, for the record, is my adaptation of your
test program, allowing one to specify the number of significant
figures and comparing using the BigDecimal(double) constructor with
valueOf(double), and its output.

I'm not sure I understand any of this very well, but I'm not quite
curious enough .... Best to let it drop now maybe.


import java.math.BigDecimal;
import java.math.RoundingMode;

public class SquareRootTestBLMBLM {
public static void main(String[] args) {
testWithConstructor(2, 17);
testWithConstructor(2, 18);
testWithValueOf(2, 17);
testWithValueOf(2, 18);
}

static void testWithConstructor(int square, int digits){
BigDecimal bigSquare = BigDecimal.valueOf(square);
double dRoot = Math.sqrt(square);
BigDecimal bigRoot = new BigDecimal(dRoot);
BigDecimal roundedBigRoot = bigRoot.setScale(digits,RoundingMode.HALF_EVEN);
BigDecimal rawError = bigSquare.subtract(bigRoot.multiply(bigRoot));
BigDecimal roundedError =
bigSquare.subtract(roundedBigRoot.multiply(roundedBigRoot));
System.out.println("\nUsing BigDecimal constructor and " + digits +
" digits:");
System.out.println("Root: " + bigRoot);
System.out.println("Raw error: " + rawError);
System.out.println("Rounded error: " + roundedError);
}

static void testWithValueOf(int square, int digits){
BigDecimal bigSquare = BigDecimal.valueOf(square);
double dRoot = Math.sqrt(square);
BigDecimal bigRoot = BigDecimal.valueOf(dRoot);
BigDecimal roundedBigRoot = bigRoot.setScale(digits,RoundingMode.HALF_EVEN);
BigDecimal rawError = bigSquare.subtract(bigRoot.multiply(bigRoot));
BigDecimal roundedError =
bigSquare.subtract(roundedBigRoot.multiply(roundedBigRoot));
System.out.println("\nUsing BigDecimal valueOf and " + digits +
" digits:");
System.out.println("Root: " + bigRoot);
System.out.println("Raw error: " + rawError);
System.out.println("Rounded error: " + roundedError);
}
}


Output:

Using BigDecimal constructor and 17 digits:
Root: 1.4142135623730951454746218587388284504413604736328125
Raw error: -2.7343234630647692806884916507957232351955020204815893780647684252471663057804107666015625E-16
Rounded error: -2.862320485909535225E-16

Using BigDecimal constructor and 18 digits:
Root: 1.4142135623730951454746218587388284504413604736328125
Raw error: -2.7343234630647692806884916507957232351955020204815893780647684252471663057804107666015625E-16
Rounded error: -2.72089912967222571025E-16

Using BigDecimal valueOf and 17 digits:
Root: 1.4142135623730951
Raw error: -1.4481069235364401E-16
Rounded error: -1.448106923536440100E-16

Using BigDecimal valueOf and 18 digits:
Root: 1.4142135623730951
Raw error: -1.4481069235364401E-16
Rounded error: -1.44810692353644010000E-16


(Now that I think about it, it probably doesn't make sense to
round the result of using valueOf(double). Oh well.)
 
C

Chris Smith

But those are binary "significant figures" (bits), not the same as
the decimal (base 10) significant figures I'm talking about.

I'd add that "significant figures" is the wrong word here. A double has
52 bits of precision in the representation of the mantissa, but doubles
don't have significant figures. If one needs to keep track of
significant figures, then one needs to do it with a data type that does
so.

The point of BugDecimal, on the other hand, is to represent exact values
(or values that are rounded according to precisely defined rules). Most
of the time, of course, it's incorrect to convert a double to a
BigDecimal; but on the few occasions where that is actually desired, it
is perfectly reasonable to assume that the programmer wants the exact
mathematical value of that double. Significant figures don't enter into
it; the double has an exact value, and you're asking for it. If you
want to round the BigDecimal to fewer digits, such as if you know that
the value is only accurate to some smaller number of significant
figures, then setScale does that, and has a version that lets you
specify a rounding mode.

There are a few reasons that it doesn't make sense for BigDecimal to
round by default; one is that no one asked it to round, and there's
simply no other easy way to get an exact decimal value from a double.
The other, and more important, reason is that if you need to limit
precision, you'll need to limit it to something other than the precision
of the double data type. If you are attempting to use doubles to
manipulate values that happen to have all or nearly all of the mantissa
bits significant, then you're using the wrong data type anyway.
Assuming that's not the case, when you convert to a BigDecimal you'll
want to either work with intermediate values at full precision, or
convert them to an appropriate precision for your data, NOT for the data
type you happened to be using to represent them.
 
M

Mark Thornton

Chris said:
I'd add that "significant figures" is the wrong word here. A double has
52 bits of precision in the representation of the mantissa, but doubles
don't have significant figures. If one needs to keep track of
significant figures, then one needs to do it with a data type that does
so.

Isn't it 53 bits for normalised numbers (the leading 1 bit is implicit)?

Mark Thornton
 
C

Chris Smith

I would have guessed [...] it would be possible to
choose a value decimalNum in that range that could be expressed
in base 10 with a number of significant digits appropriate for the
number of bits of mantissa, and that converting a string representation
of decimalNum to floating point would yield floatNum again.

It is possible to define such a reversible conversion. In fact, the
methods Double.toString and Double.parseDouble are exactly such a pair
of reversible transformations between double and String, with no loss of
information. The fact that the conversion is reversible doesn't mean it
is correct, or that it's a good idea to use it for intermediate results.
Adding one to integers is also a reversible transformation, but it still
gives you a wrong answer.

In essence, there are several distinct, but similar, scenarios where you
want to convert something to decimal. Different techniques are
appropriate for different scenarios.

Scenario I: You need a lossless conversion back and forth between double
and a decimal type that doesn't lose information. This is what
Double.toString and Double.parseDouble are designed for. BigDecimal's
valueOf(double) also does it.

Scenario II: You need a conversion to decimal for values that are read
from a user or from some device that gives input in short decimal
numbers. If the values are stored in the double data type (which is
only appropriate if their original precision is much less than the
precision of the double data type), and you later want to convert them
to BigDecimal or String, then BigDecimal.valueOf or Double.toString are
the way to go, because the bias toward short decimal representations
actually helps you recover the intended value.

Scenario III: You are working with values from a source that's not
biased to provide round numbers in decimal, and you need to communicate
them to another source that won't be aware of your internal data types
so that a completely reversible conversion isn't feasible.

This is the tougher case. There are trade-offs between communication
bandwidth/size and accuracy, but on average it's better for accuracy to
use the full decimal value of your double -- that is, new BigDecimal
(val), or if you need a string, new BigDecimal(val).toString(). The
reason this is better "on average" instead of "all the time" is that as
you noted, the double already contained binary rounding error. It's
possible that you'll get lucky, and the decimal rounding error will be
in the opposite direction from the binary rounding error, so that they
cancel each other out -- but smart money is on the rounding error
accumulating instead.

If you want to make appropriate trade-offs between size and accuracy,
you can do it explicitly using setScale.

You have appropriate choices for all of these scenarios. If you're
uncomfortable with the behavior of BigDecimal when it's constructed with
a double parameter, that's understandable, because converting double to
BigDecimal is certainly not a common need at all, and most often happens
in scenario 2 where rounding the number in reversible ways is often the
appropriate choice; in fact, I've only ever used new BigDecimal(double)
for demonstrating things on newsgroups. But it does have a specific
well-defined behavior that can be valuable, and other valuable behaviors
can be achieved in other ways.
Your
experiment below, though, suggests that maybe this isn't possible,
or that's it's trickier than it seems.

Patricia's experiment suggests that rounding to the nearest even decimal
number is likely to harm the accuracy of a resulting calculation when
you didn't have any reason to expect the right answer to have a short
decimal representation to begin with. It doesn't guarantee that
reversing the rounding is impossible (in fact, it is possible, as you
could see by using the doubleValue method on the result).

Actually, Patricia's result was somewhat fortuitous. By rounding to 17
places, she got an answer that was further off. If she'd rounded to 16
or 18 places (or used BigDecimal.valueOf), she'd have gotten something
closer. That's a fluke of the test case she used, though. Here's a
modified test that demonstrates that on average, using BigDecimal's
valueOf, which does as you expected, provides poorer accuracy on square
roots of integers, versus new BigDecimal. In other words, if you
introduce this new decimal rounding inaccuracies after the already-
suffered binary rounding inaccuracies, you will occasionally luck out
and round in the correct direction; but on average, you'll end up
considerably worse off.

public class Test
{
public static void main(String[] args)
{
BigDecimal error = BigDecimal.ZERO;

for (int square = 1; square < 500; square++)
{
BigDecimal bigSquare = BigDecimal.valueOf(square);
double dRoot = Math.sqrt(square);
BigDecimal bigRoot = new BigDecimal(dRoot);
BigDecimal roundedBigRoot = BigDecimal.valueOf(dRoot);
BigDecimal rawError = bigSquare.subtract(
bigRoot.multiply(bigRoot));
BigDecimal roundedError = bigSquare.subtract(roundedBigRoot
.multiply(roundedBigRoot));

error = error.add(rawError.abs());
error = error.subtract(roundedError.abs());

System.out.println("Error: " + error);
}
}
}

Although the first few integers end up closer with the rounded version,
the error eventually does more harm than good. By the time you reach
500, the error is greater by something on the order of 10^-12 when
rounding the second time.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,774
Messages
2,569,596
Members
45,132
Latest member
TeresaWcq1
Top