Calculating the amount of times a number needs to be added to a coordinate for the floored value to change

Question

I have a problem which requires me to calculate the amount of times a number must be added to a coordinate x for the floored value of x to change. It must support both positive and negative numbers being added.

The example code below highlights the problem.

public static void main(String[] args) {
    double x = 10;
    double amountToAdd = -0.25; // must support positive + negative values
    int lastFlooredX = Integer.MIN_VALUE;
    int i = 0;

    while (i++ < 100) {
        int flooredX = (int) Math.floor(x);
        if (lastFlooredX == flooredX) {
            throw new UnsupportedOperationException("Iterated over the same number twice!");
        }
        lastFlooredX = flooredX;

        int additionsBeforeFloorChanges = // I need help!;

        x += (amountToAdd * additionsBeforeFloorChanges);
    }
}

Answer 1

The problem with the additive approach is that it's very susceptible to floating point rounding error.

Consider this simple approach for +ve x and d:

double xfloor = Math.floor(x);
int count = 0;
do
{
    x += d;
    count += 1;
    System.out.println(count + " " + x);
}
while(Math.floor(x) == xfloor);
System.out.format("Result: %d%n", count);

With x = 0 and d = 0.1 this produces:

1 0.1
2 0.2
3 0.30000000000000004
4 0.4
5 0.5
6 0.6
7 0.7
8 0.7999999999999999
9 0.8999999999999999
10 0.9999999999999999
11 1.0999999999999999
Result: 11

Which obviously is not correct.

As an alternative, we can use division to determine the number of steps required. We have to be careful to distinguish between cases where x and d have the same or opposite signs.

static int minAddFloorChange(double x, double d)
{
    if(d == 0) throw new IllegalArgumentException();

    double xa = Math.abs(x); 
    double da = Math.abs(d);

    if(x == 0 || (Math.signum(x) == Math.signum(d)))
    {           
        double xfrac = (xa == Math.rint(xa)) ? 1 : Math.ceil(xa) - xa;
        double count = xfrac / da;
        return (int)Math.ceil(count);
    }
    else
    {
        double xfrac = (x == Math.rint(xa)) ? 0 : xa - Math.floor(xa);
        double count = xfrac / da;
        return Math.max(1, (int)Math.ceil(count));
    }
}

Note, I'm not claiming that this approach is completely immune from rounding errors - you'd need someone with more knowledge of the IEEE 754 floating point format than I have to address that.

Test:

static void test(double x, double d)
{
    System.out.println(x + " : " +  d + " = " + minAddFloorChange(x, d));
}

public static void main(String[] args)
{
    test(0, 0.1);
    test(0, -0.1);

    test(1, 0.1);
    test(-1, -0.1);

    test(1, -0.1);
    test(-1, 0.1);

    test(0, +Double.MIN_VALUE);
    test(0, -Double.MIN_VALUE);

    test(1, Double.MIN_VALUE);
    test(-1, -Double.MIN_VALUE);

    test(1, -Double.MIN_VALUE);
    test(-1, Double.MIN_VALUE);     
}

Output:

0.0 : 0.1 = 10
0.0 : -0.1 = 10
1.0 : 0.1 = 10
-1.0 : -0.1 = 10
1.0 : -0.1 = 1
-1.0 : 0.1 = 1
0.0 : 4.9E-324 = 2147483647
0.0 : -4.9E-324 = 2147483647
1.0 : 4.9E-324 = 2147483647
-1.0 : -4.9E-324 = 2147483647
1.0 : -4.9E-324 = 1
-1.0 : 4.9E-324 = 1

Answer 2

public static void main(String[] args) {
        double x = 10.1;
        double amountToAdd = -0.25; // must support positive+negative values
        double y = x;
        int i = 0;

        if(x-Math.floor(x)!=0) {
          while(Math.abs(Math.floor(y)-Math.floor(x))==0) {
             i++;
             y = y +amountToAdd;    
          }
        }
        System.out.println(i);
    }

for amountToAddas -0.25 output and x as 10.1

1

for amountToAddas 0.25 output and x as 10.1

4