double double

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

double double

Paul Ramsey
Mats, what ever happened to:


I'm just coming up against some stuff in the JTS commit log that expects double double and I see you've done this work already some years ago, but it's not committed that I can see. JTS changed over some code to use DD exclusively about a year ago, so this is a case where porting has caught up to need.

Were there any substantial problems w/ your PR? If not I'm "just" going to try and rebase it and use it as the basis for going ahead.

(It seems like the state-of-the-art would eventually be to use the "long double" type, which has an implementation in GCC, but does not yet have one in clang, in hopes that by being close to the metal we'd eventually also start to reap performance gains as the silicon adds instructions to improve long double calculations. ???)

P.

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: double double

Martin Davis-3
And for bonus points implement a class (template? macro?) that will choose DoubleDouble or long double depending on platform...  :)

On Fri, Dec 7, 2018 at 3:29 PM Paul Ramsey <[hidden email]> wrote:
Mats, what ever happened to:


I'm just coming up against some stuff in the JTS commit log that expects double double and I see you've done this work already some years ago, but it's not committed that I can see. JTS changed over some code to use DD exclusively about a year ago, so this is a case where porting has caught up to need.

Were there any substantial problems w/ your PR? If not I'm "just" going to try and rebase it and use it as the basis for going ahead.

(It seems like the state-of-the-art would eventually be to use the "long double" type, which has an implementation in GCC, but does not yet have one in clang, in hopes that by being close to the metal we'd eventually also start to reap performance gains as the silicon adds instructions to improve long double calculations. ???)

P.
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: double double

Greg Troxel-2
In reply to this post by Paul Ramsey
Paul Ramsey <[hidden email]> writes:

> Mats, what ever happened to:
>
> https://github.com/libgeos/geos/pull/40
>
> I'm just coming up against some stuff in the JTS commit log that expects
> double double and I see you've done this work already some years ago, but
> it's not committed that I can see. JTS changed over some code to use DD
> exclusively about a year ago, so this is a case where porting has caught up
> to need.
>
> Were there any substantial problems w/ your PR? If not I'm "just" going to
> try and rebase it and use it as the basis for going ahead.
>
> (It seems like the state-of-the-art would eventually be to use the "long
> double" type, which has an implementation in GCC, but does not yet have one
> in clang, in hopes that by being close to the metal we'd eventually also
> start to reap performance gains as the silicon adds instructions to improve
> long double calculations. ???)

I don't follow this last paragraph.

As I understand it, long double is a type defined by C that can be more
precise than double, but doesn't have to be, and on x86 is typically 80
bits.  double double is a technique to use two doubles to get roughly
twice the precision.   I would expect that on many CPUs, long double is
the same as double.

So double double is far more precise than long double always.

https://en.wikipedia.org/wiki/Long_double
https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format#Double-double_arithmetic
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: double double

Darafei "Komяpa" Praliaskouski


On Sat, Dec 8, 2018 at 6:51 AM Greg Troxel <[hidden email]> wrote:
Paul Ramsey <[hidden email]> writes:

> Mats, what ever happened to:
>
> https://github.com/libgeos/geos/pull/40
>
> I'm just coming up against some stuff in the JTS commit log that expects
> double double and I see you've done this work already some years ago, but
> it's not committed that I can see. JTS changed over some code to use DD
> exclusively about a year ago, so this is a case where porting has caught up
> to need.
>
> Were there any substantial problems w/ your PR? If not I'm "just" going to
> try and rebase it and use it as the basis for going ahead.
>
> (It seems like the state-of-the-art would eventually be to use the "long
> double" type, which has an implementation in GCC, but does not yet have one
> in clang, in hopes that by being close to the metal we'd eventually also
> start to reap performance gains as the silicon adds instructions to improve
> long double calculations. ???)

I don't follow this last paragraph.

As I understand it, long double is a type defined by C that can be more
precise than double, but doesn't have to be, and on x86 is typically 80
bits.  double double is a technique to use two doubles to get roughly
twice the precision.   I would expect that on many CPUs, long double is
the same as double.

Windows defines long double to be the same as double. Java doesn't even have long double, so JTS has no choice for intermediate storage.

Redefining some intermediate variables as long double short term is a cheap gain.
Double double gives a bigger gain but is more painful.

It is not enough to be robust in all cases also though - here are Shewchuk's proved-robust predicates that have to use up to four doubles to manage long arithmetic:



If you find 512-bit float somewhere you may get away with it directly though, but I don't think they are available on consumer non-DSP CPUs.



So double double is far more precise than long double always.

https://en.wikipedia.org/wiki/Long_double
https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format#Double-double_arithmetic
_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel


--
Darafei Praliaskouski

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: double double

Martin Davis-3


It is not enough to be robust in all cases also though - here are Shewchuk's proved-robust predicates that have to use up to four doubles to manage long arithmetic:



If you find 512-bit float somewhere you may get away with it directly though, but I don't think they are available on consumer non-DSP CPUs.

JTS now uses DoubleDouble and Shewchuk's adaptive approach to compute the critical orientation predicate [1].  This solved some long-standing and subtle problems with the previously-used Robust Determinant algorithm  So I'd recommend GEOS switch to using it (unless the performance is a real issue).

AFAIK double-double precision is sufficient for robust evaluation of orientation.  Seems to work well, anyway.  

JTS also has a DoubleDouble-based function for computing the intersection point of two segments, but this isn't yet used as the main intersection function (not sure why not - maybe I just didn't quite get there.  It would be nice to use it as it's a lot simpler than the normalization approach now used.  But probably worth checking it it impacts performance.

There's also a DoubleDouble incircle predicate [2], which is not currently in the mainline, but probably should be (I think there were some known failure cases of the other code).



 

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel