«

Hi everyone,

I am a Java beginner, and I am trying to create a very simple binary
tree.
Each node has a value, the left child has the same value + an
increment, the right child has the same value - the same increment.
I try to recursively create the tree, but I have precision problems.

My "main" node has a value of 10, the increment is 0.1, tree depth is
4
So i want a tree that goes like this :
depth 1 : 10
depth 2 : 0.9 / 10.1
depth 3 : 0.8 / 10 / 10 / 10.2
depth 4 : 0.7 / 0.9 / 0.9 / 10.1 / 0.9 / 10.1 / 10.1 / 10.3

But at depth 4 when I try to print the value I get 9.700000000000001
instead of 9.7, and 10.299999999999999 instead of 10.3
And things get worse when the depth increase.
All the values and increment are stored in double (native type).

Is it normal? How can I avoid this problem?
Thanks a lot,
Tom.

[main class]
double increment = 0.1;
double startValue = 10;
int maxDepth = 4;
Tree myTree = new Tree(startValue, 1);
myTree.recursivelyCreateChildren(increment, maxDepth);

[Tree.java]
public int depth;
public double value;
public Tree leftChild;
public Tree rightChild;

Tree(double value, int depth){
this.value=value;
this.depth=depth;
System.out.println("node of depth " + depth + " created, value = " +
value);
}

public void createChildren(double increment){
rightChild = new Tree(value - increment, depth+1);
leftChild = new Tree(value + increment, depth+1);
}

public void recursivelyCreateChildren(double increment, int maxDepth)
{
if (depth < maxDepth){
createChildren(increment);
leftChild.recursivelyCreateChildren(increment, maxDepth);
rightChild.recursivelyCreateChildren(increment, maxDepth);
}
}

Cyprien wrote:
> Hi everyone,
>
> I am a Java beginner, and I am trying to create a very simple binary
> tree.
> Each node has a value, the left child has the same value + an
> increment, the right child has the same value - the same increment.
> I try to recursively create the tree, but I have precision problems.
>
> My "main" node has a value of 10, the increment is 0.1, tree depth is
> 4
> So i want a tree that goes like this :
> depth 1 : 10
> depth 2 : 0.9 / 10.1
> depth 3 : 0.8 / 10 / 10 / 10.2
> depth 4 : 0.7 / 0.9 / 0.9 / 10.1 / 0.9 / 10.1 / 10.1 / 10.3
>
> But at depth 4 when I try to print the value I get 9.700000000000001
> instead of 9.7, and 10.299999999999999 instead of 10.3
> And things get worse when the depth increase.
> All the values and increment are stored in double (native type).
>
> Is it normal? How can I avoid this problem?
....

This is normal, but you can avoid it in this situation either by using
BigDecimal, or by making your increment an integer multiple of a power
of two.

double is a binary type. It is very efficient at fairly accurate
approximate representation of a wide range of magnitudes, but gives no
preference to numbers that are exact, short, decimal fractions. In
particular, 0.1 is not exactly representable in double. On the other
hand, small integers and 1/8 are exactly representable, so you would get
exact results if you used 1/8 as increment.

BigDecimal is decimal based, and can exactly represent any integer, 0.1,
and any sum of those numbers.

Patricia

On Sat, 7 Jun 2008 05:10:59 -0700 (PDT), Cyprien
<> wrote, quoted or indirectly quoted
someone who said :

>
>But at depth 4 when I try to print the value I get 9.700000000000001
>instead of 9.7, and 10.299999999999999 instead of 10.3

see http:://mindprod.com/jgloss/floatingpoint.html
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Thanks a lot guys.