Advertisement

Lerp vs fastLerp

Started by November 27, 2015 09:09 AM
10 comments, last by alvaro 9 years, 2 months ago

We all know what lerps does and how it works - but there are two ways to implement lerps:

lerp = a * (1 - t) + b * t (2 multiplys, one substraction, one addition)

fastLerp = a + (b - a) * t (one multiply, one substraction, one addition)

In practice, i have never seen any differences between the both.

If i write unit tests for - both have the same result for the same combinations:


        // lerp
        assert.strictEqual(math.lerp(0, 100, -1), -100, "lerp for 0 / 100 / -1.0");
        assert.strictEqual(math.lerp(0, 100, -0.75), -75, "lerp for 0 / 100 / -0.75");
        assert.strictEqual(math.lerp(0, 100, -0.5), -50, "lerp for 0 / 100 / -0.50");
        assert.strictEqual(math.lerp(0, 100, -0.25), -25, "lerp for 0 / 100 / -0.25");
        assert.strictEqual(math.lerp(0, 100, 0), 0, "lerp for 0 / 100 / 0.0");
        assert.strictEqual(math.lerp(0, 100, 0.25), 25, "lerp for 0 / 100 / 0.25");
        assert.strictEqual(math.lerp(0, 100, 0.5), 50, "lerp for 0 / 100 / 0.5");
        assert.strictEqual(math.lerp(0, 100, 0.75), 75, "lerp for 0 / 100 / 0.75");
        assert.strictEqual(math.lerp(0, 100, 1), 100, "lerp for 0 / 100 / 1.0");
        assert.strictEqual(math.lerp(100, 0,  -1), 200, "lerp for 100 / 0 / -1.0");
        assert.strictEqual(math.lerp(100, 0, -0.75), 175, "lerp for 100 / 0 / -0.75");
        assert.strictEqual(math.lerp(100, 0, -0.5), 150, "lerp for 100 / 0 / -0.5");
        assert.strictEqual(math.lerp(100, 0, -0.25), 125, "lerp for 100 / 0 / -0.25");
        assert.strictEqual(math.lerp(100, 0, 0), 100, "lerp for 100 / 0 / 0.0");
        assert.strictEqual(math.lerp(100, 0, 0.25), 75, "lerp for 100 / 0 / 0.25");
        assert.strictEqual(math.lerp(100, 0, 0.5), 50, "lerp for 100 / 0 / 0.5");
        assert.strictEqual(math.lerp(100, 0, 0.75), 25, "lerp for 100 / 0 / 0.75");
        assert.strictEqual(math.lerp(100, 0,  1), 0, "lerp for 100 / 0 / 1.0");

        // lerpFast
        assert.strictEqual(math.lerpFast(0, 100, -1), -100, "lerpFast for 0 / 100 / -1.0");
        assert.strictEqual(math.lerpFast(0, 100, -0.75), -75, "lerpFast for 0 / 100 / -0.75");
        assert.strictEqual(math.lerpFast(0, 100, -0.5), -50, "lerpFast for 0 / 100 / -0.50");
        assert.strictEqual(math.lerpFast(0, 100, -0.25), -25, "lerpFast for 0 / 100 / -0.25");
        assert.strictEqual(math.lerpFast(0, 100, 0), 0, "lerpFast for 0 / 100 / 0.0");
        assert.strictEqual(math.lerpFast(0, 100, 0.25), 25, "lerpFast for 0 / 100 / 0.25");
        assert.strictEqual(math.lerpFast(0, 100, 0.5), 50, "lerpFast for 0 / 100 / 0.5");
        assert.strictEqual(math.lerpFast(0, 100, 0.75), 75, "lerpFast for 0 / 100 / 0.75");
        assert.strictEqual(math.lerpFast(0, 100, 1), 100, "lerpFast for 0 / 100 / 1.0");
        assert.strictEqual(math.lerpFast(100, 0,  -1), 200, "lerpFast for 100 / 0 / -1.0");
        assert.strictEqual(math.lerpFast(100, 0, -0.75), 175, "lerpFast for 100 / 0 / -0.75");
        assert.strictEqual(math.lerpFast(100, 0, -0.5), 150, "lerpFast for 100 / 0 / -0.5");
        assert.strictEqual(math.lerpFast(100, 0, -0.25), 125, "lerpFast for 100 / 0 / -0.25");
        assert.strictEqual(math.lerpFast(100, 0, 0), 100, "lerpFast for 100 / 0 / 0.0");
        assert.strictEqual(math.lerpFast(100, 0, 0.25), 75, "lerpFast for 100 / 0 / 0.25");
        assert.strictEqual(math.lerpFast(100, 0, 0.5), 50, "lerpFast for 100 / 0 / 0.5");
        assert.strictEqual(math.lerpFast(100, 0, 0.75), 25, "lerpFast for 100 / 0 / 0.75");
        assert.strictEqual(math.lerpFast(100, 0,  1), 0, "lerpFast for 100 / 0 / 1.0");

Which one is better?

Thanks in advance

They are exactly the same thing, just different forms to write it.

http://www.wolframalpha.com/input/?i=a+*+%281+-+t%29+%2B+b+*+t+

For numerical calculation in a CPU, the second form should be better for two reasons, less numerical error (probably not noticeable in normal use) and faster execution.

Edit: Continue reading for more accurate answers ;)

Advertisement

They are exactly the same thing, just different forms to write it.

http://www.wolframalpha.com/input/?i=a+*+%281+-+t%29+%2B+b+*+t+

For numerical calculation in a CPU, the second form should be better for two reasons, less numerical error (probably not noticeable in normal use) and faster execution.

Thats the point - when does the first form produces a different result than the second form? I never had any issues using the simpler form for all my math stuff (physics engine, data visualizations, games, enterprise-applications).


when does the first form produces a different result than the second form?

Never.

They are equivalent.

a * (1 - t) + bt //Multiply a into (1 - t)
= a - at + bt //Rearrange to see the end result better...
= a + bt - at //Take the common term 't' and put it outside the expression
= a + (b - a) * t

Hello to all my stalkers.


when does the first form produces a different result than the second form?

Never.

They are equivalent.


a * (1 - t) + bt //Multiply a into (1 - t)
= a - at + bt //Rearrange to see the end result better...
= a + bt - at //Take the common term 't' and put it outside the expression
= a + (b - a) * t

I think OP is aware of that, he is probably asking regarding floating-point. The two expressions are not equivalent in general, for instance if a = +infinity, b = 0, t = 0, then one of them evaluates to +infinity while the other one evaluates to NaN. I'm sure you can also come up with all sorts of fun examples that the two expressions aren't equivalent using catastrophic cancellation, denormal numbers, or other such IEEE 754 goodies cool.png

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

less numerical error

Depends on the case. With the fast version, lerp(a,b,1) may not return b. Multiplication by 0/1 are generally not lossy operations, addition and subtraction of non-zero numbers can easily be lossy.

So, fast lerp works fine almost everywhere but if you absolutely need lerp(a,b,1) to return b, use the slightly longer version.

Advertisement


when does the first form produces a different result than the second form?

Never.

They are equivalent.


a * (1 - t) + bt //Multiply a into (1 - t)
= a - at + bt //Rearrange to see the end result better...
= a + bt - at //Take the common term 't' and put it outside the expression
= a + (b - a) * t

I think OP is aware of that, he is probably asking regarding floating-point. The two expressions are not equivalent in general, for instance if a = +infinity, b = 0, t = 0, then one of them evaluates to +infinity while the other one evaluates to NaN. I'm sure you can also come up with all sorts of fun examples that the two expressions aren't equivalent using catastrophic cancellation, denormal numbers, or other such IEEE 754 goodies cool.png

Fair points :)

Hello to all my stalkers.

Ironically, fastLerp may very well be none faster, and even slower than the non-fast version, depending on how long instructions take and depending on the CPU's OOE capabilities. The non-fast version has a more favourable dependency chain. A modern CPU can possibly execute (b*t) in parallel, that is "for free", while it executes (1-t)*a, and it only need to do one addition thereafter. So basically it's a multiply followed by an add, give or take a cycle for decoding the out-of-order instruction. The fast version must first execute (b - a), followed by a dependent multiplication, and finally a dependent addition. Which sums up to a multiplication and two add/sub instructions, give or take a cycle. Unless addition is a single-cycle operation, this should be slower. Would be interesting to benchmark that. Also, would be interesting whether a modern compiler is smart enough to recognize the pattern and choose the fastest version in either case...

lerp = a * (1 - t) + b * t
fastLerp = a + (b - a) * t

in terms of precision lerp = a * (1 - t) + b * t becase there are less add/substr operations(and they *could* break the fp precision).

EDIT :
*Less* between 'a' and 'b'.??

At small scales, given constant values X and Y and variable v<=0<=1, FastLerp(X,Y,v) is smoother than Lerp(X,Y,v).

Here's some test code that shows the effect. I print out the hex value of the floats to show it more clearly. Also, note the explicit single-float-operation-per-line coding style - combined with compiler flags to limit floating point optimisation, it means this is the code that gets executed. Without this, my compiler generates code equivalent to FastLerp in both cases.


float Lerp(float x, float y, float v)
{
//	return x * (1 - v) + y * v;
	float oneMinusV = 1 - v;
	float xOneMinusV = x * oneMinusV;
	float yV = y * v;
	float xOneMinusVPlusYV = xOneMinusV + yV;
	return xOneMinusVPlusYV;
}

float FastLerp(float x, float y, float v)
{
//	return x + (y - x) * v;
	float yMinusX = y - x;
	float yMinusXV = yMinusX * v;
	float xPlusYMinusXV = x + yMinusXV;
	return xPlusYMinusXV;
}

void Test(void)
{
	int i;
	float x = 0.9999988079f;
	float y = 1.0000000000f;
	float delta = 0.0078125f;
	int numIterations = 32;
	printf("%8x\n", Types::IntFromFloat(x));
	printf("%8x\n", Types::IntFromFloat(y));
	printf("%8x\n", Types::IntFromFloat(delta));
	printf("\n");
	float v = 0.0f;
	printf("v = %f\n", v);
	for (i=0; i<numIterations; i++)
	{	float f1 = Lerp(x, y, v);
		float f2 = FastLerp(x, y, v);
		printf("%8x\t%8x\n", Types::IntFromFloat(f1), Types::IntFromFloat(f2));
		v += delta;
	}
	printf("\n");
	v = 0.5f;
	printf("v = %f\n", v);
	for (i=0; i<numIterations; i++)
	{	float f1 = Lerp(x, y, v);
		float f2 = FastLerp(x, y, v);
		printf("%8x\t%8x\n", Types::IntFromFloat(f1), Types::IntFromFloat(f2));
		v += delta;
	}
}
Output:


3f7fffec
3f800000
3c000000

v = 0.000000
3f7fffec        3f7fffec
3f7fffec        3f7fffec
3f7fffec        3f7fffec
3f7fffec        3f7fffec
3f7fffed        3f7fffed
3f7fffed        3f7fffed
3f7fffed        3f7fffed
3f7fffed        3f7fffed
3f7fffed        3f7fffed
3f7fffed        3f7fffed
3f7fffee        3f7fffee
3f7fffee        3f7fffee
3f7fffee        3f7fffee
3f7fffee        3f7fffee
3f7fffee        3f7fffee
3f7fffee        3f7fffee
3f7fffee        3f7fffee
3f7fffef        3f7fffef
3f7fffef        3f7fffef
3f7fffef        3f7fffef
3f7fffef        3f7fffef
3f7fffef        3f7fffef
3f7fffef        3f7fffef
3f7ffff0        3f7ffff0
3f7ffff0        3f7ffff0
3f7ffff0        3f7ffff0
3f7ffff0        3f7ffff0
3f7ffff0        3f7ffff0
3f7ffff0        3f7ffff0
3f7ffff1        3f7ffff1
3f7ffff1        3f7ffff1
3f7ffff1        3f7ffff1

v = 0.500000
3f7ffff6        3f7ffff6
3f7ffff6        3f7ffff6
3f7ffff6        3f7ffff6
3f7ffff6        3f7ffff6
3f7ffff6        3f7ffff7
3f7ffff7        3f7ffff7
3f7ffff7        3f7ffff7
3f7ffff7        3f7ffff7
3f7ffff7        3f7ffff7
3f7ffff8        3f7ffff7
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff8
3f7ffff8        3f7ffff9
3f7ffff9        3f7ffff9
3f7ffff9        3f7ffff9
3f7ffff9        3f7ffff9
3f7ffffa        3f7ffff9
3f7ffffa        3f7ffff9
3f7ffffa        3f7ffffa
3f7ffffa        3f7ffffa
3f7ffffa        3f7ffffa
3f7ffffa        3f7ffffa
3f7ffffa        3f7ffffa
3f7ffffa        3f7ffffa
3f7ffffa        3f7ffffb
3f7ffffa        3f7ffffb
3f7ffffb        3f7ffffb
Look at the values around 3f7ffff9.

This topic is closed to new replies.

Advertisement