in firmware must we use sqrt(x), or can we approximate

in planner.h in merlin, and i think other firmware uses this as well.

= sqrt(square(delta_mm[X_AXIS]) + square(delta_mm[Y_AXIS]) + square(delta_mm[Z_AXIS]));


this is used to calculate the length of travel and then adjust speed of travel based on the angle.

assuming a cube in which x,y step sizes are identical, the distance traveled is 1 to 1.4 inside of a cube depending on the angle. is this correct?
---- actually in a 3d view the line can also go up so the longest line drawn in a cube can be 1.96

has anyone tried to simplify the math for this part, and how accurate does it need to be?

for example, lets say i wanted to approximate it with a 32 value look up table with hard coded values so it does not use more ram, is 32 values approximated acceptable?

I guess I'm curious, because I'm sure if there was a way, it would already be implemented.

Edited 2 time(s). Last edit at 06/17/2013 07:54PM by jamesdanielv.

If you're looking for optimized algorithms, Teacup firmware is always worth a look: [github.com]

It works fast, but you also have to make sure you other algorithms don't depend on an exact number. If used for speed calculations, it's entirely fine, because speed doesn't have to be accurate (a 5% deviation would barely be noticed).

I tried to look up a better algorithm for distance calculations, but for integers I couldn't find one. There's always the problem with range, because a square has to be calculated, first. Yet, the overall result has a maximum of 2 times of the longest single distance.

For floats, there's fast inverse square root: [en.wikipedia.org]

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

looking for a simple way to know what is going on inside the cpu is not easy. i could view the raw asm instructions, but i believe the arduino math for sqrt is a version of Carmack’s method. the slight difference in microseconds time is probably from the branch to the function. there seems to be little wiggle room for performance gains except to unroll loops in firmware for reprap.
but there is also the known that we do a lot of similar math in that loop..

float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;

x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );

return number * y;
}



table generated on arduino with clocking time it takes to run.1st is sqrt function second is the one from above.
number:1 sqrt:1.00000000 micros 70 0.99830713 micros 74
number:2 sqrt:1.41421356 micros 64 1.41386008 micros 74
number:3 sqrt:1.73205080 micros 64 1.73054051 micros 74
number:4 sqrt:2.00000000 micros 70 1.99661436 micros 74
number:5 sqrt:2.23606801 micros 64 2.23570513 micros 74
number:6 sqrt:2.44948983 micros 64 2.44608831 micros 74
number:7 sqrt:2.64575123 micros 64 2.64210915 micros 74
number:8 sqrt:2.82842712 micros 64 2.82772016 micros 70
number:9 sqrt:3.00000000 micros 70 2.99657897 micros 70
number:10 sqrt:3.16227769 micros 64 3.15685772 micros 70
number:11 sqrt:3.31662487 micros 64 3.31139755 micros 74
number:12 sqrt:3.46410155 micros 64 3.46108102 micros 74
number:13 sqrt:3.60555124 micros 64 3.60506224 micros 74
number:14 sqrt:3.74165749 micros 64 3.74099731 micros 74
number:15 sqrt:3.87298345 micros 60 3.86626262 micros 74
number:16 sqrt:4.00000000 micros 64 3.99322872 micros 74
number:17 sqrt:4.12310552 micros 64 4.12061023 micros 74

but if you remove Newtonian corrections, you get a 3 times performance boost with a little more error.

float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;

x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f375a86 - ( i >> 1 );
y = * ( float * ) &i;
return number * y;
}

number:1 sqrt:1.00000000 micros 64 0.96622505 micros 30
number:2 sqrt:1.41421356 micros 70 1.43245005 micros 24
number:3 sqrt:1.73205080 micros 64 1.77367506 micros 20
number:4 sqrt:2.00000000 micros 64 1.93245010 micros 24
number:5 sqrt:2.23606801 micros 64 2.25931262 micros 20
number:6 sqrt:2.44948983 micros 70 2.52367496 micros 20
number:7 sqrt:2.64575123 micros 64 2.72553753 micros 20
number:8 sqrt:2.82842712 micros 64 2.86490011 micros 20
number:9 sqrt:3.00000000 micros 70 3.08238768 micros 24
number:10 sqrt:3.16227769 micros 64 3.26862525 micros 24
number:11 sqrt:3.31662487 micros 64 3.42361259 micros 24
number:12 sqrt:3.46410155 micros 60 3.54735016 micros 24
number:13 sqrt:3.60555124 micros 70 3.63983774 micros 20
number:14 sqrt:3.74165749 micros 64 3.70107507 micros 24
number:15 sqrt:3.87298345 micros 64 3.74053144 micros 24
number:16 sqrt:4.00000000 micros 70 3.86490011 micros 20
number:17 sqrt:4.12310552 micros 64 4.04005002 micros 24

Edited 2 time(s). Last edit at 06/20/2013 03:07AM by jamesdanielv.

here is my suggestion. use of this for approximations that can allow for 3.5% error, so far for whole numbers only.
use SqrtAprox
float SqrtAprox(float number) {//low in fat
unsigned long i;
float x, y;
y = number;
i = * ( long * ) &y;
i = 0x5f375a86 - ( i >> 1 );
y = * ( float * ) &i;
return number * y;
}

it runs about 3 times faster in whole numbers. floats error at up to 25%. will need to work on it a little more...



number: 1 sqrt: 1.00000000 micros: 64 0.96622505 micros: 34 difference: 0.03377497 %3.38
number: 2 sqrt: 1.41421356 micros: 64 1.43245005 micros: 20 difference: -0.01823652 %1.29
number: 3 sqrt: 1.73205080 micros: 64 1.77367506 micros: 24 difference: -0.04162431 %2.40
number: 4 sqrt: 2.00000000 micros: 64 1.93245010 micros: 24 difference: 0.06754994 %3.38
number: 5 sqrt: 2.23606801 micros: 64 2.25931262 micros: 20 difference: -0.02324462 %1.04
number: 6 sqrt: 2.44948983 micros: 64 2.52367496 micros: 24 difference: -0.07418513 %3.03
number: 7 sqrt: 2.64575123 micros: 64 2.72553753 micros: 24 difference: -0.07978630 %3.02
number: 8 sqrt: 2.82842712 micros: 64 2.86490011 micros: 20 difference: -0.03647303 %1.29
number: 9 sqrt: 3.00000000 micros: 70 3.08238768 micros: 20 difference: -0.08238769 %2.75
number: 10 sqrt: 3.16227769 micros: 70 3.26862525 micros: 20 difference: -0.10634757 %3.36
number: 11 sqrt: 3.31662487 micros: 70 3.42361259 micros: 20 difference: -0.10698772 %3.23
number: 12 sqrt: 3.46410155 micros: 64 3.54735016 micros: 20 difference: -0.08324862 %2.40
number: 13 sqrt: 3.60555124 micros: 64 3.63983774 micros: 24 difference: -0.03428650 %0.95
number: 14 sqrt: 3.74165749 micros: 64 3.70107507 micros: 20 difference: 0.04058242 %1.08
number: 15 sqrt: 3.87298345 micros: 64 3.74053144 micros: 24 difference: 0.13245201 %3.42
number: 16 sqrt: 4.00000000 micros: 64 3.86490011 micros: 24 difference: 0.13509988 %3.38
number: 17 sqrt: 4.12310552 micros: 60 4.04005002 micros: 24 difference: 0.08305550 %2.01
number: 18 sqrt: 4.24264049 micros: 64 4.20738744 micros: 20 difference: 0.03525305 %0.83
number: 19 sqrt: 4.35889911 micros: 64 4.36691284 micros: 24 difference: -0.00801373 %0.18
number: 20 sqrt: 4.47213602 micros: 64 4.51862525 micros: 20 difference: -0.04648924 %1.04
number: 21 sqrt: 4.58257579 micros: 64 4.66252517 micros: 20 difference: -0.07994938 %1.74
number: 22 sqrt: 4.69041585 micros: 60 4.79861259 micros: 24 difference: -0.10819674 %2.31
number: 23 sqrt: 4.79583168 micros: 64 4.92688751 micros: 20 difference: -0.13105583 %2.73
number: 24 sqrt: 4.89897966 micros: 64 5.04734992 micros: 24 difference: -0.14837026 %3.03
number: 25 sqrt: 5.00000000 micros: 70 5.16000032 micros: 20 difference: -0.16000032 %3.20
number: 26 sqrt: 5.09901952 micros: 64 5.26483774 micros: 24 difference: -0.16581821 %3.25
number: 27 sqrt: 5.19615221 micros: 64 5.36186265 micros: 24 difference: -0.16571044 %3.19
number: 28 sqrt: 5.29150247 micros: 64 5.45107507 micros: 24 difference: -0.15957260 %3.02
number: 29 sqrt: 5.38516473 micros: 64 5.53247499 micros: 24 difference: -0.14731025 %2.74
number: 30 sqrt: 5.47722578 micros: 64 5.60606288 micros: 24 difference: -0.12883710 %2.35
number: 31 sqrt: 5.56776428 micros: 64 5.67183780 micros: 24 difference: -0.10407353 %1.87
number: 32 sqrt: 5.65685415 micros: 64 5.72980022 micros: 24 difference: -0.07294607 %1.29
number: 33 sqrt: 5.74456262 micros: 60 5.84440326 micros: 24 difference: -0.09984065 %1.74
number: 34 sqrt: 5.83095169 micros: 64 5.95510005 micros: 20 difference: -0.12414838 %2.13
number: 35 sqrt: 5.91607999 micros: 64 6.06189107 micros: 24 difference: -0.14581108 %2.46
number: 36 sqrt: 6.00000000 micros: 64 6.16477537 micros: 20 difference: -0.16477537 %2.75
number: 37 sqrt: 6.08276271 micros: 74 6.26375341 micros: 20 difference: -0.18099069 %2.98
number: 38 sqrt: 6.16441392 micros: 64 6.35882520 micros: 20 difference: -0.19441127 %3.15
number: 39 sqrt: 6.24499797 micros: 60 6.44999074 micros: 24 difference: -0.20499277 %3.28
number: 40 sqrt: 6.32455539 micros: 64 6.53725051 micros: 24 difference: -0.21269512 %3.36
number: 41 sqrt: 6.40312433 micros: 64 6.62060356 micros: 24 difference: -0.21747922 %3.40
number: 42 sqrt: 6.48074054 micros: 64 6.70005035 micros: 24 difference: -0.21930980 %3.38
number: 43 sqrt: 6.55743837 micros: 64 6.77559089 micros: 20 difference: -0.21815252 %3.33
number: 44 sqrt: 6.63324975 micros: 64 6.84722518 micros: 24 difference: -0.21397542 %3.23
number: 45 sqrt: 6.70820379 micros: 60 6.91495323 micros: 24 difference: -0.20674943 %3.08
number: 46 sqrt: 6.78233003 micros: 64 6.97877550 micros: 20 difference: -0.19644546 %2.90
number: 47 sqrt: 6.85565471 micros: 64 7.03869104 micros: 24 difference: -0.18303632 %2.67
number: 48 sqrt: 6.92820310 micros: 60 7.09470033 micros: 24 difference: -0.16649723 %2.40
number: 49 sqrt: 7.00000000 micros: 64 7.14680337 micros: 24 difference: -0.14680337 %2.10
number: 50 sqrt: 7.07106781 micros: 64 7.19500017 micros: 24 difference: -0.12393237 %1.75
number: 51 sqrt: 7.14142847 micros: 64 7.23929119 micros: 34 difference: -0.09786273 %1.37
number: 52 sqrt: 7.21110248 micros: 64 7.27967548 micros: 24 difference: -0.06857300 %0.95
number: 53 sqrt: 7.28010988 micros: 60 7.31615352 micros: 24 difference: -0.03604364 %0.50
number: 54 sqrt: 7.34846925 micros: 64 7.34872531 micros: 24 difference: -0.00025606 %0.00
number: 55 sqrt: 7.41619825 micros: 64 7.37739086 micros: 20 difference: 0.03880739 %0.52
number: 56 sqrt: 7.48331499 micros: 64 7.40215015 micros: 24 difference: 0.08116484 %1.08
number: 57 sqrt: 7.54983425 micros: 64 7.42300367 micros: 24 difference: 0.12683057 %1.68
number: 58 sqrt: 7.61577320 micros: 60 7.43995046 micros: 20 difference: 0.17582273 %2.31
number: 59 sqrt: 7.68114566 micros: 60 7.45299100 micros: 24 difference: 0.22815465 %2.97
number: 60 sqrt: 7.74596691 micros: 60 7.48106288 micros: 24 difference: 0.26490402 %3.42
number: 61 sqrt: 7.81024980 micros: 60 7.54617691 micros: 24 difference: 0.26407289 %3.38
number: 62 sqrt: 7.87400770 micros: 60 7.60933780 micros: 24 difference: 0.26466989 %3.36
number: 63 sqrt: 7.93725395 micros: 64 7.67054557 micros: 20 difference: 0.26670837 %3.36
number: 64 sqrt: 8.00000000 micros: 70 7.72980022 micros: 20 difference: 0.27019977 %3.38
number: 65 sqrt: 8.06225776 micros: 64 7.81884002 micros: 24 difference: 0.24341773 %3.02

here is the code to test the data and provide the time it took each one to run:

int i=0;
float testvar; //use to know float
long timervar; //use for counter
long timervar2; //use for counter
float testvar2 ;// used to sort number as well


void setup()
{ Serial.begin(115200);

delay(200); //helps with gibberish removal;
Serial.println("");//ensures that new line starts
}


float SqrtAprox(float number) {//low in fat
unsigned long i;
float x, y;
y = number;
i = * ( long * ) &y;
i = 0x5f375a86 - ( i >> 1 );
y = * ( float * ) &i;
return number * y;
}




void loop(){
i++;
byte c=i;
//first set timer of sqrt
timervar=micros();
testvar=sqrt(c);
timervar=micros()-timervar;


//second set timer of SqrtAprox
timervar2=micros();
testvar2=SqrtAprox(i);
timervar2=micros()-timervar2;
Serial.print("number: ");
Serial.print(c, DEC);
Serial.print(" sqrt: ");
Serial.print(testvar,8);
Serial.print(" micros: ");
Serial.print(timervar,8);
Serial.print(" ");

Serial.print(testvar2,8);
Serial.print(" micros: ");
Serial.print(timervar2,8);
Serial.print(" diference: ");
Serial.print(testvar-testvar2,8);
Serial.print(" %");
Serial.println(abs((testvar-testvar2)/testvar)*100,2);
delay(20); // delay 200 milliseconds


if (i>64){ int wait=0;// hey why go anywhere we've done a lot already.
while (wait==0){wait=0;} ;}
}

Edited 4 time(s). Last edit at 06/20/2013 06:56AM by jamesdanielv.

Ok i know i need to reduce error, but i thought id try implementing it in firmware.

the part on the right is just off the printer using the alternate root calc method in planner.cpp. sqrt is all over, and has been replaced.

the part on the right has not been cleaned up, and the base has a 0.5mm layer and it is a little thicker that the base. lt looks ok at the top layers and the corners as well as the lines. i don't see any difference.

the part on the left is from a few days ago testing slic3r settings .





i don't think the clear pla dose the parts justice with the camera flash. next parts will be larger objects probably in black. parts seem smoother in cura as well. used .99 slic3r. will use cura, and print parts in black pla. probably something bigger with more curves.

i need people to try this. replace planner.cpp here: planner.ccp it should process acceleration math a lot faster.



if this method works there is a lot more power left over in arduino. I'll work on improving precision

Edited 8 time(s). Last edit at 06/20/2013 09:27AM by jamesdanielv.