User talk:Rednaxela/FastTrig

Sound good! But, will it skipped turns at first tick of the first round? » Nat | Talk » 10:41, 3 March 2009 (UTC)

It shouldn't. It will always be as fast or faster than standard trig functions at least so long as you do the following:

• 'inline' the index calculations like was said and used in the example testfor
• Run init() BEFORE the battle begins (i.e. in static initialization code of your bot class)

An example of that static initialization code is like this:

public class SomeBot extends AdvancedRobot {
    static {
        FastTrig.init();
    }

    public void run() {
        // Not in here
    }
{

The initialization code doesn't take long (0.0017 seconds on my computer at 2880 divisions) but just to be sure it doesn't hurt to place the initialization outside of where the bot is timed --Rednaxela 16:27, 3 March 2009 (UTC)

My take

Nice work. From what I remember Simonton did something similar. I'm not sure if he had any luck though. One thing I noticed, I'm not sure if it works properly for negative angles, you will be rounding the wrong way. Also, the most useful trig function would be atan2. --Skilgannon 20:43, 3 March 2009 (UTC)

Ahh yes, sine doesn't work right at all yet for negative numbers. Cosine does work correctly except for rounding. I'll fix this now. :) --Rednaxela 21:51, 3 March 2009 (UTC)

Bugs

I was going to change the User:Rednaxela/FastTrig to fix the bug that Skilgannon said, and another one that happens with large DIVISION numbers and saw your edit, I haven't tested the fixed version, but I think it is still buggy. I think it should be:

  public static final double sin(double value) {
    return sineTable[(int)(((value/K + 0.5) % DIVISIONS + DIVISIONS)%DIVISIONS)];
  }
  public static final double cos(double value) {
    return cosineTable[(int)(((value/K + 0.5) % DIVISIONS + DIVISIONS)%DIVISIONS)];
  }

I'm testing it with 62832 DIVISIONS, and much bigger loops than yours and is much faster. Here is the test I used:

package ags.util;
public class FastTrigTest {
  public static void main(String[] args) {
    FastTrig.init();
    double v=0;
    long ms;
    int A = 10000;
    int B = 1000;
    double absolute = 0;
    for ( int i = 0; i < A; ++i ) for ( int j = 0; j < B; ++j ) {
      double angle = Math.random() * Math.PI * 200 - Math.PI * 100;
      absolute = Math.max(absolute, Math.abs(Math.sin(angle) - FastTrig.sin(angle)));
      absolute = Math.max(absolute, Math.abs(Math.cos(angle) - FastTrig.cos(angle)));
    }
    System.out.printf("Wrose error: %.12f\n", absolute);
    v=0;
    ms = -System.nanoTime();
    for ( int i = 0; i < A; ++i ) for ( int j = 0; j < B; ++j )
      v += FastTrig.sin(i * j * Math.PI - Math.PI / 3);
    ms += System.nanoTime();
    System.out.printf("FastTrig time: %.2f seconds\n", ms / 1E9);
    v = 0;
    ms = -System.nanoTime();
    for ( int i = 0; i < A; ++i ) for ( int j = 0; j < B; ++j )
      v += Math.sin(i * j * Math.PI - Math.PI / 3);
    ms += System.nanoTime();
    System.out.printf("Math time: %.2f seconds\n", ms/1E9);
  }
}

It also checks the error, so it was easy to the bugs. But anyway, including this will be a priority for me now :). Good work. --zyx 22:15, 3 March 2009 (UTC)

Thanks! Well, my +40*DIVISIONS one DOES work unless the angle is extremely negative, to a magnitude you wouldn't generally expect to see, but your double-modulus solution is more robust. Now making an updated version that includes that increased robustness, and atan(), and maybe atan2(). Will update the page when that's ready. --Rednaxela 00:05, 4 March 2009 (UTC)

Also discovered speed was further increased by using value*K instead of value/K and adjusting the constant to compensate, and also that the cosine table is redundant. Using the sine table for cosine with a shifted index doesn't affect speed but decreases init time and memory use. --Rednaxela 00:12, 4 March 2009 (UTC)

Hi, I have some problem. I do create new function:

public static final double tan(double value) {
	return FastTrig.sin(value) / FastTrig.cos(value);
}

... then I add following line to test ...

absolute = Math.max(absolute, Math.abs(Math.tan(angle) - FastTrig.tan(angle)));

... then, I run, result in: Worst error: Infinity! What wrong? » Nat | Talk » 03:47, 5 March 2009 (UTC)

Well Nat, at some angles cosine is equal to 0. Due to this you can't simply divide those. You should create a seperate table for tangent and use that and that would be faster anyway. --Rednaxela 04:11, 5 March 2009 (UTC)

Ahh, I forgot. I try your new way, too, but it still have a much of error, I don't understand why! » Nat | Talk » 04:38, 5 March 2009 (UTC)

What about the fact that tangent gives undefined at certain values? The error-checking code isn't designed the cope with that because (Undefined - Undefined) isn't equal to 0. --Rednaxela 04:49, 5 March 2009 (UTC)

Really? because I make all with high diff (over than 1) out, and all is number! Note that some calculator (like Google) return 1.6.....E16 for tan(PI / 2), and my machine return that, too! I don't know because trig function are java native method so it is platform dependent. » Nat | Talk » 05:06, 5 March 2009 (UTC)

Ahh. At PI / 2 it is undefined in actual math, HOWEVER it seems that beause computer can't quite perfetly represent PI/2 in floating point binary, it rounds to a number just SLIGHTLY smaller, which makes the result of the function simply become a very-large-number. Which come to think of it reminds me of why the error would be so high for tangent: Tangent by nature includes some very large values which mean error is naturally similarly larger. Really, "absolute error" shouldn't be what we measure, instead "angle error" is more relevant in reality with the kinds of geometry we'd be doing in robocode. --Rednaxela 05:16, 5 March 2009 (UTC)

OK, I understand. One more I just want to know, can we create an atan map? It seem that sin,cos and atan is most use trig function in robocode. » Nat | Talk » 06:17, 5 March 2009 (UTC)

I've pondered atan, but it's tricky because it doesn't repeat, and I'm not sure how much aproximation is permissiable near the edges --Rednaxela 06:53, 5 March 2009 (UTC)