Joseph Goodman

Greenhorn

Posts: 18

posted 13 years ago

I have read in several places that the Java trig functions are very, very, slow compared to other languages. I was wondering if there was any alternative to using these functions. Perhaps there is a trig library that performs better? I have to call these functions over and over to project geographic locations onto an othrographic projection. I need the trig functions to run as fast as possible.

Thanks

Thanks

Maulin Vasavada

Ranch Hand

Posts: 1873

posted 13 years ago

Hi Joseph,

Could you find tangible results showing that Math's trig functions are slower against so and so other libraries?

I see that they are natively implemented in Java 1.4.2_03 so I guess they should not be slower.

Thanks

Maulin

Could you find tangible results showing that Math's trig functions are slower against so and so other libraries?

I see that they are natively implemented in Java 1.4.2_03 so I guess they should not be slower.

Thanks

Maulin

posted 13 years ago

There's an overhead associated with calling a native method, and so (especially for short methods) native doesn't necessarily imply fast.

In any case, Java numerics has a checkered history, and you'll find that sometimes Math.cos() is slow, and sometimes fast, depending on version, platform, etc.

The thing to do is to implement your program, then benchmark it.

In any case, Java numerics has a checkered history, and you'll find that sometimes Math.cos() is slow, and sometimes fast, depending on version, platform, etc.

The thing to do is to implement your program, then benchmark it.

*If*you measure that Math.cos is indeed a bottleneck, then there are many tricks people have used through the years to make this kind of thing faster -- remember that trig functions have always been slow on every platform. The first thing to think about would be pre-computing tables, and perhaps extrapolating betwen table entries if you need better accuracy.
Joseph Goodman

Greenhorn

Posts: 18

posted 13 years ago

This link shows a benchmark of trig method in different languages. The trig functions of JRE 1.4.2 appear to be 16 times slower than that of C++.

OS News Benchmark

Here is another similar benchmark:

benchmark2

I am positive that these function are causing my bottleneck. If I remove the calls to Math.cos and Math.sin the bottleneck dissapears. I am considering using the CORDIC algorithm. It allows me to set the precision of my calculations. Since I am using 32 bit float and not 64 bit double, it might make a performance difference.

OS News Benchmark

Here is another similar benchmark:

benchmark2

I am positive that these function are causing my bottleneck. If I remove the calls to Math.cos and Math.sin the bottleneck dissapears. I am considering using the CORDIC algorithm. It allows me to set the precision of my calculations. Since I am using 32 bit float and not 64 bit double, it might make a performance difference.

Maulin Vasavada

Ranch Hand

Posts: 1873

Warren Dew

blacksmith

Ranch Hand

Ranch Hand

Posts: 1332

2

posted 13 years ago

Joseph Goodman:

Since CORDIC is designed for machines without a hardware multiply instruction, it would seem to be a clear lose for RISC processors and a probable lose for Intel Pentium machines.

In my opinion, those benchmarks indicate that the trig functions were poorly implemented in that JVM. Reimplementing them yourself using a standard power series might be faster. And, as you say, a 32 bit implementation instead of a 64 bit implementation ought to be speed things up, perhaps by a factor of four or more, on machines with only a 32 bit processor.

*I am positive that these function are causing my bottleneck. If I remove the calls to Math.cos and Math.sin the bottleneck dissapears. I am considering using the CORDIC algorithm. It allows me to set the precision of my calculations. Since I am using 32 bit float and not 64 bit double, it might make a performance difference.*Since CORDIC is designed for machines without a hardware multiply instruction, it would seem to be a clear lose for RISC processors and a probable lose for Intel Pentium machines.

In my opinion, those benchmarks indicate that the trig functions were poorly implemented in that JVM. Reimplementing them yourself using a standard power series might be faster. And, as you say, a 32 bit implementation instead of a 64 bit implementation ought to be speed things up, perhaps by a factor of four or more, on machines with only a 32 bit processor.

Joseph Goodman

Greenhorn

Posts: 18

Warren Dew

blacksmith

Ranch Hand

Ranch Hand

Posts: 1332

2

posted 13 years ago

There's a standard power series approximation for each trigonometric function. For example:

cos(x) = 1 - x^2/2! + x^4/4! - x^6/6! ...

sin(x) = x - x^3/3! + x^5/5! ...

These series converge very quickly - in about half a dozen terms for a typical 32 bit floating point number - provided x is between -pi and +pi. (You can calculate ahead of time how many terms are needed.) The calculation can be sped up futher by calculating from the right and interleaving multiplications and additions. For example, the first three terms of cos(x) above could be calculated as:

y = ((x * x) / 12) - 1 // 12 == 4*3

cos(x) = y * ((x * x) / 2) + 1 // 2 == 2*1

(Hopefully I have that right; I haven't tested & coded it.) You should be able to generalize for larger numbers of terms.

I don't normally recommend rolling your own library functions, but for your application, it might be worth a try.

Edit: there's a separate power series for tan(x) and sec(x), but I'd just the relationships with sin and cos for that (e.g., tan = sin/cos) unless you really need performance. Also, when calculating the power series, it will be faster to multiply by the inverse of a constant (e.g., *0.5 instead of /2).

[ September 21, 2004: Message edited by: Warren Dew ]

cos(x) = 1 - x^2/2! + x^4/4! - x^6/6! ...

sin(x) = x - x^3/3! + x^5/5! ...

These series converge very quickly - in about half a dozen terms for a typical 32 bit floating point number - provided x is between -pi and +pi. (You can calculate ahead of time how many terms are needed.) The calculation can be sped up futher by calculating from the right and interleaving multiplications and additions. For example, the first three terms of cos(x) above could be calculated as:

y = ((x * x) / 12) - 1 // 12 == 4*3

cos(x) = y * ((x * x) / 2) + 1 // 2 == 2*1

(Hopefully I have that right; I haven't tested & coded it.) You should be able to generalize for larger numbers of terms.

I don't normally recommend rolling your own library functions, but for your application, it might be worth a try.

Edit: there's a separate power series for tan(x) and sec(x), but I'd just the relationships with sin and cos for that (e.g., tan = sin/cos) unless you really need performance. Also, when calculating the power series, it will be faster to multiply by the inverse of a constant (e.g., *0.5 instead of /2).

[ September 21, 2004: Message edited by: Warren Dew ]

It is sorta covered in the JavaRanch Style Guide. |