[RobertKuhlmann]

Speed for fatan2:

  2.5 fatan2(opp,adj) 10000 times   facos s;acos s
    1.18900001 s;2.03500008 s

Code will be on GitHub during the day.

[RobertKuhlmann]

I just finished a successful facos-test:

 2.4 facos(num) 10000 times   facos s;acos s
    0.86300001 s;2.31200003 s

Measurements for fatan2 will follow…

[RobertKuhlmann]

Hello Quentin any Yogi,

I was very busy today so please excuse my late answer.
I’m not finished with facos and fatan2. I’m on business travel tomorrow and will work on, inclusive complete integration with the armlevel-branch with conditional defines in Configuration.h a.s.o.

@Yogi:
We have some tweaks in the back, that may allow us to reach your requested speeds. I’ll take a look/try on that too.

I’ll upload the integration requirements on GitHub as soon as possible, so that you can write test-routines more easy. I’m using M998 (in Marlin_main.cpp) because it is a realistic test-environment for later use in Marlin (especially when it comes to memory usage).

pow(x,2):
My tests with the sqrt-approach transfered to sq() were not better than sq() itself. I didn’t compare it to pow though.

atan2:
The optimization-potential seems very good here, as soon as acos is up and running. I will try to finish my work on that tomorrow.

@Yogi:
Yes, I’m living in germany. My mail address: github@robertkuhlmann.de (its a fresh address exclusively for dev.-exchange, so if spammed I can change it with only little effort).

Greetings
Robert

[RobertKuhlmann]

Find me on Github:
https://github.com/RobertKuhlmann/Marlin_maths

I’ve uploaded my results to github. Replacements for sqrt, sin, cos and tan are operational and tested.
Speed is doubled for these.

I’ve included an enhancement for Marlin_main.cpp for test-output to the serial monitor with command M998.

[RobertKuhlmann]

Good news I’d like to share to all readers here:

The new functions work now. We have a fast replacement for sqrt() and an extremely fast one for sin(), cos() and tan().

I’m looking forward to finish the new math-library today.

To get it to work, I had to take care of teh fact, that PROGMEM can not be addressed like normal memory, but has to be read out by prgm-read-commands (prgm-read-dword in our case).
The value-array can be declared like this:

const float SIN_TABLE[901] PROGMEM = {
0.00000000000000000,
0.00174532836589831,
0.00349065141522373,
0.00523596383141958,
0.00698126029796155,
...
};

Access to the values in the array can be achieved this way:

      for (int i=0;i < 900; i++)
      {
        union {float flt; unsigned long lng;} cvt;
        cvt.lng = pgm_read_dword(&SIN_TABLE[i]);
        ms.printFloat(cvt.flt,8);
        SERIAL_ECHOLN("");
      }

One little goody for attentional readers of this thread:
Output of floats with the precision you like can be done with MarlinSerial (include MarlinSerial.h for that), but you need to move the declaration of printFloat from the private to the public section. Usage: Look into the code-snippet above.

Another goody. I do speed-measurement the folloewing way:

...
      SERIAL_ECHOLN("  2.1 SQRT(float) 10000 times   fsqrt s;sqrt s");
      float starttime1=millis();
      for (int i=0; i <= 10000; i++)
      {
        saveresult += fsqrt((i/100));
      }
      float stoptime1=millis();
      float starttime2=millis();
      for (int i=0; i <= 10000; i++)
      {
        saveresult += sqrt((i/100));
      }
      float stoptime2=millis();
      SERIAL_ECHO("    ");
      ms.printFloat((stoptime1-starttime1)/1000,8);
      SERIAL_ECHO(" s;");
      ms.printFloat((stoptime2-starttime2)/1000,8);
      SERIAL_ECHOLN(" s;");
      ms.printFloat(saveresult,8);
      SERIAL_ECHOLN("");
...

(print saveresult to prevent compiler-optimization)

Greetings from Germany
Robert

[RobertKuhlmann]

Yes. Arduino’s Reference says that. So we have to store the 32-bit representation of our floats and dereference and typecast on read. Unsigned int (is 32-bit long, as float is) is supported by PROGMEM arrays.

Good point. I was just wondering about the results I’ve gotfrom my fsin-tests.

Way to go:
The result values have to be stored in the array as the unsigned integer representation of the 32-bit float values.

The function for fsin(deg) should look something like this (assuming only 900 values for 0.0°-90.0° are stored in the array):

float fsin(float deg)
{
  int tmpswitch = 0;
  int index;
  if (deg > 270) {tmpswitch = 3;}
  else {if (deg > 180) {tmpswitch = 2;}
  else {if (deg > 90) {tmpswitch = 1;}}}
  switch (tmpswitch){
  case 0: {index = (int)deg*10;} break;
  case 1: {index = 900-(int)deg*10;} break;
  case 2: {index = -(int)deg*10;} break;
  case 3: {index= -900-(int)deg*10;} break;
  }//switch (tmpswitch)
  return return *(float*)&SIN_TABLE[index];
} //float fsin(float deg)

– untested –

That’s what we can learn from the fsqrt-function, that returns the 32-bit memory of an unsigned int as float.

And we need a little function to give us all the unsigned integers we need for the table (I think that’ll be no job excel can do. 😉 ).

[RobertKuhlmann]

I’ve seen the conversions in Marlin_main.cpp too (e.g. sth. like “sin(f_delta[x_axis]/SCARA_RAD2DEG)” or similar).

In motion_control.cpp the sin-calls gets a rad in function mc_arc, but that isn’t in use in your armlevel-branch. So, yes, we can switch to sin(deg), cos(deg) a.s.o.

[RobertKuhlmann]

I’ve got the fast approach running lately:

float fsqrt(float x)
{
    long val_int = *(long*)&x; /* Same bits, but as an int */
 
    val_int -= 127L << 23; /* Subtract 2^m. */
    val_int >>= 1; /* Divide by 2. */
    val_int += 127L << 23; /* Add ((b + 1) / 2) * 2^m. */
 
    return *(float*)&val_int; /* Interpret again as float */
}//float fsqrt(float x)

It’s significantly faster than sqrt(x):

  2. Performance
  2.1 SQRT(float) 10000 times   <fast> s;<standard> s
    0.26399998 s;0.68300004 s;

I’ll calibrate and take a look if accuracy is good enough…

[RobertKuhlmann]

Looks like the “Quake-sqrt” is 7 times slower than ATmega’s sqrt:

2.1 SQRT(float) 10000 times   <fast> s;<standard> s
    0.71600003 s;0.10400000 s;

…

Stephan’s sqrt doesn’t give useful results until now.

[RobertKuhlmann]

You are so very right. 🙂
I’ll have to break up my work on Marlin between merging and new trig.-functions, because the merge isn’t working as expected.
So I’ll concentrate on finishing the maths first.

[RobertKuhlmann]

Hi Quentin,

I think it will no become too specific.
256k should be available on any platform.

Even the code is not ATmega-specific.

But I’ll have to break up the arrays further on, because my Arduino won’t work with this package (fw doesn’t boot). I guess it needs more free memory at startup, than just the few kilobytes I left him.

But even with e.g. 16k-rad-tables the accuracy should be good enough. If not we can use some tricks, because of the symmetries in sinus, cosinus and tangens.

Have a nice weekend, Quentin. And all of you Morgan-fans too, of course. 🙂

[RobertKuhlmann]

Maths compiled now.
http://reprap.org/wiki/File:Marlin_mathematics.zip

Size of Marlin now (armlevel+Yogi+new_mathematics):
229996 bytes used of 258048 available bytes. 😀

[RobertKuhlmann]

Baahhh. Arrays are limited to 32K, it seems. Need to work around that…

-> Three arrays instead of multidimensional though. No fundamental problem.

[RobertKuhlmann]

Next steps done:

I’ve done an array of three columns (one each for fsin(), fcos(), ftan() ) with 7854 rows.
7854 is (2*Pi*10000)/8 (truncated to int). This allows addressing the table this way:

float fsin(float rad)
{
  return TRIG_TABLES[rad*1250,0];
} //float fsin(float rad)

TRIG_TABLES takes 94248 bytes.

Another table of 10001 rows for facos, consumes 40004 bytes, making facos look like this:

float facos(float num)
{
  //num range is 1 >= num >= -1
  //with 10001 rows (max index 10000, starting at 0)
  return ACOS_TABLE[(int)(5000-(num/2)*10000)];
}//float facos(float num)

Merging the armlevel- and Yogi’s branch is completed and compiles with no errors. I’ll check this against the actual Marlin branch, write some math-test routines and speed measurement and put it on my Morgan today.
I’ll post the results as soon as possible.
The new math-routines and tables can be found here in advance:
http://reprap.org/wiki/File:Marlin_mathematics.zip

Greetings
Robert

[RobertKuhlmann]

News:
Merging goes on very good. I’ve corrected the errors in “new_mathematics”, especially in “math_tables.h” and they should work now. I’ll test them before I send out the next version, using an Arduino simulator.

I have to refresh my C-skills. But it’s getting better every day. The arrays where defined wrong and therefor useless. But I’ve fixed that.

I’ll try a more radical approach to speed up sqrt. Take a look at this:

01: float squareRoot(float x)
02: {
03:   unsigned int i = *(unsigned int*) &x;
04:
05:   // adjust bias
06:   i  += 127 << 23;
07:   // approximation of square root
08:   i >>= 1;
09:
10:   return *(float*) &i;
11: }

It’s extremely fast and maybe it’s accurate enough for our purposes.
(found it over here: http://bits.stephan-brumme.com/squareRoot.html)

Thanks go to Stephan Brumme for publishing and documenting this approach.
Similar to this it should be quite easy to use this approach for sq() as well (with no loss of accuracy of course).

The new sin for example in new_mathematics.cpp now looks like this:

float rad2deg(float rad)
{
  return (rad*4068)/71;
}

float fsin(float rad)
{
  return SIN_TABLE[(int)(rad2deg(rad)*10)];
} //float fsin(float rad)

[Author]

Posts