Floating point arithmetic

General Discussions
#1

I’m trying to make a maths computer game, and have been getting frustated with floating-point arithmetic imprecision. For example, I do some calculations on a number and I always end up with something like 8.99999999999978 instead of 9.0.

I never understood why the hell that happened but I found this great blog article about how it works. Here it is if you’re interested: http://funcall.blogspot.com/2007/06/how-floating-point-works.html

I was thinking of using BigDecimal instead of doubles, but I don’t think they’ll solve my troubles because the floating point arithmetic will still be inexact, but to a lesser extent. By the way, here’s an interesting thread about BigDecimal performance:
http://forum.java.sun.com/thread.jspa?threadID=5119298&start=0&tstart=0

I modified the original benchmark to get rid of the string concatenation and parsing:

public static void test(){
		System.out.println("Test: BigDecimal performance");
        final long iterations = 10000000;
        
        long t = System.currentTimeMillis();
        double d = 123.456;
        for (int i = 0; i < iterations; i++) {
            final double b = d * System.currentTimeMillis() * System.currentTimeMillis();
        }
        System.out.println("double: "+(System.currentTimeMillis() - t));
 
        
        t = System.currentTimeMillis();
        BigDecimal bd = new BigDecimal("123.456");
        for (int i = 0; i < iterations; i++) {
            final BigDecimal b = bd.multiply(new BigDecimal(System.currentTimeMillis())).multiply(new BigDecimal(System.currentTimeMillis()));
        }
        System.out.println("java.math.BigDecimal: "+(System.currentTimeMillis() - t));
	}

These are my results, after running that test method once to warm it up:

Java HotSpot(TM) Client VM 11.0-b11
Test: BigDecimal performance
double: 797
java.math.BigDecimal: 9250

So BigDecimal is more than 10 times slower in java 6.

#2

What kind of operations do you use that give those results?

If you know that the result from a certain operation should be an integer then you could always just convert to an int after the calculation.

#3

I don’t think you really need (or want) to be using BigDecimal for game purposes. Sure you’ll get rounding errors, but regular float precision is still very accurate - you just have to make sure to use an epsilon value when doing equality testing. Even then I don’t find myself doing equality tests often, usually you’re comparing shapes or distances anyway, where it doesn’t matter if the actual threshold is 0.0000001 out.

Why do you think you need exact values?

#4

Well it freaks me out when 10*0.09 gives 0.8999999999999999 and it’s likely to freak out any poor kids trying to learn maths.

Also, it stuffs up my inequality testing (>, <) so I have to fudge things which can often cause other errors that I don’t anticipate.

#5

I’ve had problems like this with physics engines (cos 90, for example, gives like 1.0 * 10^-8), where objects would never truly be at rest. The solution, I found, was to simply round numbers that are at a certain precision. Ex. ) if (x <= 0.0001) x = 0; And the like. It kept things fine in terms of accuracy and got rid of rounding issues. You just need to check the numbers every timestep.


float decimalNumber;
int roundedNumber = Math.round(decimalNumber);
if (Math.abs(decimalNumber-roundedNumber) <= 0.00001)
     decimalNumber = roundedNumber;

The above typically makes things work okay.

#6

What about java.text.NumberFormat, it seems to do all the hard work for you with min/max fractional digits

#7

Sure, if you’d writing a calculator and displaying the result then BigDecimal (or fixed point arithmetic) is probably the way to go. But in a game when do you ever have to display the result of 10*0.9 to the user?

Similarly with equality testing - you don’t test discrete values, you test against ranges or limits. If you think of your world as one big continuous range then testing discrete values doesn’t really make sense. I’m struggling to see the actual problem you’re having that requires having to fudge things.

#8

It’s a game about maths, I guess they have to enter the answers to the questions and then the answers are displayed. Thats why the results need to be accurate.

#9

Yeah, and also discrete testing happens a lot (at least for me), when I’m looking for zeroed values.

#10

Thanks for the replies guys. 8)

I’m using NumberFormat to present the numbers and that works well, but it doesn’t fix the inequality testing.

For example, an enemy has 0.9 hit points and should die after being hit exactly 10 times with a sword that does 0.09 damage per hit, but since 10*0.09 gives 0.8999999999999999 it will actually take 11 hits to kill the enemy which is really a big problem for a kid learning multiplication!

Yep, it does work a little like a calculator in that way, but the presentation of the number is OK, NumberFormat fixes it, but the above example shows the problem.

They are great ideas for zero-testing. I’ll try them out, thanks! :slight_smile:

#11

I meant you could parse the result of NumberFormat to a double again, after which (in)equality testing works again (I think…)

#12

So would that be like rounding the number to some decimal place? This might cause problems when the rounded result is used to do more calculations. For example:

double c = 10.0/3.0;
double c3 = 3*c;
// do rounding:
double million = 1000000;
double rc = Math.round(c*million)/million;
double rc3 = 3*rc;
// round the result:
double rrc3 = Math.round(rc3*million)/million;;
System.out.println("c == "+c+", c3 == "+c3);
System.out.println("rc == "+rc+", rc3 == "+rc3+", rrc3 == "+rrc3);

gives

c == 3.3333333333333335, c3 == 10.0
rc == 3.333333, rc3 == 9.999999, rrc3 == 9.999999

So 3 * 10/3 gives 10 without any rounding, but with rounding it gives 9.999999, whether or not the result is rounded. :frowning:

PS: to quickly test this stuff I used beanshell in this little program I made:
http://www.freewebs.com/commanderkeith/SlaveBot/SlaveBot_jvm1.4+.jnlp

#13

Well, you should keep the ‘real’ value around ofcourse for further calculations.

paste this in your SlaveBot:

import java.text.NumberFormat;

NumberFormat nf = NumberFormat.getInstance();

double format(double a, int digits)
{
   nf.setMaximumFractionDigits(digits);
   return Double.parseDouble(nf.format(a).replace(',', '.'));
}

double format(double a)
{
   return format(a, 8);
}

double take = 0.09;
double value = 9.00;

while(format(value) != 0.00)
   value -= take; // NOT rounding the intermediate result

System.out.println("formatted value: 0.00");
System.out.println("real value: "+value);


System.out.println("\n\n");


public int tryToKill(double healthPoints, double hitPoints)
{
   System.out.println("attacking: "+healthPoints+" / "+hitPoints);
   int attacks = 0;
   while(format(healthPoints - hitPoints) >= 0.00) 
   {
      healthPoints -= hitPoints;
      attacks++;
      
      System.out.println("   healthPoints after attack: "+healthPoints+" (~"+ format(healthPoints)+")");
   }
   System.out.println("fp-error: "+healthPoints);
   return attacks;
}

System.out.println("attacks required: "+tryToKill(0.9, 0.09));



formatted value: 0.00
real value: 1.0352829704629585E-14



attacking: 0.9 / 0.09
   healthPoints after attack: 0.81 (~0.81)
   healthPoints after attack: 0.7200000000000001 (~0.72)
   healthPoints after attack: 0.6300000000000001 (~0.63)
   healthPoints after attack: 0.5400000000000001 (~0.54)
   healthPoints after attack: 0.4500000000000002 (~0.45)
   healthPoints after attack: 0.3600000000000002 (~0.36)
   healthPoints after attack: 0.27000000000000024 (~0.27)
   healthPoints after attack: 0.18000000000000024 (~0.18)
   healthPoints after attack: 0.09000000000000025 (~0.09)
   healthPoints after attack: 2.498001805406602E-16 (~0.0)
fp-error: 2.498001805406602E-16
attacks required: 10
#14

Wow, that came out bad! ;D I should really rename that program to something less butt-sounding.

Thanks man, I’ll study that code tonight.

Bye,
keith

#15

Hm… ‘insert this code in your SlaveBot’ might have been worse…

Anyway, I think this is as good as it gets with floating-point values (that are inherently inaccurate).
If it turns out this just doesn’t cut it for you, you might want to look into doing your math with longs.


static int BITS = 16;
static long encode(double v) { if(v > (1 << BITS)) throw new Exception();  return (long)(v * (1 << BITS)); }
static long decode(long v) { return (double)v / (1 << BITS); }
static long add(long a, long b) { return a + b; }
static long sub(long a, long b) { return a - b; }
static long mul(long a, long b) { return (a * b) >>> BITS; }
static long div(long a, long b) { return (a << BITS) / b; }

(or something like that…)

#16
#17

Riven, that is a really top piece of code, thanks a lot for putting it together.

I’m just trying to think how I can use it in my application - I think the string parsing and creation will kill the frame rate in my game so I need to think how to do something similar without using NumberFormat. I’ll probably modify the equality testing part of the code so it takes the floating point error into account.

Ah, interesting. Can java do that? It doesn’t sound like that’s exactly what BigDecimal does. (http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigDecimal.html)