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

StackOverflow https://stackoverflow.com/questions/523531

Вопрос

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

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

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

Это было полезно?

Решение

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

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

Другие советы

Здесь представляет собой набор низкоуровневых приемов для быстрого приближения тригонометрических функций.На C есть пример кода, которому мне трудно следовать, но методы так же легко реализованы на 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;
    }
  }
}

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

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

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

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

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

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

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

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

Вы могли бы предварительно сохранить свои sin и 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):

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

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

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

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

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

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

На моем лабораторном столе sin и cos занимают около 144 секунд.

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

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

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

Проверьте Математический пакет Apache Commons Math package если вы хотите использовать существующие материалы.

Если производительность равна действительно по сути, тогда вы можете приступить к реализации этих функций самостоятельно, используя стандартные математические методы - в частности, ряд Тейлора / Маклорена.

Например, вот несколько расширений ряда Тейлора, которые могут быть полезны (взяты из википедия):

alt text

alt text

alt text

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top