Alpha max plus Beta min

Performance Tuning
#1

So I do not know if this is useful or not and I really don’t know if it is worth anything but I read about it on the nets and decided to take a whack at it and see what happens.

Basically, an algorithm that approximates the sqrt. I have no idea if I am doing this right but here it is

http://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm :point: love wiki :-*

public float fastSqrt(Vector2f vec1)
	{
		float x = vec1.x*vec1.x;
		float y = vec1.y*vec1.y;
		if(x > y)
		{
			x = (x*.960434f)/vec1.x;
			y = (y*.397825f)/vec1.y;
		}
		else
		{
			y = (y*.960434f)/vec1.y;
			x = (x*.397825f)/vec1.x;
		}
		//when dividing your vector could have a negative component so need to check that. 
		if(x <0)
			x *= -1;
		if(y <0)
			y *= -1;
		return x+y;
	}

I know this is micro benchmarking which is basically useless but I found no speed improvement against Math.sqrt

I have to be doing something right as the result is only off from Math.sqrt by a little and in my particle prog there is almost no visual difference.

Anyone know something on this? I think it is a cool idea and would like to hear what other, more experienced, people have to say.

#2

Math.sqrt() is almost never your bottleneck, but I still think that it might be useful. For example, it works on floats directly. Casting a double to a float is not free (and pretty slow in my experience). Just one question, exactly what is it calculating? The length of vec1?

Minor performance tip:
x *= -1 is the same as x = -x. I think simply using Math.abs() should be the fastest though.


return Math.abs(x) + Math.abs(y);
#3

Here is one based on the Carmacks constant



	public static final float sqrt(final float num) {
		int i = 0;
		float x2, y;
		
		x2 = num * 0.5f;
		y = num;
		i = Float.floatToIntBits(num);
		
		// carmacks constant
		i = 0x5f3759df - (i >> 1);
		y = Float.intBitsToFloat(i);
		
		// replicate for better accuracy
		y = y * (1.5f - ( x2 * y * y));
		//y = y * (1.5f - ( x2 * y * y));
		
		return y * num;	
	}

Never done benchmarking compared to java’s sqrt(), perhaps someone else can take their time and do it ;D

~DrHalfway

#4

My opinion is don’t bother with software sqrt and 1/sqrt. They’re just too fast these days to goof around with (and very hard to approximate). Maybe one day we’ll have access to the SIMD approximations…sigh.

#5

I guess I should explicitly state that if the range is narrow (like say re-normalization) and/or high error is acceptable, then approximations of either is more than approp.

#6

Woh read about the Carmacks constant really funny.

Yeah I know that this was not much of a slow down but thought it sounded fun so tried it. I generally try to stay away from the Math class as I have no idea what it does.

#7

Math.sqrt is fast, even on Android, not worth doing anything else.