tangente - Funciones transcendentes/trigonométricas rápidas para Java

identidades trigonometricas en java

Question

Dado que las funciones trigonométricas en java.lang.Math son bastante lentas: ¿hay una biblioteca que haga una aproximación rápida y buena? Parece posible hacer un cálculo varias veces más rápido sin perder mucha precisión. (En mi máquina una multiplicación toma 1.5ns, y java.lang.Math.sin 46ns a 116ns). Lamentablemente, aún no hay una forma de usar las funciones de hardware.

ACTUALIZACIÓN: las funciones deberían ser lo suficientemente precisas, por ejemplo, para los cálculos de GPS. Eso significa que necesitaría una precisión de al menos 7 dígitos decimales, lo que descarta las tablas de búsqueda simples. Y debería ser mucho más rápido que java.lang.Math.sin en su sistema básico x86. De lo contrario, no tendría sentido.

Para valores superiores a pi / 4, Java realiza algunos cálculos costosos además de las funciones de hardware. Lo hace por una buena razón, pero a veces te importa más la velocidad que la precisión del último bit.

Answer 1

¿Podría explicar qué necesita hacer si estas rutinas son demasiado lentas? Es posible que pueda hacer algunas transformaciones de coordenadas con anticipación de una forma u otra.

Answer 2

Las funciones java.lang.Math llaman a las funciones de hardware. Debería haber aplicaciones sencillas que pueda hacer, pero no serán tan precisas.

En mi labtop, el pecado y cos lleva alrededor de 144 ns.

Answer 3

Las funciones trigonométricas son el ejemplo clásico de una tabla de búsqueda. Mira el excelente

• Artículo de tabla de búsqueda en wikipedia

Si buscas una biblioteca para J2ME, puedes probar:

• la biblioteca matemática de enteros de punto fijo MathFP

Answer 4

No he oído hablar de ninguna biblioteca, probablemente porque es lo suficientemente raro como para ver aplicaciones trigonométricas pesadas de Java. También es bastante fácil hacer su propio diseño con JNI (misma precisión, mejor rendimiento), métodos numéricos (precisión / rendimiento variable) o una tabla de aproximación simple.

Al igual que con cualquier optimización, lo mejor es probar que estas funciones son en realidad un cuello de botella antes de molestarse en reinventar la rueda.

Answer 5

Puede pre-almacenar su pecado y cos en una matriz si solo necesita algunos valores aproximados. Por ejemplo, si desea almacenar los valores de 0 ° a 360 °:

double sin[]=new double[360];
for(int i=0;i< sin.length;++i) sin[i]=Math.sin(i/180.0*Math.PI):

luego usa esta matriz usando grados / enteros en lugar de radianes / dobles.

Answer 6

Aquí hay una colección de trucos de bajo nivel para aproximar rápidamente las funciones trigonométricas. Hay un código de ejemplo en C que me resulta difícil de seguir, pero las técnicas se implementan tan fácilmente en Java.

Aquí está mi implementación equivalente de invsqrt y atan2 en Java.

Pude haber hecho algo similar para las otras funciones trigonométricas, pero no lo he encontrado necesario ya que los perfiles mostraron que solo sqrt y atan / atan2 eran los principales cuellos de botella.

public class FastTrig
{
  /** Fast approximation of 1.0 / sqrt(x).
   * See <a href="http://www.beyond3d.com/content/articles/8/">http://www.beyond3d.com/content/articles/8/</a>
   * @param x Positive value to estimate inverse of square root of
   * @return Approximately 1.0 / sqrt(x)
   **/
  public static double
  invSqrt(double x)
  {
    double xhalf = 0.5 * x; 
    long i = Double.doubleToRawLongBits(x);
    i = 0x5FE6EB50C7B537AAL - (i>>1); 
    x = Double.longBitsToDouble(i);
    x = x * (1.5 - xhalf*x*x); 
    return x; 
  }

  /** Approximation of arctangent.
   *  Slightly faster and substantially less accurate than
   *  {@link Math#atan2(double, double)}.
   **/
  public static double fast_atan2(double y, double x)
  {
    double d2 = x*x + y*y;

    // Bail out if d2 is NaN, zero or subnormal
    if (Double.isNaN(d2) ||
        (Double.doubleToRawLongBits(d2) < 0x10000000000000L))
    {
      return Double.NaN;
    }

    // Normalise such that 0.0 <= y <= x
    boolean negY = y < 0.0;
    if (negY) {y = -y;}
    boolean negX = x < 0.0;
    if (negX) {x = -x;}
    boolean steep = y > x;
    if (steep)
    {
      double t = x;
      x = y;
      y = t;
    }

    // Scale to unit circle (0.0 <= y <= x <= 1.0)
    double rinv = invSqrt(d2); // rinv ≅ 1.0 / hypot(x, y)
    x *= rinv; // x ≅ cos θ
    y *= rinv; // y ≅ sin θ, hence θ ≅ asin y

    // Hack: we want: ind = floor(y * 256)
    // We deliberately force truncation by adding floating-point numbers whose
    // exponents differ greatly.  The FPU will right-shift y to match exponents,
    // dropping all but the first 9 significant bits, which become the 9 LSBs
    // of the resulting mantissa.
    // Inspired by a similar piece of C code at
    // http://www.shellandslate.com/computermath101.html
    double yp = FRAC_BIAS + y;
    int ind = (int) Double.doubleToRawLongBits(yp);

    // Find φ (a first approximation of θ) from the LUT
    double φ = ASIN_TAB[ind];
    double cφ = COS_TAB[ind]; // cos(φ)

    // sin(φ) == ind / 256.0
    // Note that sφ is truncated, hence not identical to y.
    double sφ = yp - FRAC_BIAS;
    double sd = y * cφ - x * sφ; // sin(θ-φ) ≡ sinθ cosφ - cosθ sinφ

    // asin(sd) ≅ sd + ⅙sd³ (from first 2 terms of Maclaurin series)
    double d = (6.0 + sd * sd) * sd * ONE_SIXTH;
    double θ = φ + d;

    // Translate back to correct octant
    if (steep) { θ = Math.PI * 0.5 - θ; }
    if (negX) { θ = Math.PI - θ; }
    if (negY) { θ = -θ; }

    return θ;
  }

  private static final double ONE_SIXTH = 1.0 / 6.0;
  private static final int FRAC_EXP = 8; // LUT precision == 2 ** -8 == 1/256
  private static final int LUT_SIZE = (1 << FRAC_EXP) + 1;
  private static final double FRAC_BIAS =
    Double.longBitsToDouble((0x433L - FRAC_EXP) << 52);
  private static final double[] ASIN_TAB = new double[LUT_SIZE];
  private static final double[] COS_TAB = new double[LUT_SIZE];

  static
  {
    /* Populate trig tables */
    for (int ind = 0; ind < LUT_SIZE; ++ ind)
    {
      double v = ind / (double) (1 << FRAC_EXP);
      double asinv = Math.asin(v);
      COS_TAB[ind] = Math.cos(asinv);
      ASIN_TAB[ind] = asinv;
    }
  }
}

Answer 7

En la prueba sin / cos, estaba realizando números enteros de cero a un millón. Supongo que 144 ns no es lo suficientemente rápido para ti.

¿Tiene un requisito específico para la velocidad que necesita?

¿Puede calificar su requerimiento en términos de tiempo por operación que es satisfactorio?

Answer 8

En el x86, las funciones java.lang.Math sin y cos no llaman directamente a las funciones de hardware porque Intel no siempre hizo un buen trabajo implicándolas. Hay una buena explicación en el error # 4857011.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4857011

Es posible que desee pensar mucho sobre un resultado inexacto. Es divertido la frecuencia con la que paso el tiempo encontrando esto en el código de los demás.

"Pero el comentario dice Sin ..."

Answer 9

Eso podría hacerlo: http://sourceforge.net/projects/jafama/

Answer 10

Consulte el paquete Apache Commons Math si desea usar material existente.

Si el rendimiento es realmente esencial, puede implementar estas funciones usted mismo utilizando los métodos matemáticos estándar, específicamente las series de Taylor / Maclaurin.

Por ejemplo, aquí hay varias expansiones de la serie Taylor que podrían ser útiles (tomadas de wikipedia ):

Answer 11

Me sorprende que las funciones integradas de Java sean tan lentas. Seguramente la JVM está llamando a las funciones trigonométricas nativas en su CPU, no implementando los algoritmos en Java. ¿Está seguro de que su cuello de botella es llamadas a funciones trigonométricas y no a algún código circundante? Tal vez algunas asignaciones de memoria?

¿Podrías reescribir en C ++ la parte de tu código que hace las matemáticas? Simplemente llamar al código C ++ para calcular las funciones trigonométricas probablemente no aceleraría las cosas, pero mover algún contexto también, como un ciclo externo, a C ++ podría acelerar las cosas.

Si debe desplegar sus propias funciones trigonométricas, no use solo series de Taylor. Los algoritmos CORDIC son mucho más rápidos a menos que tu argumento sea muy pequeño. Puede usar CORDIC para comenzar, luego pulir el resultado con una breve serie de Taylor. Consulte esta pregunta de sobre cómo implementar funciones trigonométricas .

Answer 12

Aproximaciones de computadora por Hart. Tabula las fórmulas aproximadas economizadas de Chebyshev para un conjunto de funciones con diferentes precisiones.

Editar: Obtener mi copia del estante, resultó ser un libro diferente que suena muy similar. Aquí hay una función pecado usando sus tablas. (Probado en C, ya que es más útil para mí.) No sé si esto será más rápido que el Java incorporado, pero se garantiza que será menos preciso, al menos. :) Es posible que deba reducir el alcance del argumento primero; ver las sugerencias de John Cook . El libro también tiene arcsin y arctan.

#include <math.h>
#include <stdio.h>

// Return an approx to sin(pi/2 * x) where -1 <= x <= 1.
// In that range it has a max absolute error of 5e-9
// according to Hastings, Approximations For Digital Computers.
static double xsin (double x) {
  double x2 = x * x;
  return ((((.00015148419 * x2
             - .00467376557) * x2
            + .07968967928) * x2
           - .64596371106) * x2
          + 1.57079631847) * x;
}

int main () {
  double pi = 4 * atan (1);
  printf ("%.10f/n", xsin (0.77));
  printf ("%.10f/n", sin (0.77 * (pi/2)));
  return 0;
}