-1

I need to calculate ASin a lot of times in my project. In C# it takes to much time.

I use Math.Asin() from System namespace

The question is there any way to implement Asin function faster in C#.

Any approximation algorithm or another implementation which can work faster?

Nikita
  • 837
  • 1
  • 12
  • 23
  • 1
    If an approximate answer is good enough for you then you should consider pre-calculating a lookup table. You can use as many entries as you need to get the desired accuracy. – RogerN Dec 01 '16 at 18:23
  • I can not use too many additional memory, but still need a good approximation. So pre-calculating does not work for me. – Nikita Dec 01 '16 at 18:26
  • If there is no other way to implement asin , then I need approximation function, but I still cannot find appropriate – Nikita Dec 01 '16 at 18:27
  • Is it really `asin` that is the bottle-neck or is it something that requires arrays where safe C# code slows down because of constant range-checks? Does it help to mark the part of the code which is slow as `unsafe` to avoid the range check? -- `asin(x)` is essentially `atan2(x,sqrt(1-x*x))` where `atan2` and `sqrt` are usually handled by the FPU, one has to be very careful with alternatives, as they can easily exceed that operations count. – Lutz Lehmann Dec 01 '16 at 20:17
  • Have you actually profiled your code? – Daniel Underwood Dec 01 '16 at 22:29
  • Could you please, conforming to the guidelines, provide a minimal working example that showcases the same bad behavior? – Lutz Lehmann Dec 01 '16 at 22:34
  • Chances are if there was a faster way to do Asin then c# would already be using it. After all, why wouldn't they? So that leaves you with an approximation and if approximations are acceptable then you need to give more information on how precise you need the result to be? Whether it needs to be accurate to one decimal place or ten can make a massive difference to what solutions are available (though I can't think of any better approximations than lookup tables off the top of my head so if you've already ruled them out then you're just stuck with it I suspect. – Chris Dec 02 '16 at 00:07
  • The other thing might be the question of whether you can take a step back and ask if you really need to be calculating Asin so many times or is there an optimisation available that involves removing all the calls to that method. Or perhaps if the values you are passing are often repeated you can memoize the function to improve performance on subsequent calls. Essentially more context might help us come up with a proper way to help. That is this may be an XY problem - See http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem if you don't know what that is. – Chris Dec 02 '16 at 00:09
  • @Nikita You may want to take a look at my updated answer. I covered what I would like to in a comment, but it was too long for a comment. – Daniel Underwood Dec 03 '16 at 00:30

1 Answers1

1

After some debate in the comments and a benchmark for testing, it is apparent that the solution I have given below isn't really going to improve on the performance of System.Math.Asin(). In fact, both of the calls are nearly negligible and shouldn't be a huge impact for any application. If you are running into performance issues, your cause is likely one of the following:

  1. Your arcsin call isn't actually the bottleneck. You need to profile your application to determine the bottleneck for sure. Premature optimization is a common mistake and can lead to a lot of wasted time.
  2. You're calling the function too many times. You may have a valid reason for calling a function many times, but the calls are likely able to be optimized as a higher level. Possible solutions would be to use parallel calls or to change your order of operations to reduce calls. If you're calling something like y = sin(x); z = asin(y), then you're making extra unnecessary calls. That is a trivial example, but many more complicated computations can have similar effects mathematically.
  3. You're calling the function somewhere you shouldn't. For example, if you're trying to do computations in a GUI or rendering thread, you're going to run into performance issues and have a lack of responsiveness. This is a common design mistake and it should be noted that computations should not be done in a GUI thread.
  4. Your use case isn't feasible. If you're doing something like live data transformation and visualization, then there's an upper limit on how much data you can process in real-time. This is dependent on the hardware and there isn't much that can be done other than offloading the computations to somewhere with more processing power. A case like this is where cloud computing can come in handy.

Those points being made, the solution below is still a valid path towards optimization in C#. Do note that optimization should not be done until profiling an application so you actually know that the bottleneck is where you think it is. Note that this isn't the only route to optimization. Paths such as parallel processing or choosing different algorithms are also valid.

A bit of a different solution, but you can try to load the C standard library with something like the answer to this question. The C standard library on Windows is msvcrt.dll and should contain a function asin:

[DllImport("msvcrt.dll", EntryPoint="asin",
ExactSpelling=false, CharSet=CharSet.Unicode,
SetLastError=true)]
static extern double asin(double radians);

//calling the function
static void Main()
{
    double x = asin(0);
}

If this still isn't fast enough, you could write a fast asin algorithm in C. There's this question, which is similar to yours. You could also create a faster square root function to be used in this solution as well.

Depending on how accurate you need it, you could also do a Taylor series approximation if you're going to have an angle close to 0. You could also shift the angle to be close to zero, but that would need a bit more trickery.

Community
  • 1
  • 1
Daniel Underwood
  • 2,191
  • 2
  • 22
  • 48
  • Why should a soft linked procedure be faster than the CLI call to essentially the same code? – Lutz Lehmann Dec 01 '16 at 20:13
  • My assumption is that `System.Math.Asin()` was being interpreted by the .NET runtime rather than at a machine level. If this is the case, the C version should be a bit quicker. If not, they should be around the same. The only way to know for sure is a benchmark. If it is the same performance, a customized implementation in C should be faster than the same implementation in C#. Since OP seems to want more performance than most cases would need, porting some of the calculations to C should be able to squeeze out a bit of extra performance. – Daniel Underwood Dec 01 '16 at 20:22
  • I would believe it likely that in the CLI runtime calls to asin like other calls to IEEE 754 defined math functions are hard-coded, there should be no further interpreted sub-routine, except perhaps argument checks. – Lutz Lehmann Dec 01 '16 at 20:34
  • I threw together [this code](https://gist.github.com/danielunderwood/70f292e50dadabbda6f72033c83d2acc) to try to benchmark the two cases. From this, the two methods are coming up with pretty much the same results. But I'm also seeing either 0 or 1 tick on each call aside from a few outliers, which makes me wonder if it's being timed correctly. I thought it could be an optimization by the compiler, but I've saved the points to a file and read them back to try to get rid of any values precomputed by the compiler. If the results are correct, I think OP should consider if he actually has an issue. – Daniel Underwood Dec 01 '16 at 22:26
  • I still think that if this is really the slow part, then there is some loop`for(k=0; k – Lutz Lehmann Dec 01 '16 at 22:45