User:Rednaxela/FastTrig
Jump to navigation
Jump to search
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)
FastTrig re-create
package wiki;
import static java.lang.Math.abs;
import java.io.PrintStream;
/**
* FastMath - a faster replacement to Trig
*
* Run command:
* java -Xmx1G wiki.FastMath
*
* @author Rednaxela
* @author Skilgannon
* @author Starrynte
* @author Nat
*/
public final class FastMath {
public static final double PI = 3.1415926535897932384626433832795D;
public static final double TWO_PI = 6.2831853071795864769252867665590D;
public static final double HALF_PI = 1.5707963267948966192313216916398D;
public static final double QUARTER_PI = 0.7853981633974483096156608458199D;
public static final double THREE_OVER_TWO_PI
= 4.7123889803846898576939650749193D;
private static final int TRIG_DIVISIONS = 8192;//MUST be power of 2!!!
private static final int TRIG_HIGH_DIVISIONS = 131072;//MUST be power of 2!!!
private static final double K = TRIG_DIVISIONS / TWO_PI;
private static final double ACOS_K = (TRIG_HIGH_DIVISIONS - 1)/ 2;
private static final double TAN_K = TRIG_HIGH_DIVISIONS / PI;
private static final double[] sineTable = new double[TRIG_DIVISIONS];
private static final double[] tanTable = new double[TRIG_HIGH_DIVISIONS];
private static final double[] acosTable = new double[TRIG_HIGH_DIVISIONS];
public static final void init() {
for (int i = 0; i < TRIG_DIVISIONS; i++) {
sineTable[i] = Math.sin(i/K);
}
for(int i = 0; i < TRIG_HIGH_DIVISIONS; i++){
tanTable[i] = Math.tan(i/TAN_K);
acosTable[i] = Math.acos(i / ACOS_K - 1);
}
}
public static final double sin(double value) {
return sineTable[(int)(((value * K + 0.5) % TRIG_DIVISIONS + TRIG_DIVISIONS) )&(TRIG_DIVISIONS - 1)];
}
public static final double cos(double value) {
return sineTable[(int)(((value * K + 0.5) % TRIG_DIVISIONS + 1.25 * TRIG_DIVISIONS) )&(TRIG_DIVISIONS - 1)];
}
public static final double tan(double value) {
return tanTable[(int)(((value * TAN_K + 0.5) % TRIG_HIGH_DIVISIONS + TRIG_HIGH_DIVISIONS) )&(TRIG_HIGH_DIVISIONS - 1)];
}
public static final double asin(double value) {
//return atan(x / Math.sqrt(1 - x*x));
return HALF_PI - acos(value);
}
public static final double acos(double value) {
return acosTable[(int)(value*ACOS_K + (ACOS_K + 0.5))];
}
public static final double atan(double value) {
return (value >= 0 ? acos(1 / sqrt(value * value + 1)) : -acos(1 / sqrt(value * value + 1)));
}
public static final double atan2(double x, double y) {
return (x >= 0 ? acos(y / sqrt(x*x + y*y)) : -acos(y / sqrt(x*x + y*y)));
}
public static final double sqrt(double x){
return Math.sqrt(x);
//return x * (1.5d - 0.5*x* (x = Double.longBitsToDouble(0x5fe6ec85e7de30daL - (Double.doubleToLongBits(x)>>1) )) *x) * x;
}
public static void main(String args[]) {
double[] angletest, arctest, atantest, tantest;
double[][] atan2test;
double[] expect, current;
PrintStream o = System.out;
final int NUM = 10000000;
long ms;
double error;
angletest = new double[NUM];
tantest = new double[NUM];
arctest = new double[NUM];
atantest = new double[NUM];
atan2test = new double[NUM][2];
System.out.println("Initializing FastMath...");
for (int i = 0; i < NUM; i++) {
// angletest[i] = (Math.random() + 1d) + i * Math.PI - Math.PI / 3d;
angletest[i] = Math.random() * (PI * 3) - PI;
tantest[i] = Math.random() * PI - HALF_PI;
arctest[i] = Math.random() * 2d - 1d;
atantest[i] = Math.random() * 16000d - 8000d;
atan2test[i][0] = Math.random() * 10000d - 5000d;
atan2test[i][1] = Math.random() * 10000d - 5000d;
}
ms = -System.nanoTime();
FastMath.init();
ms += System.nanoTime();
o.printf("FastMath init time: %.5f seconds\n", ms / 1E9);
o.println();
// ---------------------------------------
o.println("== Sine Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.sin
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.sin(angletest[i]);
}
ms += System.nanoTime();
o.printf("Math.sin() time: %.5f seconds\n", ms / 1E9);
// FastMath.sin
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.sin(angletest[i]);
}
ms += System.nanoTime();
o.printf("FastMath.sin() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.sin() worst error: %.5f\n", error);
// ---------------------------------------
o.println("== Cosine Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.cos
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.cos(angletest[i]);
}
ms += System.nanoTime();
o.printf("Math.cos() time: %.5f seconds\n", ms / 1E9);
// FastMath.cos
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.cos(angletest[i]);
}
ms += System.nanoTime();
o.printf("FastMath.cos() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.cos() worst error: %.5f\n", error);
// ---------------------------------------
o.println("== Tangent Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.tan
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.tan(tantest[i]);
}
ms += System.nanoTime();
o.printf("Math.tan() time: %.5f seconds\n", ms / 1E9);
// FastMath.tan
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.tan(tantest[i]);
}
ms += System.nanoTime();
o.printf("FastMath.tan() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.tan() max error: %.5f\n", error);
// ---------------------------------------
o.println("== Arcsine Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.asin
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.asin(arctest[i]);
}
ms += System.nanoTime();
o.printf("Math.asin() time: %.5f seconds\n", ms / 1E9);
// FastMath.asin
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.asin(arctest[i]);
}
ms += System.nanoTime();
o.printf("FastMath.asin() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.asin() worst error: %.5f\n", error);
// ---------------------------------------
o.println("== Arccosine Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.acos
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.acos(arctest[i]);
}
ms += System.nanoTime();
o.printf("Math.asin() time: %.5f seconds\n", ms / 1E9);
// FastMath.acos
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.acos(arctest[i]);
}
ms += System.nanoTime();
o.printf("FastMath.acos() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.acos() worst error: %.5f\n", error);
// ---------------------------------------
o.println("== Arctangent Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.atan
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.atan(atantest[i]);
}
ms += System.nanoTime();
o.printf("Math.atan() time: %.5f seconds\n", ms / 1E9);
// FastMath.atan
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.atan(atantest[i]);
}
ms += System.nanoTime();
o.printf("FastMath.atan() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.atan() worst error: %.5f\n", error);
// ---------------------------------------
o.println("== Arctangent2 Test ==");
expect = new double[NUM];
current = new double[NUM];
error = 0;
// Math.atan2
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
expect[i] = Math.atan2(atan2test[i][0], atan2test[i][1]);
}
ms += System.nanoTime();
o.printf("Math.atan2() time: %.5f seconds\n", ms / 1E9);
// FastMath.atan2
ms = -System.nanoTime();
for (int i = 0; i < NUM; i++) {
current[i] = FastMath.atan2(atan2test[i][0], atan2test[i][1]);
}
ms += System.nanoTime();
o.printf("FastMath.atan2() time: %.5f seconds\n", ms / 1E9);
for (int i = 0; i < NUM; i++) {
error = Math.max(error, abs(expect[i] - current[i]));
}
o.printf("FastMath.atan2() worst error: %.5f\n", error);
}
}
Result:
Initializing FastMath... FastMath init time: 0.12839 seconds == Sine Test == Math.sin() time: 1.48196 seconds FastMath.sin() time: 0.27152 seconds FastMath.sin() worst error: 0.00038 == Cosine Test == Math.cos() time: 1.38444 seconds FastMath.cos() time: 0.26755 seconds FastMath.cos() worst error: 0.00038 == Tangent Test == Math.tan() time: 1.90291 seconds FastMath.tan() time: 0.27914 seconds FastMath.tan() max error: 40440.39341 /* Note: The nearer to PI the value are, the more error they will raise */ == Arcsine Test == Math.asin() time: 9.08303 seconds FastMath.asin() time: 0.13469 seconds FastMath.asin() worst error: 0.00390 == Arccosine Test == Math.asin() time: 8.72265 seconds FastMath.acos() time: 0.11361 seconds FastMath.acos() worst error: 0.00390 == Arctangent Test == Math.atan() time: 2.98640 seconds FastMath.atan() time: 0.52767 seconds FastMath.atan() worst error: 0.00376 == Arctangent2 Test == Math.atan2() time: 4.10049 seconds FastMath.atan2() time: 0.71804 seconds FastMath.atan2() worst error: 0.00391
