User:Rednaxela/FastTrig

A little class for fast trig lookups. Tests show that:

• When used with the sin/cos static methods, it ranges from twice as slow, to three times as fast, depending on how much of a chance the JIT has to optimize
• When you inline the index-calculation code into your own code (see usage in the main method) instead of using static methods, it ranges from just slightly faster, up to three times as fast.
• Increasing the number of divisions has no impact on runtime performance, only initialization time and memory consumption.

This could provide some measurable speedup to intensive play-it-forward guns or precise prediction in surfers. Cheers!

package ags.util;

public class FastTrig {
	public static final int DIVISIONS = 7200;
	public static final double K = DIVISIONS/(Math.PI*2);
	public static final double[] sineTable = new double[DIVISIONS];

	public static final void init() {
		for (int i=0; i<DIVISIONS; i++) {
			double value = i/K;
			sineTable[i] = Math.sin(value);
		}
	}
	
	public static final double sin(double value) {
		return sineTable[(int)(((value*K + 0.5) % DIVISIONS + DIVISIONS)%DIVISIONS)];
	}
	
	public static final double cos(double value) {
		return sineTable[(int)(((value*K + 0.5) % DIVISIONS + 1.25*DIVISIONS)%DIVISIONS)];
	}
	
	public static void main(String[] args) {
		double v=0;
		long ms;

		ms = -System.nanoTime();
		FastTrig.init();
		ms += System.nanoTime();
		System.out.printf("FastTrig init time: %.5f seconds\n", ms / 1E9);

		int A = 10000;
		int B = 1000;
		double absolute = 0;
		for ( int i = 0; i < A; ++i ) for ( int j = 0; j < B; ++j ) {
			double angle = Math.random() * Math.PI * 200 - Math.PI * 100;
			absolute = Math.max(absolute, Math.abs(Math.sin(angle) - FastTrig.sin(angle)));
			absolute = Math.max(absolute, Math.abs(Math.cos(angle) - FastTrig.cos(angle)));
		}
		System.out.printf("Wrost error: %.12f\n", absolute);
		v=0;
		ms = -System.nanoTime();
		for ( int i = 0; i < A; ++i ) for ( int j = 0; j < B; ++j )
			v += FastTrig.sin(i * j * Math.PI - Math.PI / 3);
		ms += System.nanoTime();
		System.out.printf("FastTrig time: %.3f seconds\n", ms / 1E9);
		v = 0;
		ms = -System.nanoTime();
		for ( int i = 0; i < A; ++i ) for ( int j = 0; j < B; ++j )
			v += Math.sin(i * j * Math.PI - Math.PI / 3);
		ms += System.nanoTime();
		System.out.printf("Math time: %.3f seconds\n", ms/1E9);
	}
}

Test output is as follows:

FastTrig init time: 0.00470 seconds
Wrost error: 0.000436329459
FastTrig time: 0.506 seconds
Math time: 8.619 seconds

--Rednaxela 00:34, 4 March 2009 (UTC)