slowness of GMP rational numbers in computers

so over here https://github.com/openscad/openscad/issues/265

Giles Bathgate links to a CGAL computer math/geometry video here: http://www.youtube.com/watch?v=3DLfkWWw_Tg

 

Now that comment thread is way off topic so i wont post there. But I will post here!

The video leaves out some details.

One of the main reasons libGMP rationals are slow because GMP does a reduction after every rational operation. For example, if you multiply 3/24 * 2/24, you get 6/24. GMP will then reduce it to 1/4, putting it in lowest terms. This means GMP has to factorize both the top and bottom integer. After every add, every subtract, every multiply, every division.

https://gmplib.org/manual/Rational-Number-Functions.html

This is not strictly necessary for every algorithm using rationals. (I think GMP source code or manual might even say this)

I would wager there are algorithms to solve some problems in geometry that dont need to do a GCD reduction-to-lowest-terms at every step of the process.

Giles mentions Generic Programming and the highly templated nature of CGAL. and one of its costs.

 

The other cost of the generic programming is that algorithms designed for rationals dont really work with floats. Geometry is fundamentally tied to the underlying number system it is using. http://www.cut-the-knot.org/arithmetic/rational.shtml

For example the geometry of lines (line-line intersection) is entirely doable with linear algebra, no square root required. However it supposes that the underlying number system is ‘closed under division’, that is that if you put X and Y into the phrase X/Y ,the result will still be the same type as X and Y were to begin with. This is not true of floating point! 1.0/3.0 does not produce a floating point number, it produces an infinite sequence 0.33333333…..

This is why some of the CGAL algorithms you will find have to be used quite differently under float vs rational. For example is_simple2 doesnt work right with float coordinates (if i remember correctly?).

 

Advertisements

About donbright

don bright http://github.com/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s