Fast Math

[Nate]

Here is my class for some fast math. Some of it was discussed here.

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158   159   160   161   162   163   164   165   166   167   168   169   170   171   172

import java.lang.reflect.Method; /**  * Utility and fast math functions.  *  * Thanks to:<br>  * Riven on JavaGaming.org for sin/cos/atan2 tables.<br>  * Roquen on JavaGaming.org for random numbers.<br>  * pjt33 on JavaGaming.org for fixed point.<br>  * Jim Shima for atan2_fast.<br>  */ public class MathUtil {    static public final float PI = 3.1415926535897932384626433832795028841971f;    static private final int SIN_BITS = 12; // Adjust for accuracy.    static private final int SIN_MASK = ~(-1 << SIN_BITS);    static private final int SIN_COUNT = SIN_MASK + 1;    static private final float radFull = PI * 2;    static private final float degFull = 360;    static private final float radToIndex = SIN_COUNT / radFull;    static private final float degToIndex = SIN_COUNT / degFull;    static public final float[] sin = new float[SIN_COUNT];    static public final float[] cos = new float[SIN_COUNT];    static {       for (int i = 0; i < SIN_COUNT; i++) {          float a = (i + 0.5f) / SIN_COUNT * radFull;          sin[i] = (float)Math.sin(a);          cos[i] = (float)Math.cos(a);       }    }    static public final float sin (float rad) {       return sin[(int)(rad * radToIndex) & SIN_MASK];    }    static public final float cos (float rad) {       return cos[(int)(rad * radToIndex) & SIN_MASK];    }    static public final float sin (int deg) {       return sin[(int)(deg * degToIndex) & SIN_MASK];    }    static public final float cos (int deg) {       return cos[(int)(deg * degToIndex) & SIN_MASK];    }    private static final int ATAN2_BITS = 7; // Adjust for accuracy.    private static final int ATAN2_BITS2 = ATAN2_BITS << 1;    private static final int ATAN2_MASK = ~(-1 << ATAN2_BITS2);    private static final int ATAN2_COUNT = ATAN2_MASK + 1;    private static final int ATAN2_DIM = (int)Math.sqrt(ATAN2_COUNT);    private static final float INV_ATAN2_DIM_MINUS_1 = 1.0f / (ATAN2_DIM - 1);    private static final float[] atan2 = new float[ATAN2_COUNT];    static {       for (int i = 0; i < ATAN2_DIM; i++) {          for (int j = 0; j < ATAN2_DIM; j++) {             float x0 = (float)i / ATAN2_DIM;             float y0 = (float)j / ATAN2_DIM;             atan2[j * ATAN2_DIM + i] = (float)Math.atan2(y0, x0);          }       }    }    public static final float atan2 (float y, float x) {       float add, mul;       if (x < 0) {          if (y < 0) {             y = -y;             mul = 1;          } else             mul = -1;          x = -x;          add = -3.141592653f;       } else {          if (y < 0) {             y = -y;             mul = -1;          } else             mul = 1;          add = 0;       }       float invDiv = 1 / (((x < y) ? y : x) * INV_ATAN2_DIM_MINUS_1);       int xi = (int)(x * invDiv);       int yi = (int)(y * invDiv);       return (atan2[yi * ATAN2_DIM + xi] + add) * mul;    }    /**     * This is a very fast atan2, but not very accurate.     */    static public float atan2_fast (float y, float x) {       // From: http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm       float abs_y = y < 0 ? -y : y;       float angle;       if (x >= 0)          angle = 0.7853981633974483f - 0.7853981633974483f * (x - abs_y) / (x + abs_y);       else          angle = 2.356194490192345f - 0.7853981633974483f * (x + abs_y) / (abs_y - x);       return y < 0 ? -angle : angle;    }    static private Method sqrtMethod;    static {       try {          sqrtMethod = Class.forName("android.util.FloatMath").getMethod("sqrt", new Class[] {float.class});       } catch (Exception ex) {          try {             sqrtMethod = Class.forName("java.lang.Math").getMethod("sqrt", new Class[] {double.class});          } catch (Exception ignored) {          }       }    }    static public final float sqrt (float value) {       try {          return ((Number)sqrtMethod.invoke(null, value)).floatValue();       } catch (Exception ex) {          throw new RuntimeException(ex);       }    }    /**     * Fixed point multiply.     */    static public int multiply (int x, int y) {       return (int)((long)x * (long)y >> 16);    }    /**     * Fixed point divide.     */    static public int divide (int x, int y) {       return (int)((((long)x) << 16) / y);    }    static private int randomSeed = (int)System.currentTimeMillis();    /**     * Returns a random number between 0 (inclusive) and the specified value (inclusive).     * @param range Must be >= 0.     */    static public final int random (int range) {       int seed = randomSeed * 1103515245 + 12345;       randomSeed = seed;       return ((seed >>> 15) * (range + 1)) >>> 17;    }    static public final int random (int start, int end) {       int seed = randomSeed * 1103515245 + 12345;       randomSeed = seed;       return (((seed >>> 15) * ((end - start) + 1)) >>> 17) + start;    }    static public final boolean randomBoolean () {       int seed = randomSeed * 1103515245 + 12345;       randomSeed = seed;       return seed > 0;    }    static public final float random () {       int seed = randomSeed * 1103515245 + 12345;       randomSeed = seed;       return (seed >>> 8) * (1f / (1 << 24));    }    static public int nextPowerOfTwo (int value) {       return 1 << (32 - Integer.numberOfLeadingZeros(value - 1));    } }

Couple notes:

• For sqrt use FloatMath.sqrt, it is fast. The sqrt method here will call FloatMath.sqrt on Android and Math.sqrt on the desktop.
• Don't bother with fixed point, for the most part float is faster. Usually you only need fixed point for Open GL ES, and in that case the multiple and divide methods can be useful. You can add and subtract fixed point numbers the normal way.

[Abuse]

Worth noting none of those random number methods are thread safe.
Not a bad thing so long as it's documented - though opting for a static utility class compounds the problem, as the application programmer cannot avoid the limitation by using a different instance in each thread.

[Nate]

Good point. When it does occur, it just means both threads get the same "random" value. I prefer putting up with this flaw to keep the methods static. You're right, it should be documented.

Games published by our own members! Check 'em out!

[pjt33]

If you're really worried, xor the result with Thread.currentThread().hashCode()

[Roquen]

WRT: The RNG and multiple threads. 

The worst case scenario is a variant of the following:  Thread 1 reads the seed and is interrupted by Thread 2.  Thread 2 reads the seed and is interrupted by Thread 3.  Thread 1 comes back to life and generates some random numbers.  Thread 2 wakes up and effectively moves the position in sequence to one past where we were at the beginning. Something to worry about? Not really. The window of opportunity is very narrow (about 5 opcodes) and must happen a couple of times in concert. The work being performed on Thread 1 must be something where this backward jump in the sequence would be possibly noticable.  I'm more worry about a duck with a piece of tinsel in its bill landing on my head under a clear blue sky and then getting struck by lightning. Possible? Sure, but I'm not losing any sleep over it.

I'd add the core 32-bit generator as well for ranges of 0 to (2^n)-1.  Trade two shifts, a multiply and add of the ranged version for a single shift.

WRT: Sin/Cos. You could collapse the two tables into 1 at the cost of making one of functions slightly more expense (a constant add).

[Riven]

WRT: Sin/Cos. You could collapse the two tables into 1 at the cost of making one of functions slightly more expense (a constant add).

So you're suggesting to make my FastMath code a tad slower?

[Roquen]

I've gotten the impression that many people are running to memory limitiation issues with their apps.  So sure it's only a few K of savings, but if your at the wall...you gotta trim.  Choosing to make one of the them slower is an option.  It's nice to consider before hand so that you can favor one over the other when the choice doesn't matter.

[Riven]

Adjust:

   static private final int SIN_BITS = 12; // Adjust for accuracy.

if you really want to reduce memory usage.

[Roquen]

Sure.  You can lower the value by one and cut your memory usage in half.  Your suggestion doubles the max error, mine increases the runtime cost of one of the functions.  Of these two choices, the "best" option is game specific.

It might be worth checking if something like the following is faster on Android when you do need both:

1   2   3   4   5   6   7

static void sincos(FloatPair r, Float rad) {   int id = (int)(rad * radToIndex);   r.a = sin[id & SIN_MASK];   r.b = sin[(id + COS_OFF) & SIN_MASK]; }

[CommanderKeith]

I was browsing through this thread and the other one (http://www.java-gaming.org/topics/arithmictic-performance/20972/view.html) to find out how expensive Math.sqrt is compared to a normal plus/multiply/divide operation and couldn't find a benchmark but there's a good article here for anyone interested:

http://metafessional.com/blog/software-development/java-math-performance.html

1   2   3   4   5   6   7   8   9   10   11   12   13

clientVM   +   -   *   /   sqrt   sin   cos integer   16   16   15   26 long   30   30   30   120 float   15   15   16   30 double   29   26   27   52   242   4205   4205 fixed   13   12   40   191   427   60   59 serverVM   +   -   *   /   sqrt   sin   cos integer   21   115   14   21 long   24   25   25   106 float   12   12   12   29 double   24   24   25   54   87   3317   3260 fixed   14   13   32   189   314   57   64

 

Games published by our own members! Check 'em out!

[Riven]

_{Pssst, your values are under the wrong columns}

[Roquen]

This table looks very questionable.  Fixed point +/- faster than integer? When it's the same op?  And the integer subtract on the serverVM?  The sampling method must have been flawed.

[CommanderKeith]

Hmm, yeah those numbers do look a bit suspect.

Sorry for quoting a dodgy reference I should have thought twice when I noticed that he didn't post his benchmark code.

[Mr. Gol]

1	static public final float PI = 3.1415926535897932384626433832795028841971f;

A float can't hold that precision.