Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (489)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (555)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Smart & Faster cos/sin (no lookup table)  (Read 3372 times)
0 Members and 1 Guest are viewing this topic.
Offline DzzD
« Posted 2011-05-09 21:15:43 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
public class MathX
{
     
    private static double f2=-0.5;
    private static double f4=-f2/(3.0*4.0);
    private static double f6=-f4/(5.0*6.0);
    private static double f8=-f6/(7.0*8.0);
    private static double f10=-f8/(9.0*10.0);
    private static double f12=-f10/(11.0*12.0);
    private static double f14=-f12/(13.0*14.0);
    private static double f16=-f14/(15.0*16.0);
    private static double f18=-f16/(17.0*18.0);
    private static double f20=-f18/(19.0*20.0);
    private static double PI=Math.PI;
    private static double PI2=2.0*PI;
    private static double PI05=0.5*PI;
 
    /**
    * Compute and return sinus of its parameter using taylor serie
    * @param x angle in radian to
    * @return sinus value for the given parameter
    */

    public static double sin(double x)
    {
        return cos(x-PI05);
    }
 
    /**
    * Compute and return cosinus of its parameter using taylor serie
    * @param x angle in radian to
    * @return cosinus value for the given parameter
    */

    public static double cos(double x)
    {
        if(x<0.0) x=-x;
        if(x<PI2)
        {
            if(x<PI)
            {  
                double x2=x*x;
                return 1.0+x2*(f2+x2*(f4+x2*(f6+x2*(f8+x2*(f10+x2*(f12+x2*(f14+x2*(f16+x2*(f18+x2*f20)))))))));    
            }
            else
            {
                x-=PI;
                double x2=x*x;
                return -(1.0+x2*(f2+x2*(f4+x2*(f6+x2*(f8+x2*(f10+x2*(f12+x2*(f14+x2*(f16+x2*(f18+x2*f20))))))))));      
            }
        }
        x%=PI2;
        x-=PI;
        double x2=x*x;
        return -(1.0+x2*(f2+x2*(f4+x2*(f6+x2*(f8+x2*(f10+x2*(f12+x2*(f14+x2*(f16+x2*(f18+x2*f20))))))))));
    }  
         
}

Offline Roquen
« Reply #1 - Posted 2011-05-10 19:31:09 »

Power series are interesting in theory and for knowing the rate of converagance, but not really useful for direct implement.  Wikipedia has a basic list of sound methods here.  It's best to use a computer algebra system or a specialized DSL to construct approximations (without too much hair loss).
Offline DzzD
« Reply #2 - Posted 2011-05-12 12:01:17 »

in this particular case (cos/sin) implementation become very interresting in term of speed, as the final expression can be factorized a lot it requiere few ops (few multiplications & additions) and is computed very fast, knowing the input range of value, one can even sometime inline it, with enought factor it is still faster than original Math.cos without noticable errors.

I've always used Mathcad (so long time that I am still using V 5.0 and just see that nowadays it is up to V15 !), it is a very nice software and easy to use

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2011-05-12 15:01:38 »

The big problems with truncated power series are:
1) The are centered around a point (where something like remez will be over the desired range)
2) The constants are reals, which are rounded to a float and these errors compound over the polynomial evaluation.  Numeric methods take into account FP usage.

As a simple example, here's code for a 5th order remez based vs. 5th order truncated power series:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
  // On [-Pi/2, Pi/2]
 // max abs error = 1.588p-13     @ 1.6a91e2p0  (~.000164)
 // max rel error = 1.61c6558p-13 @ 1.86ec88p-1 (~.000169)
 // f(0)    = 0
 // f(Pi/2) = 1 - 0x1.38p-19 (~.999998)
 public static float sin_n0(float x)
  {
    float x2 = x*x;
   
    return x * (1 + x2 * (x2 * 0.00761f - 0.16605f));
  }
 
  // On [-Pi/2, Pi/2]
 // max abs error = (at Pi/2)
 // max rel error = (at Pi/2)
 // f(0)    = 0
 // f(Pi/2) = 0x1.01288ap0 (~1.004525)
 public static float sin_r0(float x)
  {
    float x2 = x*x;
   
    return x * (1 + x2 * (x2 * (1.f/120.f) - (1.f/6.f)));
  }
Offline DzzD
« Reply #4 - Posted 2011-05-12 15:09:52 »

Quote
1) The are centered around a point (where something like remez will be over the desired range)
yes, that's why I mentioned that cosinus is a special case : symetrical and periodic (never very far of central point)

Offline DzzD
« Reply #5 - Posted 2011-05-12 15:22:10 »

Quote
2) The constants are reals, which are rounded to a float and these errors compound over the polynomial evaluation.  Numeric methods take into account FP usage.
hehe that's where double become your friend... and for an unknow reason you're forcing float WTF ? : 32 bit more precision are not negligeable in such computation, just try

NB: division is very slow in comparaison of multiplication/addition/substraction, using constant is not an option for evident speed reason

EDIT : Let me explain ....

  static double f1= 1.0/120.0;
  static double f2= 1.0/6.0;   
  public static double sin_r0d(double x) 
   {   
    double x2 = x*x;       
    return x * (1.0 + x2 * (x2 * f1 - f2));
   }
       
   public static double sin_r0d2(double x) 
   {   
     return x+Math.pow(x,5)/120.0-Math.pow(x,3)/6.0;
   }

    public static double sin_r0d3(double x) 
    {   
       double x2 = x*x;       
       return x * (1 + x2 * (x2 * (1.0/120.0) - (1.0/6.0))); 
    }

Output :
sin_n0(Math.PI*0.5)=0.9999977
sin_r0(Math.PI*0.5)=1.0045248
sin_r0d(Math.PI*0.5)=1.0045248555348174
sin_r0d2(Math.PI*0.5)=1.0045248555348174
sin_r0d3(Math.PI*0.5)=1.0045248555348174

error stay very low on all double computation and for your sample code all double computation results are identical and more accurate

Offline Roquen
« Reply #6 - Posted 2011-05-12 16:26:13 »

I chose a low order polynomial and 32-bit floats for comparison purposes.  The same issues hold if you move to doubles.  Unless my subtraction skills are on the frizt today, you're helping me prove my point.

Your double version is off by ~0x1.29p-8 (~.0045).
My float version is off by 0x1.38p-19 (~.000003)

So I have over twice as many valid digits, even though I have less of them. Tongue
Offline DzzD
« Reply #7 - Posted 2011-05-12 16:49:37 »

not requiered to proff anything, ouf ... I will not have to type any code this time  !

you're measuring error against the wrong equation, we are computing  x+(x^5)/120-(x^3)/6 not sinus, sinus have nothing to do there, it is only a hazard the error introduced by float low precision make the polynomial closer to sin, but still farther from  x+(x^5)/120-(x^3)/6 , expected result is more near to 1.0045... than 1.00

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2011-05-12 17:09:25 »

Can you two get a room? Pointing

For a lot of cases an error margin of 0.004 is perfectly acceptable, as we're probably not able to *see* the cumulative divergence any time soon, and once it's there, it might actually not be that important for the gameplay. It's always a tradeoff: if you want accuracy, simply use Math.sin(..) directly.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #9 - Posted 2011-05-12 18:00:00 »

Hehe: Wrong error (points to the title of the thread).

@Riven. Room?  You have no idea of domestic train/plane prices.

The complexity (assuming same precision) is the same, so why not get more "bang for your buck"??
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Nickropheliac (12 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

CopyableCougar4 (27 views)
2014-08-22 19:31:30

atombrot (40 views)
2014-08-19 09:29:53

Tekkerue (38 views)
2014-08-16 06:45:27

Tekkerue (34 views)
2014-08-16 06:22:17

Tekkerue (24 views)
2014-08-16 06:20:21

Tekkerue (34 views)
2014-08-16 06:12:11

Rayexar (72 views)
2014-08-11 02:49:23

BurntPizza (47 views)
2014-08-09 21:09:32
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!