Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (804)
Games in Android Showcase (237)
games submitted by our members
Games in WIP (867)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2] 3
  ignore  |  Print  
  Extremely Fast sine/cosine  (Read 52794 times)
0 Members and 1 Guest are viewing this topic.
Offline KaiHH

JGO Kernel


Medals: 786



« Reply #30 - Posted 2015-10-03 09:18:58 »

I solved that.
Ahh sorry, @theagentd. I somewhat overlooked that +1 in the array allocation.
But regarding @Roquen's comment, can you probably give a vague percentage of how much faster the table-based lookup is compared to other methods in WSW maybe?
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #31 - Posted 2015-10-03 10:26:40 »

Now I can really reduce the bit depth of the lookup table to 6 bits and still have ten times the accuracy of the non-interpolating algorithm.
At such few discrete values (2^6=64, 360/64=5.6deg per value) you start to need to renormalize your interpolated values... I'd say that you'd at least use 8 bits, for game purposes.


cos(0.0deg) = 1.0
sin(0.0deg) = 0.0

cos(5.6deg) = 0.99522739998
sin(5.6deg) = 0.09758289975



cos(2.8deg) = 0.99880613734
sin(2.8deg) = 0.04884976979

dx = (cos(0.0deg) + cos(5.6deg)) * 0.5 = 0.99761369999
dy = (sin(0.0deg) + sin(5.6deg)) * 0.5 = 0.04879144987
err = 1.0 - sqrt(dx*dx + dy*dy)
err = 0.00119386265


this might seem low, but this inaccuracy will quickly propagate up to noticeable errors, not in direction but in magnitude.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline KaiHH

JGO Kernel


Medals: 786



« Reply #32 - Posted 2015-10-03 10:38:46 »

At such few discrete values (2^6=64, 360/64=5.6deg per value) you start to need to renormalize your interpolated values... I'd say that you'd at least use 8 bits, for game purposes.
Yes, indeed. After applying alot of small rotations to a matrix, there was not only rotation but also some scaling effects as well.
I ended up using 9 bits.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #33 - Posted 2015-10-03 10:48:10 »

As cache is that important, simply merge the cos and sin lookup tables and test whether that reduces cache-misses to the point the overall performance (in real world tests) increases.

1  
2  
3  
public static float cos(float v) {
   return sin(v + PI2);
}


with 9 bits, that would use (512+1)*4 = 2052 bytes, which hopefully lies in one 4K page.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Roquen

JGO Kernel


Medals: 518



« Reply #34 - Posted 2015-10-03 14:06:41 »

KaiHH: I'd be in state of sin to attempt to generalize numbers. Where would you think you could get a performance increase in JOML via table look-up?
Offline theagentd
« Reply #35 - Posted 2015-10-03 14:32:44 »

But regarding @Roquen's comment, can you probably give a vague percentage of how much faster the table-based lookup is compared to other methods in WSW maybe?
The only time I use lots of sin() calculations is for our swinging grass to simulate a wind force based on the position of each straw.

Math.sin(): 15.01ms
9-bit lookup with interpolation: 4.45ms
6-bit lookup with interpolation: 4.45ms

This is for the entirety of the grass calculation, so it does lots of other things too.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #36 - Posted 2015-10-03 14:41:09 »

That's when table-based is at it's best..you gotta make that cache load pay off.  What's the math...I'm not seeing an obvious sin here?
Offline theagentd
« Reply #37 - Posted 2015-10-03 15:55:27 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
public class FastSineWindFunction implements WindFunction{

   @Override
   public float getWindX(float time, float x, float y) {
      return FastTrigonometry2.sin(time + x);
   }

   @Override
   public float getWindY(float time, float x, float y) {
      return FastTrigonometry2.sin(time + y);
   }
}


I also have an implementation which does Math.sin().

Myomyomyo.
Offline Archive
« Reply #38 - Posted 2015-10-03 16:19:14 »

16.16 fixed point LUT.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
   public static int[] sin = new int[2048];

   public static int[] cos = new int[2048];

   static {
      for (int i = 0; i < 2048; i++) {
         sin[i] = (int) (65536.0 * Math.sin(i * 0.0030679615));
         cos[i] = (int) (65536.0 * Math.cos(i * 0.0030679615));
      }
   }


Usage

1  
2  
3  
4  
5  
int angle = 1024; (angle range is between 0 and 2047)
(should &= 0x7FF any variable angles to prevent out of bounds errors)

int value = 100;
int multiplied = value * sin[angle] >> 16;

Offline Roquen

JGO Kernel


Medals: 518



« Reply #39 - Posted 2015-10-03 16:45:30 »

sum of angles.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Archive
« Reply #40 - Posted 2015-10-03 17:35:35 »

sum of angles.
?

Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #41 - Posted 2015-10-03 22:13:09 »

Math.sin(): 15.01ms
9-bit lookup with interpolation: 4.45ms
6-bit lookup with interpolation: 4.45ms
I am curious as how to 12-bit without interpolation performs. Kiss

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline theagentd
« Reply #42 - Posted 2015-10-04 04:45:58 »

12-bit interpolated: 4.43 ms
12-bit raw value: 3.31 ms

16-bit interpolated: 5.20 ms
16-bit raw value: 4.25 ms


I totally did not see that coming. Weird. I don't think I got values like these earlier.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #43 - Posted 2015-10-04 12:39:24 »

That's for theagentd to ignore. For N objects he's performing 2N forward trig ops per simulation step.  The sim only requires two per step.
Offline theagentd
« Reply #44 - Posted 2015-10-04 13:27:15 »

So given 3 values (x, y, time) I can compute sin(x+time) and sin(y+time) with a single trigonometry function?

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #45 - Posted 2015-10-04 13:37:18 »

sin(t+x) = cos(x)sin(t)+cos(t)sin(x)
sin(t+y) = cos(y)sin(t)+cos(t)sin(y)

per sim step is cos(t) & sin(t) which is really one trig op...not that it would matter.

{....cos(x),sin(x),cos(y),sin(y)...} packed array.  Speculate loading and skips the trig table lookup.  More accurate, but that probably doesn't matter either.  So 2x (2 look-up, 2 mul, 1 add) per entry.
Offline theagentd
« Reply #46 - Posted 2015-10-04 16:26:17 »

sin(t+x) = cos(x)sin(t)+cos(t)sin(x)
sin(t+y) = cos(y)sin(t)+cos(t)sin(y)

per sim step is cos(t) & sin(t) which is really one trig op...not that it would matter.

{....cos(x),sin(x),cos(y),sin(y)...} packed array.  Speculate loading and skips the trig table lookup.  More accurate, but that probably doesn't matter either.  So 2x (2 look-up, 2 mul, 1 add) per entry.
Uhm, I simply use sin() to get a wavey motion. Each grass patch has a spring system, and the wind force calculation is based on a sinus function. There is no rotation here.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #47 - Posted 2015-10-04 17:28:18 »

No you're computing the y-component of two rotations.

EDIT: I'd expect the 2-fold symmetry to be obvious here.

EDIT 2: http://glslsandbox.com/e#28037.0
Offline theagentd
« Reply #48 - Posted 2015-10-04 23:10:40 »

I should care... but your "explanation" is like the worst possible professors at my uni who supposedly know a lot about their topics but can't teach for shit all combined into one. I can't follow your reasoning and it's too time consuming to decode your intentions. Sorry.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #49 - Posted 2015-10-05 07:46:07 »

I said up front "for you to ignore".

Quote
but your "explanation" is like the...
I explained nothing...there should be no need.  Math transforms are legal or not.  Identities are always legal.  The math doesn't care how you're thinking about the input or output.

For the google impaired: https://en.wikipedia.org/wiki/List_of_trigonometric_identities#Angle_sum_and_difference_identities

Every expression on this page is always true (for real input).

Any legal interpretation you can place on a mathematical expression is always legal.  Comparing two angles is always the same as comparing a point against a line through the origin.  It may or may not be worthwhile to consider other interpretations...either it's helpful in some way or it's not.  You brought up rotations, so yeah what you're doing is related to rotations.

EDIT: Pictures!

Click to Play


This one's slightly more fun:
Click to Play



Quote
..the worst possible professors at my uni...
They're paid to help you.  Any time I type in information here I'm putting my hand in my pocket and throwing cash out the window the entire time I'm typing.  Seems pretty understandable that my willingness to do so is rather limited.

I don't understand what you're whining about.  If you don't understand what, say, fold-symmetry means and you care then starting typing in google...I just did that and even before I completed my typing some pictures where popping up.  But you don't even need to do that...I typed in a brute force shader (rather poor visualization, but good enough)...click on the link.

Quote
too time consuming to decode your intentions
If you're using trig and/or inverse trig functions at any high rate, it's very likely you're missing some mathematical property that makes them disappear.  Using trig functions means you're manipulating angles...and angle are generally not interesting for computation.

Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #50 - Posted 2015-10-05 16:58:02 »

Offtopic:

Roquen, what kind of mobile plan are you on that you value terse descriptions over comprehensible descriptions. As I said before, you can be correct, but if you cannot convince, the effort is meaningless.

Most of us seem to take mobile bandwidth and online-time for granted. Surely it cannot be so expensive that you would handicap yourself like this.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Roquen

JGO Kernel


Medals: 518



« Reply #51 - Posted 2015-10-05 18:03:07 »

Fiber to the house...unlimited on the phone.  My time is the limiting factor.  Like I've said before I expect people can ask a question if they don't follow and/or can surf the web.
Offline ziozio
« Reply #52 - Posted 2015-10-05 18:19:58 »

sin(t+x) = cos(x)sin(t)+cos(t)sin(x)
sin(t+y) = cos(y)sin(t)+cos(t)sin(y)

per sim step is cos(t) & sin(t) which is really one trig op...not that it would matter.

{....cos(x),sin(x),cos(y),sin(y)...} packed array.  Speculate loading and skips the trig table lookup.  More accurate, but that probably doesn't matter either.  So 2x (2 look-up, 2 mul, 1 add) per entry.

Quote
For N objects he's performing 2N forward trig ops per simulation step.  The sim only requires two per step.

To decode this a bit for the people that are interested. I believe this is what Roquen is trying to say.

If you pre compute cos(x), sin(x), cos(y), sin(y) and save these values for each of the N objects you only need to compute sin(t) and cos(t) for each render cycle because these are the only variables that change. As you already have cos(x),sin(x),cos(y),sin(y) saved you just need to perform 4 multiplications and 2 additions per render cycle. Comparing both methods you get (Theagentd vs Roquen)

2N Lookups + 2N additions vs 4N multiplications + 2N Additions + 2 Lookups = 2N Lookups vs 4N Multiplications + 2 Lookups

Assuming multiplications are more than 2x quicker than lookups and N is sufficiently large you will save time using this method.

Hope this helps clears things up a bit
Offline theagentd
« Reply #53 - Posted 2015-10-05 18:42:43 »

To decode this a bit for the people that are interested. I believe this is what Roquen is trying to say.

If you pre compute cos(x), sin(x), cos(y), sin(y) and save these values for each of the N objects you only need to compute sin(t) and cos(t) for each render cycle because these are the only variables that change. As you already have cos(x),sin(x),cos(y),sin(y) saved you just need to perform 4 multiplications and 2 additions per render cycle. Comparing both methods you get (Theagentd vs Roquen)

2N Lookups + 2N additions vs 4N multiplications + 2N Additions + 2 Lookups = 2N Lookups vs 4N Multiplications + 2 Lookups

Assuming multiplications are more than 2x quicker than lookups and N is sufficiently large you will save time using this method.

Hope this helps clears things up a bit
Thank you, that is a great idea. I will implement that.                                                       

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #54 - Posted 2015-10-05 20:15:16 »

@ziozio: The real difference is going to be in dependency chains. (for x only shown below)

Table look up requires a sequence of 6
x0 = read x
x1 = x0 + RegM
x2 = x1 * K
x3 = int(x2)
x4 = x3 & M
x5 = table[x4]

Using sum-of-angles requires 3:
x00 = read cos(x) | x01 = read sin(x)
x01 = x00*RegM    | x11 = x01*RegN
x2  = x01+x11

@theagentd: the pre-computed sin/cos values have to be in an array.  Perhaps using jitwatch and careful layout you could get the computation into SIMD (packed) ops.
Offline CommanderKeith
« Reply #55 - Posted 2015-10-06 02:15:11 »

Quote
Quote
..the worst possible professors at my uni...
They're paid to help you.  Any time I type in information here I'm putting my hand in my pocket and throwing cash out the window the entire time I'm typing.  Seems pretty understandable that my willingness to do so is rather limited.
Lol, you must be an economist as well as a mathematician and programmer!
As someone who obviously understand opportunity cost, do you contribute to open source software? A truly rational person would not, it seems, since it's a complete waste of time. Yet may programmers do, for the fame, notoriety or feel-good emotion that they're part of something bigger than themselves.
I'm not faulting you and I appreciate your maths posts and your humour, demonstrated here. I just wonder how you can justify your actions based solely on opportunity cost.

Offline Roquen

JGO Kernel


Medals: 518



« Reply #56 - Posted 2015-10-06 11:39:09 »

Indeed, money here really means opportunity cost.  Personally I think it's a good idea to periodically think about the opportunity cost associated with any decision you make and decide from there if it's a good idea.  If you spend (say) an hour doing A, that's costing you two hours worth of doing B instead.  (You change to doing B, after the first hour that's how much of B you could have done if you had not done A.  But you're still one hour where would would have been if you hadn't done A at all.)

And another thing to take into account is Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.

Quote
...do you contribute to open source software?
I used to quite a bit.  I more or less stop for years when Richard Stallman adopted his "I'm a f**king idiot" public persona.  I still refuse to contribute to any FSF licensed software (beyond bug reports).  RS is really just the tip of the iceberg...I stopped and thought:  I really don't like any of these figurehead people and I don't like how these communities are are attracting and promoting the creation of vocal dogmatic asses. Sure I know they are actually the minority, but I don't care.  (Oddly I just got a tweet to this: http://sarah.thesharps.us/2015/10/05/closing-a-door)

Not so much these days mostly because projects I'd be willing to contribute to are complex and I don't have (or am unwilling to spend) the time to needed to understand the code base. Say LLVM or HotSpot.

Quote
A truly rational person would not, it seems, since it's a complete waste of time.
Quote
just wonder how you can justify your actions based solely on opportunity cost.
Because opportunity cost isn't the only consideration.  Another other important economic idea is utility.  Which may or may not be utility for the person in question that's spending their time.  I don't see any point in spending time typing up something where there are tons of resources on the subject.  Like locally trig identities.  On the other hand if I know of few to no resources on a particular topic I'm likely to write significantly more.  Recent examples: looking at N-d problems in 2D if that's the actual case. This information is scattered across different domains (I'm not aware of a single resource with this info).  And inequalities.  Time and time again I see very experience people missing some basic properties.  The wikipedia page seems to me to be somewhat understandable...but it does not walk through how they are related which is important for real understanding.
Offline theagentd
« Reply #57 - Posted 2015-10-06 12:10:14 »

Quote
..the worst possible professors at my uni...
They're paid to help you.  Any time I type in information here I'm putting my hand in my pocket and throwing cash out the window the entire time I'm typing.  Seems pretty understandable that my willingness to do so is rather limited.
Wow, I didn't even see this until now. Is that a joke? I'm being serious. What do you even think the purpose of this forum is?

I use and enjoy this forum for a number of reasons. People make interesting things that inspire me. I can post about think I've coded that I'm proud of and get feedback and acknowledgement from people who actually understand and appreciate what I'm doing, which is a rarity IRL for me. I learn new things about math, HotSpot, LWJGL and uncountable other things all the time here. I can follow and discuss the development of things I admire or personally care about. Even just explaining things to others helps me get a better grasp of those concepts myself.

That being said, how do your posts fit into that? Although you seem to want to help, your answers are too brief and unexplained to help much without a direct neural link to your brain. Your explanations are like a summary of your knowledge that only someone with similar knowledge already would understand. What annoys me the most is that you just literally told me that your time is extremely valuable, yet you expect every single person who read (and actually want to understand) your comments to spend a significant amount of time Googling to decode your posts.

I think it's sad, because if you're half as knowledgeable as you claim seem to be then I have lots to learn from you. I may not be interested in learning everything (AKA advanced quaternion math), but we often comment in the same threads which means our interests do overlap. IMO the main point of this forum is sharing knowledge. Maybe you don't think that you're "receiving" as much as you're "giving" to this forum since you already know a lot, but there are lots of other points that even it out IMO. It's not a zero-sum game.

Sorry for the off-topic post...

EDIT: claim ---> seem

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #58 - Posted 2015-10-06 12:34:49 »

Quote
What do you even think the purpose of this forum is?
Whatever you can make of it.

Quote
Even just explaining things to others helps me get a better grasp of those concepts myself.
This is worth pointing at...talking through stuff with someone often help clarify things to yourself.

Quote
...you just literally told me that your time is extremely valuable,
Everybody's time is valuable that's the whole point of opportunity cost vs. utility comments above.

Quote
yet you expect every single person who read (and actually want to understand) your comments to spend a significant amount of time Googling to decode your posts.
Or simply post:  can you explain this?  Look above I talk about dependency chains.  Explaining that for the widest audience would require giving a complete overview of how modern CPUs work. Or dig up a bunch of URLs for people to wade through.  

Quote
...if you're half as knowledgeable as you claim...
I don't recall making such a claim.  

Quote
I may not be interested in learning everything...
That's part of my point in being terse, there's no point is spending time on something if nobody's interested.

EDIT: Hit post instead of preview.
Offline princec

« JGO Spiffy Duke »


Medals: 1136
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #59 - Posted 2015-10-06 13:47:48 »

I like @Roquen's posts... it's like trying to do a cryptic crossword. Unfortunately 90% of what Roquen says is founded upon a huge chunk of basic mathematical and comp sci knowledge and wisdom which I don't have, so I am frequently completely in the dark about many assumptions that are made.

Now... I've got 35 years programming experience, 22 of which professional, and a honours comp sci degree, and even a Maths A level, but as I say... most of this stuff appears to be based on top of some foundation which appears not to have featured in either my admittedly wasted education or admittedly pragmatic experience. I would say that for the large majority of readers, they're in the same or worse states of understanding than I am, as many of 'em are half my age. When @theagentd or @Riven don't know what Roquen's on about though I know we're doomed, because they're amongst the two most intelligent people on the board.

All of which brings me to thinking that... it is possible that to save endless repeated terse and cryptic explanations (wasting your time even further) it might be ultimately more efficient to be more pragmatic and straightforward in approach to teaching us ignoramuses your wisdom.

Cas Smiley

Pages: 1 [2] 3
  ignore  |  Print  
 
 

 
Riven (397 views)
2019-09-04 15:33:17

hadezbladez (5280 views)
2018-11-16 13:46:03

hadezbladez (2204 views)
2018-11-16 13:41:33

hadezbladez (5544 views)
2018-11-16 13:35:35

hadezbladez (1150 views)
2018-11-16 13:32:03

EgonOlsen (4585 views)
2018-06-10 19:43:48

EgonOlsen (5462 views)
2018-06-10 19:43:44

EgonOlsen (3119 views)
2018-06-10 19:43:20

DesertCoockie (4016 views)
2018-05-13 18:23:11

nelsongames (4708 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
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!