Быстрые трансцендентные / тригонометрические функции для Java

Question

Поскольку тригонометрические функции в java.lang.Math довольно медленные: есть ли библиотека, которая делает быстрое и хорошее приближение? Кажется возможным выполнить вычисления в несколько раз быстрее, не теряя много точности. (На моей машине умножение занимает 1,5 нс, а java.lang.Math.sin от 46 нс до 116 нс). К сожалению, пока нет способа использовать аппаратные функции.

ОБНОВЛЕНИЕ: функции должны быть достаточно точными, скажем, для расчетов GPS. Это означает, что вам потребуется точность не менее 7 десятичных цифр, что исключает простые таблицы поиска. И это должно быть намного быстрее, чем java.lang.Math.sin в вашей базовой системе x86. Иначе в этом не было бы смысла.

Для значений более pi / 4 Java делает некоторые дорогостоящие вычисления в дополнение к аппаратным функциям. Это делается по уважительной причине, но иногда вы больше заботитесь о скорости, чем о точности последнего бита.

Answer 1

Компьютерные аппроксимации Харт. Табулирует приближенные к Чебышеву приближенные формулы для набора функций с различной точностью.

Редактировать: Взяв мою копию с полки, она оказалась другой книгой , которая звучит очень похоже. Вот функция sin, использующая ее таблицы. (Протестировано на C, так как это удобнее для меня.) Я не знаю, будет ли это быстрее, чем встроенная Java, но, по крайней мере, она гарантированно будет менее точной. :) Возможно, вам придется сначала уменьшить-аргумент; см. предложения Джона Кука . В книге также есть арксин и арктан.

#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

Здесь - это набор низкоуровневых трюков для быстрого приближения функций триггера. В Си есть пример кода, которому трудно следовать, но методы так же легко реализуются в Java.

Вот моя эквивалентная реализация invsqrt и atan2 в Java.

Я мог бы сделать что-то подобное для других функций триггера, но я не счел это необходимым, поскольку профилирование показало, что только sqrt и atan / atan2 были основными узкими местами.

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

Это может сделать это: http://sourceforge.net/projects/jafama/

Answer 4

Я удивлен, что встроенные функции Java будут такими медленными. Несомненно, JVM вызывает собственные функции триггера на вашем процессоре, не реализуя алгоритмы на Java. Вы уверены, что ваше узкое место - это вызовы функций триггера, а не некоторый окружающий код? Может быть, некоторые выделения памяти?

Не могли бы вы переписать в C ++ ту часть кода, которая выполняет математику? Простой вызов кода C ++ для вычисления функций триггера, вероятно, не ускорит процесс, но перемещение некоторого контекста, например внешнего цикла, в C ++ может ускорить процесс.

Если вам нужно выполнить свои собственные триггерные функции, не используйте только серии Тейлора. Алгоритмы CORDIC намного быстрее, если ваш аргумент не очень мал. Вы можете использовать CORDIC для начала, а затем отполировать результат короткой серией Тейлора. См. Этот вопрос StackOverflow на , как реализовать триггерные функции .

Answer 5

На x86 функции java.lang.Math sin и cos напрямую не вызывают аппаратные функции, потому что Intel не всегда хорошо справлялась с ними. В баге # 4857011. есть хорошее объяснение.

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

Возможно, вы захотите подумать о неточном результате. Забавно, как часто я трачу время на поиск этого в чужом коде.

«Но в комментарии говорится, что грех ...»

Answer 6

Вы можете предварительно сохранить свои грехи и cos в массиве, если вам нужны только приблизительные значения. Например, если вы хотите сохранить значения от 0 ° до 360 °:

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

затем вы используете этот массив, используя градусы / целые числа вместо радиан / двойных.

Answer 7

Тригонометрические функции являются классическим примером для справочной таблицы. Смотри отлично

• Статья таблицы поиска в Википедии

Если вы ищете библиотеку для J2ME, вы можете попробовать:

• * Математическая целочисленная библиотека с фиксированной точкой 1013 * MathFP

Answer 8

Я не слышал ни о каких библиотеках, вероятно, потому что это достаточно редко, чтобы увидеть триггерные тяжелые Java-приложения. Также достаточно легко выполнить свой собственный анализ с помощью JNI (та же точность, лучшая производительность), численных методов (переменная точность / производительность) или таблицы простой аппроксимации.

Как и при любой оптимизации, лучше всего проверить, что эти функции на самом деле являются узким местом, прежде чем пытаться изобретать велосипед.

Answer 9

В тесте sin / cos я выполнял для целых чисел от нуля до миллиона. Я предполагаю, что 144 нс не достаточно быстро для вас.

Есть ли у вас особые требования к скорости, которая вам нужна?

Можете ли вы квалифицировать свое требование с точки зрения времени на операцию, которое является удовлетворительным?

Answer 10

Не могли бы вы уточнить, что вам нужно делать, если эти процедуры слишком медленные. Вы можете сделать некоторые преобразования координат заранее, так или иначе.