Precision of trigonometrical functions

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

Transact-SQL (2000)

Precision of trigonometrical functions

Author

Topic

AskSQLTeam
Ask SQLTeam Question

0 Posts

Posted - 2006-09-13 : 06:33:28

Uwe writes "Hi SQLTeam,

is there any way to get a more precise result for this function
SELECT SIN(52.68533) = 0.6606956517243444. Using the ms windows calculator i get this result 0,66069565172434472596669710743042 which is much better for further calculations.

The underlying Problem is, that i use something like SIN(x) in a much more complex formula to calculate the the distance between 2 geographical points. One part of the formular looks like this one

ACOS(SIN(RADIANS(52.6833))*SIN(RADIANS(52.6833))+(COS(RADIANS(52.6833))*COS(RADIANS(52.6833))*COS(RADIANS(7.95)-RADIANS(7.95))))*6378.388

When you try to run this as an Query against MS SQL Server (2000,2005), an error occurred. This happens because of the unprecise calculation of the sin and cosinus, culminating in a value larger then 1 for the acos function whats the error produced.

Example :
SELECT SIN(RADIANS(52.6833))*SIN(RADIANS(52.6833))+(COS(RADIANS(52.6833))*COS(RADIANS(52.6833))*COS(RADIANS(7.95)-RADIANS(7.95)))
=1.0000000000000002

Solving the same formula using the values calculatet by the ms windows calculator everything works fine...the result is
0.9903891431021473 and the function acos could take place.

I already tried to use cast and convert but nothing happend except of adding nulls up to reach the precision of the casted type.

THX"

Kristen
Test

22859 Posts

Posted - 2006-09-13 : 07:54:30

Not the Great Circle algorithm?

Are you looking for to-the-nearest kilometer/mile, or to the nearest thousand'th of an inch/cm?

To find your nearest Store simple Pythagoras will do, and run much faster on your server.

But I may be anticipating the wrong question, and therefore on the wrong track, in which case please Speak Up!!

Kristen

Kristen
Test

22859 Posts

Posted - 2006-09-13 : 08:09:24

This may help:

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=71720&SearchTerms=sin,cos,sqrt

there is an older thread which has more detail which would be worth searching for

Kristen

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2006-09-13 : 09:52:50

as written is there not a problem with your formula....

....COS(RADIANS(7.95) - RADIANS(7.95))
which is cos(a -a) = cos 0????

robvolk
Most Valuable Yak

15732 Posts

Posted - 2006-09-13 : 09:57:58

SQL Server's trig functions return a float type, which is both non-precise and limited to 15 digits of evaluation. You'll need to use an external program via COM or extended procedures to get more precise results.

I would suggest that instead of bringing the calculation to the data/database, offload the data to the calculating engine, then import the results back into the database as needed.

Kristen
Test

22859 Posts

Posted - 2006-09-14 : 06:46:32

I remembered a thread somewhere that suggested straight Pythagoras instead of Great Circle algorithm - where accuracy of a mile or so was needed, and not accuracy of fractions of an inch!

This has lots of useful info:

http://sqlteam.com/forums/topic.asp?TOPIC_ID=40295

and leads to:

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=12572&SearchTerms=you+need+points+a+few+inches+apart+to+notice

which is the one I was looking for.

For completeness I also turned up these:

http://sqlteam.com/forums/topic.asp?TOPIC_ID=16859
http://sqlteam.com/forums/topic.asp?TOPIC_ID=37410&SearchTerms=pythagoras
http://sqlteam.com/forums/topic.asp?TOPIC_ID=70781&SearchTerms=pythagoras
http://sqlteam.com/forums/topic.asp?TOPIC_ID=53132&SearchTerms=pythagoras,pythagorus
http://sqlteam.com/forums/topic.asp?TOPIC_ID=71621&SearchTerms=pythagoras,pythagorus
http://sqlteam.com/forums/topic.asp?TOPIC_ID=30843&SearchTerms=pythagoras,pythagorus

http://sqlteam.com/forums/topic.asp?TOPIC_ID=71720&SearchTerms=Pythagorus

Kristen

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-14 : 07:37:39

Great Circle distance

quote:
Spherical distance on the Earth

The shape of the Earth more closely resembles a flattened spheroid with extreme values for the radius of curvature, or arcradius, of 6335.437 km at the equator (vertically) and 6399.592 km at the poles, and having an average great-circle radius of 6372.795 km.

Using a sphere with a radius of 6372.795 km thus results in an error of up to about 0.5%.

I am sure some people more clever than me can calculate the distance needed with Pythagora's theorem to error with 0.5% compared with great circle distance formula.

Peter Larsson
Helsingborg, Sweden

Kristen
Test

22859 Posts

Posted - 2006-09-14 : 07:51:57

So, does that mean that worst case (which I think is North / South) comparing the distance to a "nearest store" directly 1 mile North of me and one 1 mile South might be out by about 8.8 yards?

If so its a bit pointless using some fancy, but cpu-intensive!, Trigonometry then!

Kristen

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-14 : 07:54:36

At least it makes you wonder how many decimals are really needed...

Peter Larsson
Helsingborg, Sweden

Kristen
Test

22859 Posts

Posted - 2006-09-14 : 07:58:09

"At least it makes you wonder how many decimals are really needed"

Not many for a "Square-it, add-it, and square-root it" calculation! - indeed, if all you need is "nearest", and not "how far" too, then the square-root isn't needed either (as recommended in one of the links I posted earlier)

Kristen
Kristen

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-14 : 08:01:55

You mean the Trigger Madness, where I suggested TOP 1?

And also, after reading some of the topics above, how accurate are the longitude and latitude readings anyway?
Are they measured outside the store, in the middle of the street, or in the middle of the store? That can mean 10's or 100's of yards error marginal to begin with.

Peter Larsson
Helsingborg, Sweden

RocketScientist
Official SQLTeam Chef

85 Posts

Posted - 2006-09-14 : 12:02:34

There are two issues here:

For distances less than about 60mi (100km) you're going to save a lot of time just working with the world as if it were flat (straight-up pythagorean). Once you get outside of that 60 mi/100km radius the actual and calculated distances will start to diverge pretty fast, at a rate that depends on the distance. For a driving distance estimation, anything less than 60 miles is "close enough". If you're just trying to rank a bunch of locations from closest to farthest, then it doesn't matter because you'll get the same ranked results whether you assume the world is flat or not, the variances between a flat earth and reality will grow the same in all directions.

(Note that this assumes the earth is a perfect sphere. Which it isn't, but your fancy-schmancy great circle algorithms make the same assumption, so it's a wash.)

Second, you're not considering the number of significant digits correctly. You have in your example 7 significant digits (52.68533). Any operations you perform that have more than 8 or 9 significant digits as interim results (to account for rounding errors) and you're exceeding the precision of your latitude/longitude measurements anyway.

Let's look for a moment at the precision of your input data by taking a look at two points right next to each other and how far apart they are. I use 24,000 for the circumference of the earth. It's in the right ballpark, and the values kinda-sorta cancel each other out anyway.

(52.68533 / 360) * 24,000 - (52.68532 / 360) * 24,000
or
3512.3551 - 3512.3546
or
.0005 miles, or 2.64 feet.

Notice that I carried enough digits in step 2 to not have a rounding problem.

Basically your variance here is about 2-3 feet. A touch under a meter for our friends in other countries.

So it makes no sense to try to do this with more significant digits, because (1) your incoming data isn't that precise, and (2) within 3 feet is close enough for driving distance. So from both a scientific and engineering perspective,you've got enough digits in SQL Server to handle either the driving distance or the distance ranking problems.

rs.

Kristen
Test

22859 Posts

Posted - 2006-09-14 : 12:30:40

So If I want the nearest store I can use Pythagoras (and skip the SQRT bit too).

If I want to show the distance I can use Pythagoras to quickly find the N nearest stores, and then Great Circle on those to get the actual distance with reduced CPU effort [i.e. because ti will only be a small data set].

And at the precision we are using I will be able to get the user to the right paving slab, let alone the right building!

Incidentally for folk wanting to map a User's location to Lat/Long (to then compare it to a list of known Lat/Long of possible "nearest stores") I like the way it is done at http://www.heavens-above.com/countries.asp

You choose your Country, then type in the name of your Town/Village/Hamlet and it offers you near neighbours (in case you didn't believe that it actually knows your Hamlet!) and Bingo!

All based on publicly available free data - so without the need to pay for PostCode database access etc. And great for "What's the nearest gold course to the hotel I'm going to be staying at for which I have absolutely no idea what the Post Code is" as well as countries for which PostCode -> Lat/Long is not yet an established art, or France/USA where the PostCode covers a large area, as well as countries that have no PostCodes at all.

You will have to download and import all the publicly available data, and do a bit of massaging on it ... but that's not too tough, and links to it are provided on the site. (Plus it will tell you when the Space Station is next coming overhead where you are and be bright enough to see easily, and calculate the rate that the Iridium satellites are spinning in orbit such that they will reflect the sun off their solar panels and display a timetable so that you will know when to look up to see the [often "very"] bright light shining on just where you are standing!)

Kristen

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-09-14 : 23:52:09

There isn’t anything wrong with the accuracy of SQL Server floating point calculations.

The problem is that the two points the poster is using are the same, and the Spherical Law of Cosines formula doesn't handle that very well. With two points only slightly apart, it does better.

The recommended method for doing this calculation is the Haversine formula. It handles small distances much better than the Spherical Law of Cosines formula.

The Haversine formula is more complex to implement, so it would be best to implement it as a function in an application.

The code below shows both methods.


declare @lon1 float
declare @lon2 float
declare @lat1 float
declare @lat2 float
declare @radius float

set @radius = 6371.0E
set @lon1 = radians( 7.9000 )
set @lon2 = radians( 7.9001 )
set @lat1 = radians( 52.6833 )
set @lat2 = radians( 52.6833  )


-- Begin Haversine Formula Distance Calculation
declare @a float

set @a = sqrt(square(sin((@lat2-@lat1)/2.0E)) + 
	(cos(@lat1) * cos(@lat2) * square(sin((@lon2-@lon1)/2.0E))) )

select [Haversine Formula Distance] =
	@radius * ( 2.0E *asin(case when 1.0E < @a then 1.0E else @a end ))

-- End Haversine Formula Distance Calculation


select [Spherical Law of Cosines Distance] =
acos((sin(@lat1)*sin(@lat2))+(cos(@lat1)*cos(@lat2)*cos(@lon2-@lon1)))*@radius

Results:


Haversine Formula Distance                            
----------------------------------------------------- 
6.7408614135541648E-3

(1 row(s) affected)

Spherical Law of Cosines Distance                     
----------------------------------------------------- 
6.7397375639908462E-3

(1 row(s) affected)

CODO ERGO SUM

Kristen
Test

22859 Posts

Posted - 2006-09-15 : 03:56:38

Sorry MVJ, I'm struggling to believe the CPU effort [of either of those, compared to straight Pythagoras] is worth it for a "nearest store" type query.

Kristen

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-15 : 04:24:11

From Wikipedia

quote:
This formula is only an approximation when applied to the Earth, because the Earth is not a perfect sphere: its radius R varies from 6356.78 km at the poles to 6378.14 km at the equator. There are small corrections, typically on the order of 0.1% (assuming the geometric mean R = 6367.45 km is used everywhere), because of this slight ellipticity of the planet.

Yes, 0.1% is better than 0.5%. But still gives up to 1.5 yards error on the mile.

Peter Larsson
Helsingborg, Sweden

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-09-15 : 07:09:16

quote:
Originally posted by Kristen

Sorry MVJ, I'm struggling to believe the CPU effort [of either of those, compared to straight Pythagoras] is worth it for a "nearest store" type query.

Kristen

I wasn't trying to address the suitability to the application, especially since the poster didn't really say what the application is. For all we know, he is computing the distance of airline flights. (I hope not!)

I just wanted to show that the computation of a great circle distance can be handled accurately by SQL Server, and that there was a better method for doing the calculation.

I am aware of the limitations of the accuracy of a great circle calculation due to differences in the curvature of the Earth, differences in altitude, etc. There are methods that can be used to improve the accuracy, like using a value for the radius of the Earth that is best suited for the particular query being run.

As to CPU usage, well maybe it’s time to turn this into a testing thread! (You first

)

If the application is using this calculation only occasionally, CPU may not be much of an issue. In that case, coding for Pythagoras at short distances and great circle at longer distances may not be worth it.

CODO ERGO SUM

Kristen
Test

22859 Posts

Posted - 2006-09-15 : 07:36:00

No problem with that!

My interest would be:

If you had millions (well, "lots" anyway) of rows with Lat / Long in them, and the Lat & Long columns were indexed, what would be the most efficient way to find the "Nearest 10" objects?

Lets assume that anything further than 100 miles (or maybe 50 even) is "too far to be of any interest" - although you folk in the States would probably drive that far to pick up something useful, we in the UK would probably not!

I imagine that performing Haversine on the Lat / Long columns causing a table scan (and lots of Trig. CPU effort) is probably not the most efficient way!

Kristen

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-09-15 : 09:46:53

quote:
Originally posted by Kristen

No problem with that!

My interest would be:

If you had millions (well, "lots" anyway) of rows with Lat / Long in them, and the Lat & Long columns were indexed, what would be the most efficient way to find the "Nearest 10" objects?

Lets assume that anything further than 100 miles (or maybe 50 even) is "too far to be of any interest" - although you folk in the States would probably drive that far to pick up something useful, we in the UK would probably not!

I imagine that performing Haversine on the Lat / Long columns causing a table scan (and lots of Trig. CPU effort) is probably not the most efficient way!

Kristen

I wouldn't do it that way for the initial lookup.

I would want to do an indexed lookup using the method of a "square" around the circle, and do distance calculation on that result set only.

By square around the circle, I mean calculate a max/min longitude and latitude that defines a square that holds the circle that you are really after. By chance, about 3/4 of the items within that square will be in the target circle. Doing the distance calculation on this much smaller result set would be much less CPU intensive.

Of course, this method is not valid if you are very near the north or south poles, but until they build the South Pole Mall, it should be OK.


-- Initial Query
select
	*
from
	MyStores
where
	MyStoreLat between @MaxLat and @MinLat and
	MyStoreLon between @MaxLon and @MinLon

CODO ERGO SUM

Kristen
Test

22859 Posts

Posted - 2006-09-15 : 12:51:18

Yup, I've used the square-circle approach before - but only when I wanted "All stores within N miles" (actually it was Dates! but you get the idea)

But if I wanted just the TOP 10, regardless of distance but considering that a sensible driving limit would be involved, what's my best way to do that?

If I order by the Sum of the Squares of the Lat and Log differences, respectively, am I going to get any help from an index on Lat / Long?

If not the key is to have a "reasonable" distance limit and select a Square Circle for starters, and hope it hasn't got too many results in it.

Could I get a first-cut using just the Difference of the Lat & Long, rather than the Squares? (I'm trying to get the index cover you see ...):
[code]
select TOP 100 MyID
from MyStores
where MyStoreLat >= @MyLat
ORDER BY MyStoreLat ASC

UNION ALL

select TOP 100 MyID
from MyStores
where MyStoreLat < @MyLat
ORDER BY MyStoreLat DESC

UNION ALL

... repeat for MyStoreLong

(The ORDER BY within each UNION-able piece is going to need work/nesting, of course!!)

So now I have got the ID of 400 rows (possibly including some duplicates) of things that are close in at least one plane, hopefully having fully utilised the Index, and I can further-process those with Haversine or whatever?

I'm banking on the closest object having the smallest either Lat or Long (but not necessarily both), but I can't quite get my head around whether that hypothesis is correct!

Kristen

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-09-15 : 13:33:28

I would just go with the square circle, compute the distance, and then order by distance to select the top N. If you have good indexes, the initial query for the square circle should be fast.

I don't see any reason to complicate it too much. The initial query will probably return a small result set for most typical applications: Show me all the service centers within 20 miles, show me all stores within 50 miles that sell a product, show me the 5 closest Wal-Marts within 20 miles, etc.

CODO ERGO SUM

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources