0
Offline
Newbie
Karma: 1
Posts: 26
Arduino rocks


« on: January 31, 2011, 05:25:51 pm » 
OK, firstly i'm sorry if this question has been posted elsewhere, i've had a good look in the forum and i haven't really found an answer.
I've read a whole load about calculating gps positions using arduino and the problems relating to accuracy, i know there's a couple of posts relating to accuracy issues and i thought about adding to them, but they're in the old "read only" forum and this is only kinda related.
I know that "Floats have only 67 decimal digits of precision" and that doubles are essentialy the same, so my question is.........
How does the Ardupilot module calculate gps distances so accurately? How have those cleaver people worked around the float/double issue?
I'm working with some pretty large distances (up to 1000's of kilometers), so the initial accuracy of the fix during the calculations is really important as is rounding errors!!
Any other work around's would great.



Logged





0
Offline
Newbie
Karma: 1
Posts: 16
Arduino rocks


« Reply #1 on: January 31, 2011, 07:21:48 pm » 
I'm working with a gps also, I'm using the TinyGPS library, its a life saver. The tinyGPS library can read in the NMEA statements from a gps and load them into floats. These NMEA statements are decimal equivalent to the hours, minutes,seconds of "normal" gps coordinates. The way that those decimal values are calculated, a change of .00001 is actually only about 68 inches (depending if it is latitude or longitude and location) while a change in the "ones" position can be hundreds of miles. So the float can handle great accuracy , besides most GPS with NMEA only output down to the 5th place which is still within a float's range. I don't know much about the Ardupilots but i would guess that is accurate enough to navagate. I



Logged





0
Offline
Newbie
Karma: 1
Posts: 26
Arduino rocks


« Reply #2 on: February 01, 2011, 03:52:13 am » 
@wkuace I think you (or i) my have misunderstood floats, i maybe did not explain fully in my post i should have quoted the entire paragraph, so here it is. "Floats have only 67 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point. Unlike other platforms, where you can get more precision by using a double (e.g. up to 15 digits), on the Arduino, double is the same size as float." the 67 bit i believe is to take into account the "." in the statement, ie one of the "digits or precision" is the "." so you can further reduce your accuracy if you have a decimal point. So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 and who knows whether it will round up or down the following figures to make it .8 or .9. So now we are up to a 0.099minute out with both the position and the destination waypoint, which then will increase after its put into the haversign formula due to rounding errors. There is already a thread in the old "read only" http://www.arduino.cc/cgibin/yabb2/YaBB.pl?num=1294325235 so for more stuff in gps's and floats have a look there. It's all very frustrating.



Logged





Tacoma, WA
Offline
Full Member
Karma: 4
Posts: 192
Arduino rocks


« Reply #3 on: February 02, 2011, 01:24:18 am » 
Is there a way to put everything to the left of the decimal into a long, and everything to the right of it into another long, and work with the number that way?



Logged

Brian from Tacoma, WA Arduino evangelist  since Dec, 2010.




0
Offline
Newbie
Karma: 1
Posts: 26
Arduino rocks


« Reply #4 on: February 05, 2011, 06:11:27 am » 
year, i guess i could put 2 longs together and deal with it that way, but i would still really like to figure out how ardupilot does it?



Logged





Auburn, CA, USA
Offline
Newbie
Karma: 3
Posts: 20
Arduino pebbles


« Reply #5 on: February 05, 2011, 02:06:17 pm » 
year, i guess i could put 2 longs together and deal with it that way, but i would still really like to figure out how ardupilot does it?
ArduPilot_2_7/GPS_NMEA.pde:102



Logged





Seattle WA
Offline
Full Member
Karma: 1
Posts: 208
Arduino rocks


« Reply #6 on: February 06, 2011, 01:38:28 am » 
@wkuace I think you (or i) my have misunderstood floats, i maybe did not explain fully in my post i should have quoted the entire paragraph, so here it is. "Floats have only 67 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point. Unlike other platforms, where you can get more precision by using a double (e.g. up to 15 digits), on the Arduino, double is the same size as float." the 67 bit i believe is to take into account the "." in the statement, ie one of the "digits or precision" is the "." so you can further reduce your accuracy if you have a decimal point. So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 and who knows whether it will round up or down the following figures to make it .8 or .9. So now we are up to a 0.099minute out with both the position and the destination waypoint, which then will increase after its put into the haversign formula due to rounding errors. There is already a thread in the old "read only" http://www.arduino.cc/cgibin/yabb2/YaBB.pl?num=1294325235 so for more stuff in gps's and floats have a look there. It's all very frustrating. What you are missing is that a float gives you six or seven significant figures in base 10, not six or seven digits in base 10. That's a major distinction. Seven signficant figures will give you precision as good as the GPS system is actually capable of. Over a hemisphere, seven signficant figures in distance works out to a spatial resolution of a couple of meters. It is possible there's a bug in Arduino floating point implementation, of course. Fixed point is great for applications like this  there are plenty of libraries and references for it floating around the web. I have no particular ones to recommend, however.



Logged





0
Offline
Newbie
Karma: 0
Posts: 1
<>


« Reply #7 on: February 07, 2011, 01:21:13 pm » 
afclewis:"So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 "
I believe you will get an error if you try to load a string into a float. 121°35' 53" in decimal equivalent is 121.598056. you also have to allow for N/S and E/W.
Don't forget, GPS is +/ 510 meters anyway. If you require accuracy, you should look at Vincenty's formulae.



Logged





Offline
Full Member
Karma: 11
Posts: 147


« Reply #8 on: February 07, 2011, 02:24:26 pm » 
afclewis:"So as i understand it this means that if i have an NMEA statement that says my position is 121°35'.87663 my float will only record 121°35'.8 " What the GPS outputs is a string, not a float. It's up to you to decide what to do with that string in your program. You are correct that if you decide to store that value in a float you will lose precision. The string consists of three parts: degrees, minutes, and seconds. Degrees is an integer between 0 and 359, minutes is an integer between 0 and 59, and seconds is represented by five digits between 00000 and 99999. All three of those values fit comfortably into unsigned integers. The usual way to deal with data elements like that is to create a struct to hold them. For instance: typedef struct { unsigned int degrees; unsigned int minutes; unsigned int seconds; } GPSCoordinate;
Then it's simple to write utility functions to populate a structure from a string, to write the value of a structure as a string, and to calculate the difference between two structures. If I were doing this I'd make a class library so I could use c++, which really lends itself to this kind of work.



Logged





0
Offline
Newbie
Karma: 1
Posts: 26
Arduino rocks


« Reply #9 on: February 09, 2011, 04:11:53 am » 
@DCContrarian Many thanks i'll have a see if i can do as you suggested, seems like a good plan. I'm not sure my coding is up to making a class library, but i'll give it a go and see what happens.



Logged





Offline
Edison Member
Karma: 3
Posts: 1001
Arduino rocks


« Reply #10 on: February 09, 2011, 02:00:42 pm » 
... seems like a good plan. No this is not a good plan and will not get you anywhere. You need to convert GPS coordinates to variables of type float in order to use them in your distance calculation formula. Single precision (32bit) float is all you need to do these calculations with a precision and accuracy suitable for any practical purpose. The “trick” is to convert the NMEA GPS coordinates to radians (not decimal degrees). Further, you should calculate distance as an arc rather than a metric value. You will only convert it back to a metric value for display purposes. Start with reading the NMEA output and convert coordinates to radians. Once you have this working, you can proceed to code for distance calculations. Some facts:  Float as implemented on the Arduino is in accordance with IEEE 754. This is single precision (32 bit) float.
 IEEE 754 uses a 23 bit mantissa (determines precision), 8 bits for a two’s complement exponent (determines range) and 1 bit for sign.
 Precision expressed as a number of decimal digits can be calculated from the formula log10(2**24) which is approximately 7.225 decimal digits.
 The float library on Arduino is coded in optimized assembly for the AVR range of micro controllers.
 Using floats for basic arithmetic (multiply, divide, add, subtract) is generally faster on the Arduino than using 32 bit integers, but add somewhat to the initial code size.


« Last Edit: February 09, 2011, 02:07:49 pm by BenF »

Logged





0
Offline
Newbie
Karma: 1
Posts: 26
Arduino rocks


« Reply #11 on: February 09, 2011, 02:13:25 pm » 
@BenF
Many thanks, for your comment, i did have a good think about the previous statement before instigating it and never actually started writing the code, so all good there.
I'll set about converting the NMEA string to radians tomorrow. Thanks for the detail about how a float is made up, things making more sense now.



Logged





Offline
Full Member
Karma: 11
Posts: 147


« Reply #12 on: February 09, 2011, 04:45:14 pm » 
Single precision (32bit) float is all you need to do these calculations with a precision and accuracy suitable for any practical purpose. The “trick” is to convert the NMEA GPS coordinates to radians (not decimal degrees). Further, you should calculate distance as an arc rather than a metric value. You will only convert it back to a metric value for display purposes. Start with reading the NMEA output and convert coordinates to radians. Once you have this working, you can proceed to code for distance calculations. Some facts:  Float as implemented on the Arduino is in accordance with IEEE 754. This is single precision (32 bit) float.
 IEEE 754 uses a 23 bit mantissa (determines precision), 8 bits for a two’s complement exponent (determines range) and 1 bit for sign.
 Precision expressed as a number of decimal digits can be calculated from the formula log10(2**24) which is approximately 7.225 decimal digits.
 The float library on Arduino is coded in optimized assembly for the AVR range of micro controllers.
 Using floats for basic arithmetic (multiply, divide, add, subtract) is generally faster on the Arduino than using 32 bit integers, but add somewhat to the initial code size.
What I proposed was 16bit integer math, not 32 bit. I can't believe float math  which requires an addon library  is faster than 16bit integer math, which is done through native instructions. In any case, for an individual calculation the difference is going to be microseconds; unless you're tracking millions of devices the difference is going to be immaterial. Converting to radians does nothing to improve your precision. You start with degrees anyway and then multiply and divide which introduce additional rounding errors. It makes no difference that degrees are 3digit decimal numbers and radians are 1digit, the internal representation is base2. Here's an experiment: take the measurement given, 121°35'.87663. In excel, convert it to radians, and at every step round your result to seven significant digits. Then convert it back to degrees, also rounding at every step. When I do that I get 121°35'.87400. Three significant digits were lost in the conversion. With a float, you've got 23 bits of precision. Is that enough? As a float, you are representing a value with a 23bit binary times a multiplier. Your precision is determined by the incremental change when the lowest order bit flips. It's the circumference of the earth divided by 2^23. That's about 15 feet. Regardless of what units you pick, that's the smallest increment that can be measured. Unless you are very careful rounding errors can creep in and make your precision significantly worse. What it really gets down to is precision vs accuracy. The string you get reports a measurement in minutes with five decimal places. This level of precision implies the measurement is accurate to 1/100,000 of a minute. A degree of minute is roughly 1.1 miles; 1/100,000 of a minute is about one half inch. By using integers you maintain that precision. I agree that this precision is greater than the accuracy of the GPS. Is float precision enough? You tell me. It's probably close to the accuracy of the measurement. I know if it was me I'd rather design in greater precision than lesser, and design to preserve the precision I was given rather than lessen it.



Logged





Offline
Edison Member
Karma: 3
Posts: 1001
Arduino rocks


« Reply #13 on: February 09, 2011, 06:00:11 pm » 
What I proposed was 16bit integer math, not 32 bit. I can't believe float math  which requires an addon library  is faster than 16bit integer math, which is done through native instructions. This is general information, unrelated to your post. The AVR microcontrollers used with Arduino do not have native instructions for multiply and divide and rely on compiler generated code. There is no reason whatsoever to avoid integer math, but speed is not a reason to get overly creative towards avoiding floats. Converting to radians does nothing to improve your precision. You start with degrees anyway and then multiply and divide which introduce additional rounding errors. It makes no difference that degrees are 3digit decimal numbers and radians are 1digit, the internal representation is base2.
Yes it does. Trigonometry in C requires radians and so keeping the source and intermediate results in the same format avoids repeated conversions and loss of precision. More significant however is to calculate distance as an arc. This prevents loss of precision resulting from intermediate calculations with small values (angles) and large values (distances). With a float, you've got 23 bits of precision. Is that enough?
Actually you have 24 bits (sign bit included) and yes this is enough. As a float, you are representing a value with a 23bit binary times a multiplier. Your precision is determined by the incremental change when the lowest order bit flips. It's the circumference of the earth divided by 2^23. That's about 15 feet. Regardless of what units you pick, that's the smallest increment that can be measured. Unless you are very careful rounding errors can creep in and make your precision significantly worse.
Correct that for 24 bits and you will be close. What it really gets down to is precision vs accuracy. The string you get reports a measurement in minutes with five decimal places. This level of precision implies the measurement is accurate to 1/100,000 of a minute. A degree of minute is roughly 1.1 miles; 1/100,000 of a minute is about one half inch. By using integers you maintain that precision. I agree that this precision is greater than the accuracy of the GPS.
GPS accuracy is referenced to absolute position. When we navigate and do repeated calculations we can expect relative position reports much better than the general stated accuracy. We can not expect inch accuracy with float calculations, but this was not what was asked for. Is float precision enough? You tell me. It's probably close to the accuracy of the measurement. I know if it was me I'd rather design in greater precision than lesser, and design to preserve the precision I was given rather than lessen it.
The problem with your proposal is that you will have to write your own functions for trigonometry and basic arithmetic to maintain precision. I have written a marine autopilot based on an AVR microcontroller and so it’s a bit more than speculations on my part.



Logged





Offline
Full Member
Karma: 11
Posts: 147


« Reply #14 on: February 09, 2011, 09:20:41 pm » 
The problem with your proposal is that you will have to write your own functions for trigonometry and basic arithmetic to maintain precision.
No, I'm not proposing that at all. This is what I proposed: Then it's simple to write utility functions to populate a structure from a string, to write the value of a structure as a string, and to calculate the difference between two structures.
The only calculation I propose is the difference between two structures  subtraction. You're absolutely right that to do sine/cosine calculations you need floats. However, by storing the received values in a format that preserves precision you can do subtraction that preserves precision. You can then take the subtracted value and convert it to a float. If it's small  like hundreds of feet  that conversion will preserve precision, and that precision is likely important. If it's large  thousands of miles  precision is lost but it's likely not important. If you convert to a float before doing subtraction you lose precision in all cases.



Logged





