Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (542)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (606)
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  
  Alpha max plus Beta min  (Read 1768 times)
0 Members and 1 Guest are viewing this topic.
Offline StumpyStrust
« Posted 2012-10-25 07:16:51 »

So I do not know if this is useful or not and I really don't know if it is worth anything but I read about it on the nets and decided to take a whack at it and see what happens.

Basically, an algorithm that approximates the sqrt. I have no idea if I am doing this right but here it is

http://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm  Pointing love wiki  Kiss

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
public float fastSqrt(Vector2f vec1)
   {
      float x = vec1.x*vec1.x;
      float y = vec1.y*vec1.y;
      if(x > y)
      {
         x = (x*.960434f)/vec1.x;
         y = (y*.397825f)/vec1.y;
      }
      else
      {
         y = (y*.960434f)/vec1.y;
         x = (x*.397825f)/vec1.x;
      }
      //when dividing your vector could have a negative component so need to check that.
      if(x <0)
         x *= -1;
      if(y <0)
         y *= -1;
      return x+y;
   }


I know this is micro benchmarking which is basically useless but I found no speed improvement against Math.sqrt

I have to be doing something right as the result is only off from Math.sqrt by a little and in my particle prog there is almost no visual difference.

Anyone know something on this? I think it is a cool idea and would like to hear what other, more experienced, people have to say.

Offline theagentd

« JGO Bitwise Duke »


Medals: 367
Projects: 2
Exp: 8 years



« Reply #1 - Posted 2012-10-25 11:49:32 »

Math.sqrt() is almost never your bottleneck, but I still think that it might be useful. For example, it works on floats directly. Casting a double to a float is not free (and pretty slow in my experience). Just one question, exactly what is it calculating? The length of vec1?

Minor performance tip:
x *= -1 is the same as x = -x. I think simply using Math.abs() should be the fastest though.

1  
return Math.abs(x) + Math.abs(y);

Myomyomyo.
Offline DrHalfway
« Reply #2 - Posted 2012-10-25 13:01:09 »

Here is one based on the Carmacks constant

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
   public static final float sqrt(final float num) {
      int i = 0;
      float x2, y;
     
      x2 = num * 0.5f;
      y = num;
      i = Float.floatToIntBits(num);
     
      // carmacks constant
      i = 0x5f3759df - (i >> 1);
      y = Float.intBitsToFloat(i);
     
      // replicate for better accuracy
      y = y * (1.5f - ( x2 * y * y));
      //y = y * (1.5f - ( x2 * y * y));
     
      return y * num;  
   }


Never done benchmarking compared to java's sqrt(), perhaps someone else can take their time and do it  Grin

~DrHalfway

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2012-10-25 13:05:40 »

My opinion is don't bother with software sqrt and 1/sqrt.  They're just too fast these days to goof around with (and very hard to approximate).  Maybe one day we'll have access to the SIMD approximations...sigh.
Offline Roquen
« Reply #4 - Posted 2012-10-25 14:45:10 »

I guess I should explicitly state that if the range is narrow (like say re-normalization) and/or high error is acceptable, then approximations of either is more than approp.
Offline StumpyStrust
« Reply #5 - Posted 2012-10-25 15:47:15 »

Woh read about the Carmacks constant really funny.

Yeah I know that this was not much of a slow down but thought it sounded fun so tried it. I generally try to stay away from the Math class as I have no idea what it does.


Offline Nate

« JGO Bitwise Duke »


Medals: 159
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #6 - Posted 2012-10-25 20:32:23 »

Math.sqrt is fast, even on Android, not worth doing anything else.

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.

Elsealabs (20 views)
2014-12-28 10:39:27

CopyableCougar4 (20 views)
2014-12-28 02:10:29

BurntPizza (25 views)
2014-12-27 22:38:51

Mr.CodeIt (15 views)
2014-12-27 04:03:04

TheDudeFromCI (20 views)
2014-12-27 02:14:49

Mr.CodeIt (26 views)
2014-12-23 03:34:11

rwatson462 (58 views)
2014-12-15 09:26:44

Mr.CodeIt (47 views)
2014-12-14 19:50:38

BurntPizza (98 views)
2014-12-09 22:41:13

BurntPizza (116 views)
2014-12-08 04:46:31
How do I start Java Game Development?
by gouessej
2014-12-27 19:41:21

Resources for WIP games
by kpars
2014-12-18 10:26:14

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
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!