Fonctions rapides transcendantes / trigonométriques pour Java

Voici une collection d'astuces de bas niveau pour approximer rapidement les fonctions trig. Il y a un exemple de code en C que je trouve difficile à suivre, mais les techniques sont tout aussi facilement implémentées en Java.

Voici mon implémentation équivalente d'invsqrt et d'atan2 en Java.

J'aurais pu faire quelque chose de similaire pour les autres fonctions trig, mais je ne l'ai pas trouvé nécessaire car le profilage a montré que seuls sqrt et atan/atan2 étaient des goulots d'étranglement majeurs.

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;
    }
  }
}

Qui pourrait le rendre: http://sourceforge.net/projects/jafama/

Je suis surpris que les fonctions Java intégrées soient si lentes. La JVM appelle sûrement les fonctions trig natives sur votre CPU, sans implémenter les algorithmes en Java. Êtes-vous certain que votre goulot d'étranglement appelle des fonctions trigonométriques et non du code environnant? Peut-être quelques allocations de mémoire?

Pourriez-vous réécrire en C++ la partie de votre code qui fait le calcul? Le simple fait d'appeler du code C++ pour calculer les fonctions trigonométriques n'accélérerait probablement pas les choses, mais déplacerait également un contexte, comme une boucle externe, en C++ pourrait accélérer les choses.

Si vous devez lancer vos propres fonctions trig, n'utilisez pas la série Taylor seule. Les algorithmes de CORDIC sont beaucoup plus rapides à moins que votre argument ne soit très petit. Vous pouvez utiliser CORDIC pour commencer, puis polir le résultat avec une courte série de Taylor. Voir cette question StackOverflow sur comment implémenter les fonctions trig.

Sur le x86 le java.lang.Les fonctions Math sin et cos n'appellent pas directement les fonctions matérielles car Intel n'a pas toujours fait un si bon travail en les impliquant. Il y a une belle explication dans le bug #4857011.

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

Vous pourriez réfléchir à un résultat inexact. C'est amusant à quelle fréquence je passe du temps à trouver cela dans le code des autres.

"Mais le commentaire dit Péché..."

Vous pouvez pré-stocker vos sin et cos dans un tableau si vous n'avez besoin que de quelques valeurs approximatives. Par exemple, si vous souhaitez stocker les valeurs de 0° à 360°:

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

Vous utilisez ensuite ce tableau en utilisant des degrés/entiers au lieu de radians/double.

Je n'ai entendu parler d'aucune bibliothèque, probablement parce qu'il est assez rare de voir des applications Java lourdes. Il est également assez facile de rouler le vôtre avec JNI (même précision, meilleures performances), des méthodes numériques (précision / performance variable ) ou une simple table d'approximation.

Comme pour toute optimisation, mieux vaut tester que ces fonctions sont en fait un goulot d'étranglement avant de prendre la peine de réinventer la roue.

Les fonctions trigonométriques sont l'exemple classique d'une table de recherche. Voir l'excellent

• Article de table de recherche sur wikipedia

Si vous recherchez une bibliothèque pour J2ME, vous pouvez essayer:

• la Bibliothèque Mathématique Nombre Entier Fixe MathFP

Le java.lang.Fonctions mathématiques appelez les fonctions matérielles. Il devrait y avoir des approbations simples que vous pouvez faire, mais elles ne seront pas aussi précises.

Sur mon labtop, sin et cos prend environ 144 ns.

Dans le test sin/cos, j'effectuais pour des entiers de zéro à un million. Je suppose que 144 ns n'est pas assez rapide pour vous.

Avez-vous une exigence spécifique pour la vitesse dont vous avez besoin?

Pouvez-vous qualifier votre exigence en termes de temps par opération qui est satisfaisant?

Découvrez Apache Commons paquet de Maths si vous souhaitez utiliser le contenu existant.

Si la performance est vraiment de l'essence, alors vous pouvez procéder à l'implémentation de ces fonctions vous - même en utilisant des méthodes mathématiques standard-Taylor/Maclaurin series', en particulier.

Par exemple, voici plusieurs extensions de la série Taylor qui pourraient être utiles (tirées de wikipedia):

Pourriez-vous préciser ce que vous devez faire si ces routines sont trop lentes. Vous pourriez être en mesure de faire des transformations de coordonnées à l'avance d'une manière ou d'une autre.