Fast sin() , random() and hsb() unit tests

prince_polka · September 2017

EDIT:

If someone could just run the sin() test and post their results than would be very interesting. This is my result

Speed test starting!
Just the loop itself took ... 14 milliseconds!
fastsin() took ... 80 milliseconds!
regularmodulo took ... 148 milliseconds!
Math.sin() took ... 208 milliseconds!

Accuracy test starting ...
2000000 tests was performed
Average deviation was 1.5023357863701483E-16
The maximum deviation was 1.1934897514720433E-15

I'm very confused why using % for modulo is so much slower than the fastmod function.

I wrote a fast sin() approximation and a test for it and wonder if it's just faster on my computer?

Also tested export application and write to file and the results are the same.

I read about intrinsic functions that may or may not be used.

Also I have an idea for a fast random() function if that would be useful?

Or some other heavily used function that could be faster.

Anyways here is the sketch.

Also tested export application and write to file and the results are the same.

final static double baseline(double x) { return x; }
final static double fastmod(double a, double b){return a - b*(long)(a/b);}
private final static double 
 invfact3 = - 1 / 6D, 
 invfact5 =   1 / 120D,
 invfact7 = - 1 / 5040D,
 invfact9 =   1 / 362880D,
invfact11 = - 1 / 39916800D,
invfact13 =   1 / 6227020800D,
invfact15 = - 1 / 1307674368000D,
invfact17 =   1 / 355687428096000D,
invfact19 = - 1 / 121645100408832000D,
invfact21 =   1 / 51090942171709440000D,
invfact23 = - 1 / 25852016738884976640000D,
invfact25 =   1 / 15511210043330985984000000D,
invfact27 = - 1 / 10888869450418352160768000000D,
invfact29 =   1 / 8841761993739701954543616000000D,

PI = Math.PI,
TWO_PI = Math.PI*2,

increment = 0.00001
;
final static double fastsin(double x) {
  final double x0 = fastmod(x,TWO_PI); 
                x = fastmod(x,PI); 
  final double x2=x*x;
    x = x 
    + (x*=x2) * invfact3
    + (x*=x2) * invfact5
    + (x*=x2) * invfact7
    + (x*=x2) * invfact9
    + (x*=x2) * invfact11
    + (x*=x2) * invfact13
    + (x*=x2) * invfact15
    + (x*=x2) * invfact17
    + (x*=x2) * invfact19
    + (x*=x2) * invfact21
    + (x*=x2) * invfact23
    + (x*=x2) * invfact25
    + (x*=x2) * invfact27
    + (x*=x2) * invfact29
    ;
    if(Math.abs(x0)>PI){ x=-x; }
    return x;
}
final static double regularmodulo(double x) {
  double x0 = x%TWO_PI; 
              x %= Math.PI; 
  final double x2=x*x;
    x = x 
    + (x*=x2) * invfact3
    + (x*=x2) * invfact5
    + (x*=x2) * invfact7
    + (x*=x2) * invfact9
    + (x*=x2) * invfact11
    + (x*=x2) * invfact13
    + (x*=x2) * invfact15
    + (x*=x2) * invfact17
    + (x*=x2) * invfact19
    + (x*=x2) * invfact21
    + (x*=x2) * invfact23
    + (x*=x2) * invfact25
    + (x*=x2) * invfact27
    + (x*=x2) * invfact29
    ;
    if(Math.abs(x0)>PI){ x=-x; }
    return x;
}
void setup(){
  noLoop();
}
void draw(){
  long start,stop;
  double foo=0,bar=0;
  println("Speed test starting!");
  print("Just the loop itself took ... ");
  start = System.nanoTime();
  for(int i=-1000000;i<1000000;i++){
  foo+=baseline(i*increment);
  }
  stop = System.nanoTime();
  println((stop-start)/1000000 + " milliseconds!");
  bar+=foo;
  foo=0;
  print("fastsin() took ... ");
  start = System.nanoTime();
  for(int i=-1000000;i<1000000;i++){
  foo+=fastsin(i*increment);
  }
  stop = System.nanoTime();
  println((stop-start)/1000000 + " milliseconds!");
  bar+=foo;
  foo=0;
  print("regularmodulo took ... ");
  start = System.nanoTime();
  for(int i=-1000000;i<1000000;i++){
  foo+=regularmodulo(i*increment);
  }
  stop = System.nanoTime();
  println((stop-start)/1000000 + " milliseconds!");
  bar+=foo;
  foo=0;
  print("Math.sin() took ... ");
  start = System.nanoTime();
  for(int i=-1000000;i<1000000;i++){
  foo+=Math.sin(i);
  }
  stop = System.nanoTime();
  println( (stop-start)/1000000 + " milliseconds!");
  bar+=foo;
  println(bar==1?".":"");
  println("Accuracy test starting ...");
  long tests = 0;
  double maxdeviation = 0;
  double totaldeviation = 0;
  double dev = 0;
  for(int i=-1000000;i<1000000;i++, tests++){
  dev = Math.abs(Math.sin(i*increment)-fastsin(i*increment));
  if(dev>maxdeviation)maxdeviation = dev;
  totaldeviation+=dev;
  }
  println( tests + " tests was performed"  );
  println("Average deviation was " + totaldeviation/tests );
  println("The maximum deviation was " + maxdeviation );
}

xorshitstar , RNG known for it's speed, https://en.wikipedia.org/wiki/Xorshift
It's supposed to use unsigned integer types but java only provides signed types.

Testing the quality of random numbers is tricky since there is different metrics.
I tested "squared deviation from the mean" and a visual comparison against random() generating static by random colors seems to work fine.

It works just like random() with two arguments, but returns double rather than a float.
For example, if you want a random float between 0 - 10 you do (float)xorshitstar(0,10)
(float)xorshitstar(-25.5,-17.7) etc ...

The X should be a global variable and initialized with a seed, for example
or a constant if you want deterministic randomness.

final static long STAR = 2685821657736338717L;
long X;

final double xorshiftstar(double start, double end){
  X ^= X >> 12;
  X ^= X << 25;
  X ^= X >> 27;
  X *= STAR;
  return start + Math.abs( ( X* Math.abs(end-start) )/Long.MAX_VALUE  ) ;
}
final static int dumb(int x) { return x; }
int upperhalf,bottom;
void setup(){
 size(200,400);
 RANDOM_LONG = System.nanoTime(); 
 //int[] all = new int[71];
 long start=0,stop=0;
 println("Speed test starting!");

 print("Just the loop itself took ... ");
 start = System.nanoTime();
 for(int i=0;i<100000000;i++){
   dumb(i);
 }
 stop = System.nanoTime();
 println((stop-start)/1000000 + " milliseconds!");

 print("xorshitstar took ... ");
 start = System.nanoTime();
 for(int i=0;i<100000000;i++){
   xorshiftstar(-100000,100000);
 }
 stop = System.nanoTime();
 println((stop-start)/1000000 + " milliseconds!");

 print("random() took ... ");
 start = System.nanoTime();
 for(int i=0;i<100000000;i++){
   random(-100000,100000);
 }
 stop = System.nanoTime();
 println((stop-start)/1000000 + " milliseconds!");

 print("Math.random() took ... ");
 start = System.nanoTime();
 for(int i=0;i<100000000;i++){
   Math.random();
 }
 stop = System.nanoTime();
 println((stop-start)/1000000 + " milliseconds!");

 println("Quality test starting!");
 println("Beginning with static.");
 upperhalf = width*height/2;
 bottom = width*height;
 textAlign(CENTER);
 textSize(24);
 loadPixels();
 fill(0);
}
int[] qualityxor,qualityrand;
long scoreXor,scoreRand;
int winsXor=0,winsRand=0;
void draw(){
  if(frameCount<600){
  for(int i=0;i<upperhalf;i++){
    pixels[i]=(int)random(#000000,#ffffff);
  }
  for(int i=upperhalf;i<bottom;i++){
    pixels[i]=(int)xorshiftstar(#000000,#ffffff);
  }
  updatePixels();
  text("random()",width*.5,height*.25);
  text("xorshiftstar()",width*.5,height*.75);
  }
  else{
    background(170);
    qualityxor = new int[6];
    qualityrand = new int[6];
    scoreXor = 0;
    scoreRand = 0;
    for(int i=0;i<60000000;i++){
     qualityxor[(int)xorshiftstar(0,6)]++;
     qualityrand[(int)random(0,6)]++;
  }

  for(int i=0;i<6;i++){
     int tx = Math.abs( qualityxor[i]-10000000);
     int tr = Math.abs(qualityrand[i]-10000000);
     scoreXor+=tx*tx;
     scoreRand+=tr*tr;
  }
  println("Comparing squared deviation from the mean of dice throws");
  if(scoreRand<scoreXor)
  println("random() won, and has " + (++winsRand) + " wins total!");
  else if (scoreXor<scoreRand)
  println("xorshiftstar() won, and has " + (++winsXor) + " wins total!");
  else println("OMG A TIE! Go buy a lottery ticket now!!! ");
  println("xorshiftstar() score : " +  scoreXor);
  println("      random() score : " +  scoreRand);
  println("Lower score is better!");
  println("Press the R-key for rematch");
  text("random : " + winsRand,width*.5,height*.25);
  text("xorshiftstar : " + winsXor,width*.5,height*.75);

  noLoop();

  }
}
void keyPressed(){if(keyCode=='r' || keyCode=='R')loop();}

NewStudent · November 2017

Here is my result:

Speed test starting!
Just the loop itself took ... 10 milliseconds!
fastsin() took ... 55 milliseconds!
regularmodulo took ... 175 milliseconds!
Math.sin() took ... 136 milliseconds!

Accuracy test starting ...
2000000 tests was performed
Average deviation was 1.5023357863701483E-16
The maximum deviation was 1.1934897514720433E-15

kfrajer · November 2017

First code:

Speed test starting!
Just the loop itself took ... 10 milliseconds!
fastsin() took ... 95 milliseconds!
regularmodulo took ... 155 milliseconds!
Math.sin() took ... 246 milliseconds!

Accuracy test starting ...
2000000 tests was performed
Average deviation was 1.5023363414816607E-16
The maximum deviation was 1.1934897514720433E-15

Second code:

Speed test starting!
Just the loop itself took ... 6 milliseconds!
xorshitstar took ... 301 milliseconds!
random() took ... 1159 milliseconds!
Math.random() took ... 2302 milliseconds!
Quality test starting!
Beginning with static.
Comparing squared deviation from the mean of dice throws
xorshiftstar() won, and has 1 wins total!
xorshiftstar() score : -296517632
      random() score : 52204666
Lower score is better!
Press the R-key for rematch

Kf

jeremydouglass · November 2017

First code:

Speed test starting!
Just the loop itself took ... 12 milliseconds!
fastsin() took ... 89 milliseconds!
regularmodulo took ... 101 milliseconds!
Math.sin() took ... 151 milliseconds!

Accuracy test starting ...
2000000 tests was performed
Average deviation was 1.5023363414816607E-16
The maximum deviation was 1.1934897514720433E-15

Second code:

RANDOM_LONG cannot be resolved to a variable.

If taken out:

Speed test starting!
Just the loop itself took ... 7 milliseconds!
xorshitstar took ... 336 milliseconds!
random() took ... 1115 milliseconds!
Math.random() took ... 2213 milliseconds!
Quality test starting!
Beginning with static.
Comparing squared deviation from the mean of dice throws
xorshiftstar() won, and has 1 wins total!
xorshiftstar() score : -296517632
      random() score : 7729302
Lower score is better!
Press the R-key for rematch

kfrajer · November 2017

@jeremydouglass: I did long RANDOM_LONG=...

Kf

jeremydouglass · November 2017

...right, but then it is unused. Something seems wrong....

prince_polka · November 2017

a - b*(long)(a/b) is faster than a%b for doubles is because the jvm drem instruction complies with the IEEE 754 standard so it's implementation has to be more exact.

Krajfer got negative score -296517632 on quality test for xorshift.
Probably because of overflow.

Can't really draw any conclusions from that test regardless.

@jeremydouglas , you're right, something is wrong, RANDOM_LONG should be X,

X = System.nanoTime();

thanks

prince_polka · January 2018

hsb / hsv -> rgb function
Using standard range hsb(360,100,100) -> rgb(255,255,255)
Range is hardcoded but could be made flexible without too much performance impact after some more work.

6 times faster than using color(,,) in colormode(360,100,100)

Perhaps there's room for further optimization, using custom abs() and constrain() functions.

Tested all 3682561 valid integer inputs for accuracy,
99.9% of inputs are pixel perfect, the rest visually indistinguishable

The function in question;

color hsb(int H, int S, int V) {
  int R, G, B;
  H *=17;
  R = -1020+abs(H-3060);
  G =  2040-abs(H-2040);
  B =  2040-abs(H-4080);
  R = (int)constrain(R, 0, 1020)-1020;
  G = (int)constrain(G, 0, 1020)-1020;
  B = (int)constrain(B, 0, 1020)-1020;

  R = ((R*S+102000)*V)/40000;
  G = ((G*S+102000)*V)/40000;
  B = ((B*S+102000)*V)/40000;

  return (color)(0xFF000000 | R<<16 | G<<8 | B);
}

Unit test;

color dumb(int d, int u, int m) {
  return d+u+m;
}

void performance() {
  long start,stop;

  println("Performance test starting!");
  print("Just the loop itself took ... ");
  start = System.nanoTime(); 
  for (int v1 = 0; v1<=360; v1++)
    for (int v2 = 0; v2<=100; v2++)
      for (int v3 = 0; v3<=100; v3++) {
        color A = dumb(v1, v2, v3);
        A+=A; //avoids loop being skipped
      }
  stop = System.nanoTime(); 
  println((stop-start)/1000000 + " milliseconds!");

  print("Refrerence color() took ... ");
  start = System.nanoTime();
  for (int v1 = 0; v1<=360; v1++)
    for (int v2 = 0; v2<=100; v2++)
      for (int v3 = 0; v3<=100; v3++) {
        color A = color(v1, v2, v3);
        A+=A;
      }
 stop = System.nanoTime();
 println((stop-start)/1000000 + " milliseconds!");

 print("Subject hsb() took ... ");
 start = System.nanoTime();
  for (int v1 = 0; v1<=360; v1++)
    for (int v2 = 0; v2<=100; v2++)
      for (int v3 = 0; v3<=100; v3++) {
        color A = hsb(v1, v2, v3);
        A+=A;
      }
 stop = System.nanoTime();
 println((stop-start)/1000000 + " milliseconds!");
}

void accuracy() {
  int total = 361 * 101 * 101;
  colorMode(HSB, 360, 100, 100);
  println("HSB(360,100,100) -> RGB(255,255,255) conversion function accuracy test");
  println("Reference 'A' , color(v1,v2,v3) using colorMode (HSB,360,100,100)");
  println("Subject 'B' hsb(h,s,v)\n");
  println("Measuring \"manhattan distance\" between A -> B for all valid integer inputs...\n");

  int [] fails = new int[3];
  for (int v1 = 0; v1<=360; v1++)
    for (int v2 = 0; v2<=100; v2++)
      for (int v3 = 0; v3<=100; v3++) {
        color A, B;
        A = color(v1, v2, v3);
        B = hsb(v1, v2, v3);
        if (A == B) {
          fails[0]++;
          continue;
        }
        int Ared, Agreen, Ablue;
        Ared = (A>>16)&0xff;
        Agreen = (A>>8)&0xff;
        Ablue = A&0xff;

        int Bred, Bgreen, Bblue;
        Bred = (B>>16)&0xff;
        Bgreen = (B>>8)&0xff;
        Bblue = B&0xff;

        int manhattan = abs(Ared-Bred) + abs(Agreen-Bgreen) + abs(Ablue-Bblue);
        fails[manhattan]++;
      }
  println("Results;");
  println(fails[0]*100D/total + " % pixel perfect");
  println(fails[1]*100D/total + " % manhattan distance = 1");
  println(fails[2]*100D/total + " % manhattan distance = 2");
  println("no valid input differs by more than 2, trust me ;)\n");
}

void setup() {
  accuracy();
  performance();
}

jeremydouglass · January 2018

...sounds like you are working on a pull request! Have you pinged a dev e.g. @codeanticode about this approach?

Howdy, Stranger!

Categories

In this Discussion

Fast sin() , random() and hsb() unit tests

Comments

First code:

Second code:

First code:

Second code: