Adding and subtracting exact values to float

Question

Question:

The total amount of floating points is finite, there's about 2^32 of them. With a float, you can go directly to the next or previous one using java.lang.Math.nextAfter. I call that a single leap. My main quesion, composed of sub questions is, how can I navigate on floats using leaps ?

First, how can I move a float to another with multiple leaps at once ?

public static float moveFloat(float value, int leaps) {
    for(int i = 0; i < Math.abs(leaps); i++)
        value = Math.nextAfter(value, Float.POSITIVE_INFINITY * signum(leaps));
    return value;
}

That way should work on theory but is really unoptimized. How can I do it in a single addition ?

I also need to know how much leaps there's between 2 floats. Here's the example implementation for this one:

public static int getLeaps(float value, float destination) {
    int leaps = 0;
    float direction = signum(destination - value);

    while(value * direction < destination * direction) {
        value = Math.nextAfter(value, Float.POSITIVE_INFINITY * direction);
        leaps++;
    }

    return leaps;
}

Again, same problem here. This implementation isn't suitable.

Extra:

The thing I call a leap, does it have an actual name ?

Background:

I'm trying to make a simple 2D physics engine in Java and I have trouble with my floating point operations. I learned about relative error float comparison and it helped a bit but it's not magic. What I want is to be exact with my floating points.

I already know a lot of base ten numbers cannot be exactly represented with floating points but execptionally, I don't care. All I want is exact float arithmetic in base 2.

To simplify, in my collision detection and response process, I check if shapes overlap (let's stay in one dimension for this example) and I replace the 2 shapes overlapping using their weight.

See this example:

If the black lines are the float values(and the space between each other leaps) whatever the precision is, I want to place both shapes (colored lines) to be exactly at the brown position. (The brown position is determined by the weights ratio and by rounding. What I call penetration is the overlaping area/distance. If the penetration would of been 5, red would been pushed by 1 and blue by 4).

The problem is, do to that I have to keep the penetration of the collision (in this case the penetration is exactly the ULP of the float, or 1 leap) in a float and I suspect this leads to inexactitude. If the penetration value is bigger than the coordinates of the shapes, it will be less precise so they won't be exactly replaced at the good coordinate.

What I imagine is to keep the penetration of the collision as the amount of leaps I need to get from one to the another and use it afterwards.

This is a simplified version of the current code I have:

public class ReplaceResolver implements CollisionResolver {
    @Override
    public void resolve(Collision collision) {
        float deltaB = collision.weightRatio * collision.penetration; //bodyA's weight over the sum of the 2 (pre calculated)
        float deltaA = 1f - deltaB;

        //the normal indicates where the shape should be pushed. For now, my engine is only AA so a component of the normal (x or y) is always 0 while the other is 1
        if(deltaB > 0)
            replace(collision.bodyA, collision.normalB, deltaA); 

        if(deltaA > 0)
            replace(collision.bodyB, collision.normalA, deltaB);
    }

    private void replace(Body body, Vector2 normal, float delta) {
        body.getPosition().x += normal.x * delta; //body.getPosition() is a Vector2
        body.getPosition().y += normal.y * delta;
    }
}

Obviously, this doesn't work properly and accumulates floating point precision error. The error is well handled by my collision detection which checks for float equality using ULP. However it breaks when crossing 0 because of the ULP going extremely low.

I could simply fix an epsilon for a physic simulation but it would remove the whole point of using floats. The technique I want to use lets the user choose his precision implicitly and theorically should be working with any precision.

Answer 1

I want to do the same calculation. So, if "leaps" means as @aka.nice said, the integer difference/span/distance between two float-point values according to the IEEE 754 floating-point "single format" bit layout (IEEE754 Format), I may have found a simple method:

public static native int floatToRawIntBits(float value) and Java_java_lang_Float_floatToRawIntBits can be used for this purpose, which has similar functionality to my test code in c++ (reinterpret a memory (reinterpret_cast)).

#include <stdio.h>

/* https://stackoverflow.com/questions/44008357/adding-and-subtracting-exact-values-to-float */
int main(void) {
    float float0 = 1.5f;
    float float1 = 1.5000001f;
    int intbits_of_float0 = *(int *)&float0;
    int intbits_of_float1 = *(int *)&float1;

    printf("float %.17g is reinterpreted as an integer %d\n", float0, intbits_of_float0);
    printf("float %.17g is reinterpreted as an integer %d\n", float1, intbits_of_float1);

    return 0;
}

And, the Java code (online compiler) below is used to calcuate the "leaps":

public class Toy {
    public static void main(String args[]) {
        int length = 0x82000000;
        int x = length >>> 24;
        int y = (length >>> 24) & 0xFF;

        System.out.println("length = " + length + ", x = " + x + ", y = " + y);

        float float0 = 1.5f;
        float float1 = 1.5000001f;
        float float2 = 1.5000002f;
        float float4 = 1.5000004f;
        float float5 = 1.5000005f;

        // testLeaps(float0, float4);
        // testLeaps(0, float5);
        // testLeaps(0, -float1);
        // testLeaps(-float1, 0);

        System.out.println(Math.nextAfter(-float1, Float.POSITIVE_INFINITY));
        System.out.println(INT_POWER_MASK & Float.floatToIntBits(-float0));
        System.out.println(INT_POWER_MASK & Float.floatToIntBits(float0));
        // testLeaps(-float1, -float0);
        testLeaps(-float0, 0);
        testLeaps(float0, 0);
    }

    public static void testLeaps(float value, float destination) {
        System.out.println("optLeaps(" + value + ", " + destination + ") = " + optLeaps(value, destination));
        System.out.println("getLeaps(" + value + ", " + destination + ") = " + getLeaps(value, destination));
    }

    public static final int INT_POWER_MASK = 0x7f800000 | 0x007fffff; // ~0x80000000
    /**
     * Retrieves the integer difference between two float-point values according to
     * the IEEE 754 floating-point "single format" bit layout.
     * 
     * <pre>
     * mask 0x80000000 | 0x7f800000            | 0x007fffff
     *            sign | exponent              | coefficient/significand/mantissa
     *              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
     *              |  |                       |                                                                    |
     *              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
     *               31 30                   23 22                                                                 0
     * 0x7fc00000 => NaN
     * 0x7f800000 +Infinity
     * 0xff800000 -Infinity
     * </pre>
     * 
     * Using base (radix) 10, the numerical value of such a float type number is
     * `(-1)^sign x coefficient x 10^exponent`, so the coefficient is a key factor
     * to calculation of leaps coefficient.
     * 
     * @param value       the first operand
     * @param destination the second operand
     * @return the integer span from {@code value} to {@code destination}
     */
    public static int optLeaps(float value, float destination) {
        // TODO process possible cases for some special inputs.

        int valueBits = Float.floatToIntBits(value); // IEEE 754 floating-point "single format" bit layout
        int destinationBits = Float.floatToIntBits(destination); // IEEE 754 floating-point "single format" bit layout
        int leaps; // Float.intBitsToFloat();
        if ((destinationBits ^ valueBits) >= 0) {
            leaps = Math.abs(destinationBits - valueBits);
        } else {
            leaps = INT_POWER_MASK & destinationBits + INT_POWER_MASK & valueBits;
        }
        return leaps;
    }

    public static int getLeaps(float value, float destination) {
        int leaps = 0;
        float signum = Math.signum(destination - value);

        // float direction = Float.POSITIVE_INFINITY * signum;
        // while (value * signum < destination * signum) {
        // value = Math.nextAfter(value, direction); // Float.POSITIVE_INFINITY * direction
        // leaps++;
        // }

        if (0 == signum) {
            return 0;
        }
        if (0 < signum) {
            while (value < destination) {
                value = Math.nextAfter(value, Float.POSITIVE_INFINITY);
                leaps++;
            }
        } else {
            while (value > destination) {
                value = Math.nextAfter(value, Float.NEGATIVE_INFINITY);
                leaps++;
            }
        }
        return leaps;
    }

    // optimiaze to reduce the elapsed time by roughly half
}

Answer 2

Underlying IEEE 754 floating point model has this property: if you re-interpret the bits as Integer, taking the next float after (or before depending on the direction) is just like taking the next (or previous) integer, that is adding or subtracting 1 to the bit pattern re-interpreted as integer.

Stepping n times is adding (or subtracting) n to the bit pattern. It's as simple as that as long as the sign does not change, and you don't overflow to NaN or Inf.

And the number of different floats between two floats is the difference of two integers if the signs agree.

If signs differ, since the float has a sign-magnitude like representation, which does not fit the integer representation, you'll then have to exert a bit of arithmetic.

Answer 3

To start, I just want to say I don't like hacking into an Objects implementation, and you should using your own (or another library) implementation first, but sometimes you have to get creative.

Lets start with key detail here, what you call the "Leap" (I would call rounding error), So What/Why is there rounding error? Floats (and Doubles) are stored as Integer X Base_Integer^exponent_Integer. (IEEE Standard) So using base 10, If you have 1.2340 X 10^3 (or 1,234.0) your "Leap" will be 0.1 since that is the size of your least significant digit (In storage, the . is implied).

(And I'm out, too much black magic here for me)