Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Fast Math  (Read 5411 times)
0 Members and 1 Guest are viewing this topic.
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« 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;

/**
 * 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.

Offline Abuse

JGO Knight


Medals: 13


falling into the abyss of reality


« 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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« 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!
Legends of Yore - The Casual Retro Roguelike
Online pjt33
« Reply #3 - Posted 2009-10-23 07:03:55 »

If you're really worried, xor the result with Thread.currentThread().hashCode() Wink
Offline 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).
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 818
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 818
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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];
}

Offline CommanderKeith
« Reply #9 - Posted 2009-11-03 13:35:32 »

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


 Cool

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 818
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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.
Offline 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 Tongue I should have thought twice when I noticed that he didn't post his benchmark code.

Offline Mr. Gol

Senior Duke


Medals: 1



« Reply #13 - Posted 2009-11-03 16:23:19 »

1  
static public final float PI = 3.1415926535897932384626433832795028841971f;


A float can't hold that precision.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (38 views)
2014-10-17 03:59:02

Norakomi (28 views)
2014-10-16 15:22:06

Norakomi (24 views)
2014-10-16 15:20:20

lcass (28 views)
2014-10-15 16:18:58

TehJavaDev (55 views)
2014-10-14 00:39:48

TehJavaDev (55 views)
2014-10-14 00:35:47

TehJavaDev (44 views)
2014-10-14 00:32:37

BurntPizza (64 views)
2014-10-11 23:24:42

BurntPizza (36 views)
2014-10-11 23:10:45

BurntPizza (78 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!