Schnelle transzendente / trigonometrische Funktionen für Java

Question

Da die trigonometrischen Funktionen in java.lang.Math sind ziemlich langsam: Gibt es eine Bibliothek, die eine schnelle und gute Annäherung tut? Es scheint möglich, eine Berechnung mehrmals schneller zu tun, ohne viel Präzision zu verlieren. (Auf meinem Rechner nimmt eine Multiplikation 1,5 ns und java.lang.Math.sin 46ns bis 116ns). Leider ist noch kein Weg, um die Hardware-Funktionen zu nutzen.

UPDATE: Die Funktionen sollten genug, sagen wir, für die GPS-Berechnungen genau sein. Das heißt, Sie mindestens 7 Dezimalstellen Genauigkeit müßten, die Tabellen einfache Lookup-Regeln aus. Und es sollte viel schneller als java.lang.Math.sin auf Ihre grundlegenden x86-System sein. Sonst gäbe es darin keinen Sinn.

Für Werte über pi / 4 Java tut einige teure Berechnungen in Zusätzlich zu den Hardware-Funktionen. Er tut dies aus gutem Grund, aber manchmal kümmern Sie mehr über die Geschwindigkeit als für letzte Bit Genauigkeit.

Answer 1

Computer-Approximations von Hart. Tabellarisch Näherungsformeln für eine Reihe von Funktionen an verschiedenen Genauigkeiten Chebyshev-spart.

Edit: Getting mein Exemplar aus dem Regal, es stellte sich heraus, ein anderes Buch das klingt nur sehr ähnlich. Hier ist eine Sinusfunktion mit seinen Tabellen. (In C getestet, da die handlichen für mich.) Ich weiß nicht, ob dies schneller sein wird als die Java eingebaut, aber es ist garantiert weniger genau zu sein, zumindest. :) Möglicherweise müssen Sie zunächst das Argument Bereich reduzieren; finden Sie unter John Cook Vorschläge . Das Buch hat auch arcsin und 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;
}

Answer 2

Hier ist eine Sammlung von Low-Level-Tricks für die trigonometrischen Funktionen schnell annähert. Es gibt Beispielcode in C, die ich schwer zu folgen, aber die Techniken sind ebenso leicht in Java implementiert.

Hier ist meine gleichwertige Umsetzung von invsqrt und atan2 in Java.

Ich hätte etwas Ähnliches für die anderen trigonometrischen Funktionen getan, aber ich habe es nicht nötig, da Profilierung zeigte, dass nur sqrt und atan / atan2 waren erhebliche Engpässe.

gefunden

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 3

Das könnte es machen: http://sourceforge.net/projects/jafama/

Answer 4

Ich bin überrascht, dass die integrierte Java-Funktionen so langsam wäre. Sicherlich die JVM ruft die nativen trigonometrischen Funktionen auf Ihrer CPU, nicht die Algorithmen in Java implementiert. Sind Sie sicher, dass Ihre Engpass Anrufe Funktionen trig und nicht einige umgebenden Code? Vielleicht sind einige Speicherzuordnungen?

Könnten Sie in C ++ neu schreiben den Teil des Codes, der die Mathematik tut? Nur C ++ Code aufrufen trigonometrischen Funktionen wahrscheinlich die Dinge beschleunigen würde nicht zu berechnen, aber einige Kontext auch, wie eine äußere Schleife bewegen, um C ++ könnte die Dinge beschleunigen.

Wenn Sie eine eigene trigonometrischen Funktionen rollen müssen, nicht Taylorreihe allein verwenden. Die CORDIC-Algorithmen sind viel schneller, wenn Ihr Argument ist sehr klein. Sie könnten nutzen CORDIC, um zu beginnen, dann polieren das Ergebnis mit einer kurzen Taylor-Reihe. Sehen Sie diese Frage Stackoverflow auf wie implementieren trigonometrischen Funktionen .

Answer 5

Auf der x86 die java.lang.Math sin und cos-Funktionen nicht direkt auf die Hardware-Funktionen aufrufen, da Intel nicht immer tun, einen so guten Job, sie implimenting. Es gibt eine schöne Erklärung in Bug # 4857011.

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

Sie könnten schwer zu einem ungenauen Ergebnis zu denken. Es ist amüsant, wie oft ich Zeit finden, dies in anderem Code ausgeben.

"Aber der Kommentar sagt Sin ..."

Answer 6

Sie können Ihre Sinus und Kosinus in einem Array Pre-Speicher, wenn Sie nur ein paar ungefähre Werte benötigen. Zum Beispiel, wenn Sie die Werte von 0 ° bis 360 ° gespeichert werden sollen:

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

Sie verwenden dann diese Array Grad / Integer anstelle von Radiant / Doppel.

Answer 7

Ich habe nicht von irgendwelchen Libs gehört, wahrscheinlich, weil es selten genug trig schwere Java-Anwendungen zu sehen. Es ist auch leicht genug, um Ihre eigenen mit JNI (gleicher Präzision, bessere Leistung) zu rollen, numerischen Methoden (variable Präzision / Leistung) oder einer einfachen Annäherung Tabelle.

Wie bei jeder Optimierung, am besten zu testen, ob diese Funktionen tatsächlich ein Engpass vor stören das Rad neu zu erfinden.

Answer 8

trigonometrische Funktionen sind das klassische Beispiel für eine Lookup-Tabelle. Siehe die ausgezeichnete

• Lookup-Tabelle Artikel bei Wikipedia

Wenn Sie eine Bibliothek für J2ME sind können Sie versuchen:

• die Fixed Point Integer Math Library MathFP

Answer 9

Die java.lang.Math Funktionen aufrufen, um die Hardware-Funktionen. Es sollte einfach sein appromiations Sie machen können, aber sie werden nicht so genau sein.

Auf meinem labtop, sin und cos dauert etwa 144 ns.

Answer 10

In dem sin / cos-Test, den ich ausführen für ganze Zahlen Null bis zu einer Million. Ich gehe davon aus, dass 144 ns für Sie nicht schnell genug ist.

Haben Sie eine spezifische Anforderung für die Geschwindigkeit, die Sie benötigen?

Können Sie Ihre Anforderung in Bezug auf die Zeit pro Betrieb qualifizieren, die zufriedenstellend ist?

Answer 11

Schauen Sie sich Apache Commons Math Paket wenn Sie wollen bestehendes Material verwenden.

Wenn die Leistung ist wirklich des Wesens, dann können Sie gehen über die Implementierung dieser Funktionen selbst Standard-Mathematik-Methoden -. Taylor / Maclaurin Serie, speziell

Zum Beispiel sind hier mehrere Taylor-Reihenentwicklungen, die nützlich sein könnten (aus wikipedia ):

Answer 12

Könnten Sie das näher erläutern, was Sie tun müssen, wenn diese Routinen zu langsam sind. Sie könnten in der Lage sein, einige Koordinatentransformationen vor der Zeit eine oder andere Weise zu tun.