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

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

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

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

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

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

    #include  #include  // 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 http://www.beyond3d.com/content/articles/8/ * @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 для начала работы, а затем отполировать результат с помощью короткой серии Taylor. См. Этот вопрос StackOverflow о том, как реализовать триггерные функции .

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

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

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

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

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

    вы затем используете этот массив, используя gradleусы / целые числа вместо radians / double.

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

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

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

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

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

    • Математическая библиотека математической памяти с фиксированной точкой

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

    На моем labtop, sin и cos занимает около 144 нс.

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

    У вас есть особые требования к скорости, в которой вы нуждаетесь?

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

    Ознакомьтесь с пакетом Apache Commons Math, если вы хотите использовать существующие материалы.

    Если производительность действительно важна, то вы можете сами реализовать эти функции, используя, в частности, стандартные математические методы – Taylor / Maclaurin series.

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

    alt text

    alt text

    alt text

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

    Interesting Posts

    Что означает «Не удалось найти или загрузить основной class»?

    Каков пакет по умолчанию, в который помещаются мои classы, если я не укажу его?

    лучший OCR (оптическое распознавание символов) пример в android

    Что случилось с настройкой GRUB?

    Причины использования функции set.seed

    C ++ Стереть векторный элемент по значению, а не по положению?

    Как изменить формат экрана Windows 10 Lock?

    Неисправность получения ClaimsPrincipal при использовании EasyAuth для аутентификации против AAD в Azure App Service в веб-приложении Asp.Net Core

    Используйте канал hiearchy для Boost.Log для фильтрации серьезности и раковины

    гранулы разного размера, пропорциональные оси x на ggplot 2 r

    Игнорировать папки / файлы, когда Directory.GetFiles () лишен доступа

    Новые интересные функции C # 4.0

    Имена файлов слишком длинные, и Windows не может открыть файлы

    Обнаружение Windows Server версии 32/64-бит в CLI

    Кэширование определенных файлов Javascript и CSS

    Давайте будем гением компьютера.