Degrees to radians and back, rounding issue

[madsci1016]

I noticed in programming SAGAR, that when I scan a waypoint from EEPROM (that's in degrees) and convert it to radians with M_PI / 180  and then do the reverse to display it to the operator, it's not always the same number, it's off a little.

Is this expected, what causes this drift in math?

[chelmi]

Yes, it is expected. Floating number representation has a finite precision. Some numbers cannot be represented in binary and have to be approximated.

http://en.wikipedia.org/wiki/Floating_point#Representable_numbers.2C_conversion_and_rounding

[Webbot]

Is it to with degrees+minutes - ie minutes are 0...59.9999

I convert to radians using

Code: [Select]


double rtn = strtod(&msg[inx], null);
// convert to pure degrees [dd.dddd] format
double degrees;
double minutesfrac = modf(rtn/100, &degrees);
rtn = degrees + (minutesfrac*100)/60;
// convert to radians
rtn *= (M_PI/180);
return rtn;

But if you are just converting back using degrees = radians / (M_PI/180) then the remainder also needs converting to 'minutes'

[madsci1016]

No, i'm sticking to degrees only. To convert to Radians,

  * M_PI/180

To go back to degrees,


*  180/M_PI

but I get

30.193543,-85.797445,150   =   30.193539,-85.797440

[Webbot]

Ok then its as mentioned by Chelmi

In avr-gcc then float and double are the same thing - and use 4 bytes. So called 'single precision' floating point. This uses 1 byte to store the signed exponent ie  2 power + or - 127. The remaining 3 bytes are used to store the digits of the number (1 bit for the sign and 23 bits for the number). This is enough for around 7 digits of accuracy - and this is what you are seeing.

Multiple computations make things worse. ie the original value of degrees would only have been stored to 7 significant digits.

M_PI/180 would also have been truncated to 7 digits and would be slightly different to 180/M_PI

Trying to evaluate what that means (and I'm sure you'll all correct me)

Assuming degrees are +- 180 then you've 3 digits to the left of the point and so 4 to the right ie accuracy = 0.0001 of a degree

Circumference of the Earth is approx 40,000,000 meters
so 360 = 40,000,000
    -----     --------------
    0.0001       x

x = 40,000,000 * 0.0001 / 360 = 11 meters

So the accuracy is +/- 11 meters due to truncating to a 4 byte float.

Which is significant!! Depending on the accuracy of your GPS in the first place.

---------------

Here's a potential improvement:-
Create a data type like:

typedef struct s_degrees{
   int16_t  whole;
   float      remainder;
} DEGREES;

Given a figure (longitude or latitude) from your GPS output then parse the integer element to the 'whole' element, and the remainder to the 'remainder' element.
Now the 'remainder' has 7 decimal places rather than 4 and so the accuracy should now be +- 0.011.

However: you now need your own maths library to add, subtract, multiply, divide a DEGREES type.

-----------------------

So no easy solution!

[Soeren]

Hi,

Which is significant!! Depending on the accuracy of your GPS in the first place.

Does any (non-military) GPS come with a better accuracy?
All the GPS'es I've had, have been able to suddenly jump 50m or more when stationary and my "fittness-tracker" or whatever the name is sometimes off even more (I've lost every ounze of faith in GPS as a nav tool for 'bots).

So no easy solution!

A floating point co-processor is not that hard to add, if it matters.

[chelmi]

A floating point co-processor is not that hard to add, if it matters.

I probably missed something, but that wont help with precision, only with processing speed which doesn't seem to be an issue here.

Chelmi.

[Webbot]

A floating point co-processor is not that hard to add, if it matters.

I probably missed something, but that wont help with precision, only with processing speed which doesn't seem to be an issue here.

Chelmi.

Correct - as hardware floating point units are still normally 32 bit.

Does any (non-military) GPS come with a better accuracy?
All the GPS'es I've had, have been able to suddenly jump 50m or more when stationary and my "fittness-tracker" or whatever the name is sometimes off even more (I've lost every ounze of faith in GPS as a nav tool for 'bots).

Yep there are some. For example these that are used in sports cars at a price but claim 2cm accuracy!
http://www.racelogic.co.uk/?show=VBOX-Products-VBOX_III_RTK&gclid=CLWD_pHx9aACFSMslAod6zTesw

[madsci1016]

Yes, there are affordable GPS's that get sub 3m accuracy with WAAS correction, so this rounding this is a problem.

I take it back Webbot, maybe it would be a good thing if your lib passes coordinates in degrees, because right  now i can't avoid the rounding problem from the first conversion to radians done in the lib. Then I can see if i can convert all my calculations to use degrees instead of radians, or come up with a better solution.

[madsci1016]

changing the second * 180/M_PI  to /(M_PI/180) helped a little.


30.193543,-85.797445  to 30.193541,-85.797440, opposed to 30.193539,-85.797440

[Webbot]

I take it back Webbot, maybe it would be a good thing if your lib passes coordinates in degrees, because right  now i can't avoid the rounding problem from the first conversion to radians done in the lib. Then I can see if i can convert all my calculations to use degrees instead of radians, or come up with a better solution.

It's kinda worse than that because it means that I cant store anything as a double/float at all (even in  degrees) as that is where the rounding happens!

I'm wondering about using a scaled 32/64 bit integer instead. ie 1cm resolution would mean storing numbers +/- 1,800,000,000 so a 32 bit int would work. So the data size is still 4 bytes but no loss of accuracy. But it depends on what you then do with it (ie any casting to a float/double would break it). Adding/subtracting points would require temporary casting to 64 bit integers.

[madsci1016]

There's no way we are the first to run into this problem. I'm too worn out tonight, but I'll bust out my mad google ninja skills tomorrow to see how others have handled GPS calculations on a 8bit MCU.

[Soeren]

Hi,

Correct - as hardware floating point units are still normally 32 bit.

Admittedly, I had misread the apparently quite common FPU which says 128 32bit registers (and not 32 128 bit registers), but while expensive, they do exist. Draft P754 mentions 20 significant digits and if time is not a factor and enough registers are available and free, you can do the math for high precision by using more registers for each number.
That aside, the best approach is of course to avoid converting back and forth. Keeping the original format and converting (in a separate register) just for display, continuing with the original number will be the best way to avoid these all too well known rounding errors.

Yep there are some. For example these that are used in sports cars at a price but claim 2cm accuracy!
http://www.racelogic.co.uk/?show=VBOX-Products-VBOX_III_RTK&gclid=CLWD_pHx9aACFSMslAod6zTesw

Oh, I'm in love
But I fear she would be the most expensive darling I had ever run into - probably more than a new car

[madsci1016]

This one claims 80 bit precession, but it's a hefty $40

http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail&name=MC68882EI16AR-ND

[Soeren]

Hi,

Trust me, you don't want such an outdated and slow chip.
It's an old Motorola (now Freescale) from way back when PC's were fairly young (or should that be, when Apple was just a freshly planted seed?).

If you really wanna go crazy, there's newer ones, like those used with ARM processors.

I don't think $43 is all that shocking (heck, that won't even buy me a dinner for one at my favourite restaurant), if I considered it usable, I'd pick up some - never put a price on the ones you love

[Webbot]

Isn't it all just theoretical anyway?

Assuming you can get higher precision floating point chips then how are you going to store the result in a variable when the compiler only knows about 32 bit. ie the compiler has got to be matched to the hardware.

I'm aware that the avr-gcc folks are being beaten up for breaking the C standard by making doubles the same size as floats. They have acknowledged that it would be easy to change but are holding off as they don't know what other existing code the change will break.

Hence my preferred solution would be to use large integer widths as this will also remove rounding errors. OK it may cause other 32bit/64bit maths functions to be linked in but its gotta be the easiest way.

@madsci There is one other thing to consider which is whether the number being placed in the EEPROM is the exact value from your source/text file. Have you tried printing out the number from the EEPROM without doing any conversions. Just a thought - in case the compiler process is rounding the number in the first place.

[madsci1016]

I'll check after work, but if anything, i'd say the string to float strtof() (or whatever, i can't remember) function i use to parse the ascii in eeprom would be a better possible culprit than the gcc convert file format pre-process i use to generate a .hex from a .txt.

[madsci1016]

30.193543-85.797445   +30.193542-85.797439     $SAGAN,19,1,30.193541,-85.797440,0,0*42

First coordinates are what's pulled from eeprom as ascii. The second is after it's parsed and saved as a float using strtod().  The NMEA sentence shows the number after it's been converted to radians and back.

I wonder is using stof() will make a difference?

Any other thoughts guys?

[madsci1016]

So, I got a new GPS that is amazing. See http://www.societyofrobots.com/robotforum/index.php?topic=9190.msg82637#msg82637

Repeated the same mission over three times. Had problems running into a car or curb, but what is awesome is that every time it was the same car or curb, within a foot or so!!!!!

So the GPS rocks, but so much so it makes the rounding affect problem stand out even more. Before I can do anything about it, I need access to the raw data stream.

Webbot, any chance you can add a feature or two to the nmea.h lib?

Did you ever see if what you parse from the NMEA string and save as double (before radian conversion ) equal each other, or do you see the same drift I do?

Maybe can you provide two strings in the NMEA struct that is the raw lat/lon ASCII tokens?

Soeren <- The last time you tried GPS, didn't happen to fall when the USA mandated the ~50m inaccuracy to be built into the GPS design?

[Webbot]

Webbot, any chance you can add a feature or two to the nmea.h lib?

Did you ever see if what you parse from the NMEA string and save as double (before radian conversion ) equal each other, or do you see the same drift I do?

Maybe can you provide two strings in the NMEA struct that is the raw lat/lon ASCII tokens?

The NMEA string doesn't actually give degrees it gives degrees and minutes ie: 'dddmm.mmm'
Where the mm.mmm portion goes up to 60.
Therefore actual degrees are 'ddd' + ('mm.mmm' / 60.0)
So I cant add the 'raw' ascii strings for degrees.

Incidentally - how are you printing the floating point numbers back into ascii? As there could be a problem there.

EDIT:- I've done some playing around and found a way of converting 'degrees and minutes' into 'degrees' with less rounding.
@madsci - Are you able to build the lib from scratch? If so then I can show you what lines to change.

[madsci1016]

EDIT:- I've done some playing around and found a way of converting 'degrees and minutes' into 'degrees' with less rounding.
@madsci - Are you able to build the lib from scratch? If so then I can show you what lines to change.

No, I haven't figured out compiling the lib yet.

I am using sprintf(%f) or rprintf(%f) to print out the numbers,

The first thing I caught was parsing dd.dddddd from a txt file stored in eeprom. That's what showed me the issues with double in 8 bit. just converting to from ascii to double showed a rounding issue, then more rounding when converting from degrees to radians and back.

[Webbot]

Just want to make it clear to 'readers' that the rounding problem from your eeprom has nothing to do with WebbotLib nor your GPS - just the C compiler. ie your are parsing it to a double using the C function strtod and turning it back into a string using the C function sprintf. And you get rounding errors.

As mentioned previously - you are just seeing the problem of the C compiler using 4 bytes to store a double. It has around 7 digits of accuracy - and your eeprom values use 8 digits. Hence the loss.

What I have done is to amend WebbotLib so that the longitude/latitude returned by it are less prone to rounding errors in their own right. I'll PM you with an interim release if you want to try it out.

[madsci1016]

Just found this

http://floating-point-gui.de/

have yet to read it, but hopefully it has some answers for this rounding issue.

[Webbot]

Just found this

http://floating-point-gui.de/

have yet to read it, but hopefully it has some answers for this rounding issue.

Yep - it just explains why ALL computers can only store floating point numbers to a fixed number of significant digits. The number of significant digits depends on how many bytes the C compiler allocates to a float or double. avr-gcc breaks the C standard and uses the same number of bytes for both - so the maximum is around 7 digits of accuracy. And we have to live with that.

Good find.

[madsci1016]

There's got to be a way around this for specialized purposes.

I know the Ardupilot code parses and stores the dd.dddd number without the period, so it's parsed and stored as a whole number (with no rounding) rather then a float with rounding. I don't know if they still lose the precision when they computer distance and bearing however, I need to go through the code again.