Nate
|
 |
«
Posted
2009-09-01 19:16:19 » |
|
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;
public class MathUtil { static public final float PI = 3.1415926535897932384626433832795028841971f;
static private final int SIN_BITS = 12; 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; 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; }
static public float atan2_fast (float y, float x) { 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); } }
static public int multiply (int x, int y) { return (int)((long)x * (long)y >> 16); }
static public int divide (int x, int y) { return (int)((((long)x) << 16) / y); }
static private int randomSeed = (int)System.currentTimeMillis();
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
|
 |
«
Reply #1 - Posted
2009-10-23 00:05:09 » |
|
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
|
 |
«
Reply #2 - Posted
2009-10-23 02:27:33 » |
|
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
|
 |
«
Reply #3 - Posted
2009-10-23 07:03:55 » |
|
If you're really worried, xor the result with Thread.currentThread().hashCode() 
|
|
|
|
Roquen
|
 |
«
Reply #4 - Posted
2009-10-23 08:58:15 » |
|
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
|
 |
«
Reply #5 - Posted
2009-10-23 09:27:23 » |
|
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?
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
Roquen
|
 |
«
Reply #6 - Posted
2009-10-23 09:41:38 » |
|
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
|
 |
«
Reply #7 - Posted
2009-10-23 09:50:56 » |
|
Adjust:
static private final int SIN_BITS = 12; // Adjust for accuracy.
if you really want to reduce memory usage.
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
Roquen
|
 |
«
Reply #8 - Posted
2009-10-23 11:53:13 » |
|
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]; } |
|
|
|
|
|
Games published by our own members! Check 'em out!
|
|
Riven
|
 |
«
Reply #10 - Posted
2009-11-03 14:02:35 » |
|
Pssst, your values are under the wrong columns
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
Roquen
|
 |
«
Reply #11 - Posted
2009-11-03 14:45:44 » |
|
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
|
 |
«
Reply #12 - Posted
2009-11-03 15:42:45 » |
|
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
|
 |
«
Reply #13 - Posted
2009-11-03 16:23:19 » |
|
1
| static public final float PI = 3.1415926535897932384626433832795028841971f; |
A float can't hold that precision.
|
|
|
|
|