Funzioni trascendenti / trigonometriche veloci per Java

Poiché le funzioni trigonometriche in java.lang.Math sono piuttosto lente: esiste una libreria che faccia una rapida e buona approssimazione? Sembra ansible eseguire un calcolo più volte più velocemente senza perdere molta precisione. (Sulla mia macchina una moltiplicazione richiede 1.5ns e java.lang.Math.sin 46ns a 116ns). Sfortunatamente non esiste ancora un modo per utilizzare le funzioni hardware.

AGGIORNAMENTO: le funzioni devono essere sufficientemente accurate, ad esempio, per i calcoli GPS. Ciò significa che è necessaria una precisione di almeno 7 cifre decimali, che esclude tabelle di ricerca semplici. E dovrebbe essere molto più veloce di java.lang.Math.sin sul tuo sistema x86 di base. Altrimenti non ci sarebbe alcun senso.

Per valori superiori a pi / 4, Java ha alcuni costosi calcoli oltre alle funzioni hardware. Lo fa per una buona ragione, ma a volte ti interessa più della velocità che per l’accuratezza dell’ultimo bit.

Computer Approximations di Hart. Tabula formule approssimative economizzate secondo Chebyshev per un sacco di funzioni a diverse precisioni.

Modifica: Prendendo la mia copia dallo scaffale, si è rivelato essere un libro diverso che suona molto simile. Ecco una funzione sin usando le sue tabelle. (Testato in C dal momento che è più pratico per me.) Non so se sarà più veloce del Java built-in, ma è garantito che sia meno preciso, almeno. 🙂 Potrebbe essere necessario ridurre l’argomento prima di tutto; vedi i suggerimenti di John Cook . Il libro ha anche arcin e arcta.

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

Ecco una raccolta di trucchi di basso livello per approssimare rapidamente le funzioni trigonometriche. C’è un codice di esempio in C che trovo difficile da seguire, ma le tecniche sono altrettanto facilmente implementate in Java.

Ecco la mia implementazione equivalente di invsqrt e atan2 in Java.

Avrei potuto fare qualcosa di simile per le altre funzioni trigonometriche, ma non l’ho trovato necessario in quanto la profilazione mostrava che solo sqrt e atan / atan2 erano i principali colli di bottiglia.

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

Sono sorpreso che le funzioni Java integrate siano così lente. Sicuramente la JVM sta chiamando le funzioni trigonometriche native sulla tua CPU, non implementando gli algoritmi in Java. Sei sicuro che il collo di bottiglia siano le chiamate per triggersre funzioni e non un codice circostante? Forse alcune allocazioni di memoria?

Potresti riscrivere in C ++ la parte del tuo codice che fa la matematica? Il semplice fatto di chiamare il codice C ++ per calcolare le funzioni trigtiche probabilmente non accelererebbe le cose, ma anche spostare alcuni contesti, come un ciclo esterno, in C ++ potrebbe velocizzare le cose.

Se è necessario eseguire le proprie funzioni trigonometriche, non utilizzare la serie Taylor da solo. Gli algoritmi CORDIC sono molto più veloci a meno che il tuo argomento non sia molto piccolo. Puoi usare CORDIC per iniziare, quindi lucidare il risultato con una breve serie di Taylor. Vedi questa domanda StackOverflow su come implementare le funzioni trigonometriche .

Sull’86 le funzioni java.lang.Math sin e cos non chiamano direttamente le funzioni hardware perché Intel non ha sempre fatto un buon lavoro implorandole. C’è una bella spiegazione nel bug # 4857011.

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

Potresti voler riflettere su un risultato inesatto. È divertente quanto spesso trascorro del tempo a trovarlo nel codice degli altri.

“Ma il commento dice Sin …”

Puoi pre-memorizzare il tuo peccato e cos in un array se hai solo bisogno di valori approssimativi. Ad esempio, se si desidera memorizzare i valori da 0 ° a 360 °:

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

quindi si utilizza questo array usando gradi / numeri interi anziché radianti / doppio.

Non ho mai sentito parlare di lib, probabilmente perché è abbastanza raro vedere applicazioni Java trigliceride. È anche abbastanza facile eseguire il rollover con JNI (stessa precisione, prestazioni migliori), metodi numerici (precisione / prestazioni variabili) o una semplice tabella di approssimazione.

Come con qualsiasi ottimizzazione, è meglio testare che queste funzioni sono in realtà un collo di bottiglia prima di preoccuparsi di reinventare la ruota.

Le funzioni trigonometriche sono l’esempio classico di una tabella di ricerca. Vedi l’eccellente

  • Cerca l’articolo da tavolo su wikipedia

Se stai cercando una libreria per J2ME puoi provare:

  • la libreria matematica MathFP di interi numeri punto fisso

Le funzioni java.lang.Math chiamano le funzioni hardware. Dovrebbero esserci semplici consigli che puoi fare ma non saranno altrettanto accurati.

Sul mio labtop, sin e cos prendono circa 144 ns.

Nel test sin / cos mi stavo esibendo per numeri interi da zero a un milione. Presumo che 144 ns non sia abbastanza veloce per te.

Hai un requisito specifico per la velocità di cui hai bisogno?

Puoi qualificare il tuo requisito in termini di tempo per operazione che è soddisfacente?

Dai un’occhiata al pacchetto Math Apache Commons se vuoi usare cose esistenti.

Se le prestazioni sono davvero essenziali, puoi implementare queste funzioni tu stesso usando i metodi matematici standard – Taylor / Maclaurin series ‘, in particolare.

Ad esempio, qui ci sono diverse espansioni della serie Taylor che potrebbero essere utili (prese da wikipedia ):

alt text

alt text

alt text

Potresti approfondire ciò che devi fare se queste procedure sono troppo lente. Potresti essere in grado di fare alcune trasformazioni di coordinate prima o poi.