# High precision doubles

12 messages
Open this post in threaded view
|

## High precision doubles

 Is there anything in Haskell that can represent doubles with higher   precision than the regular kind? I'm working with formulas that   generate sets of values, and values that I know should be zero are   ending up as things like -7.105427357601002e-15 or   -1.7763568394002505e-14, which is causing all kinds of butterfly   effects. I've heard of Rational, but I need to also work with irrational   numbers (namely, pi and anything that comes from cos and sin). What   other options do I have? - Aaron
Open this post in threaded view
|

## High precision doubles

Open this post in threaded view
|

## High precision doubles

 On 24-Jun-09, at 10:18 PM, Andrew Hunter wrote: > More to the point, however: you don't want more precision.  Welcome to > the world of numerical algorithms; floating point arithmetic is > inherently inexact.  Get used to it.  For example, I'll bet your > errors are caused by testing for equality against zero, and if I had > to guess, you're probably trying to terminate a procedure when some > value hits zero?  It's not going to; you need to introduce the concept > of tolerances, and accept if |val| < tol.  This is a simplistic > solution and not really right in most cases, but might help.  If you > want more advice about how to handle floating-point inaccuracy, could > you provide a program and what's going wrong? What I'm specifically working on is a maze generator.  The generator   is based on Prim's algorithm: starting with a graph containing a   single node, I connect new nodes to existing nodes that are not   surrounded yet until I've reached a specified number of nodes in the   graph. In my case, the maze is on a hexagonal grid.  There are no boundaries   around the maze, so the generator may attach hexagonal cells, or   nodes, from any side (I don't particularly care if the generator   sometimes makes one long hallway).  Each hexagonal cell is represented   in the graph as a co-ordinate representing the cell's centre.  I have   a function that takes a co-ordinate and returns a list of co-ordinates   representing the centres of the adjacent cells. Keeping track of the   hexagons' positions is important because these mazes will be levels   for a game I hope to somehow put together; the potions would be used   for drawing the maze and for AI pathfinding. When adding a new node/hex to the graph/maze, I pick an existing node   and get all of its neighbour co-ordinates, filtering out co-ordinates   that represent nodes already present in the graph. The problem is   that, due to floating point errors, these co-ordinates are not be   exact. If hex A has the co-ordinate for hex B in its list of adjacent   hexes, hex B would not necessarily have the co-ordinate for hex A in   its own list. Things get mismatched quickly.
Open this post in threaded view
|

## High precision doubles

 > > When adding a new node/hex to the graph/maze, I pick an existing node and > get all of its neighbour co-ordinates, filtering out co-ordinates that > represent nodes already present in the graph. The problem is that, due to > floating point errors, these co-ordinates are not be exact. If hex A has the > co-ordinate for hex B in its list of adjacent hexes, hex B would not > necessarily have the co-ordinate for hex A in its own list. Things get > mismatched quickly. You won't be able to get it working easily with floating-point numbers. Ideally, you would use integers for the code you're describing, then scale them to the proper floating-point values later. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090624/f275bdb5/attachment.html
Open this post in threaded view
|

## High precision doubles

 Am Donnerstag 25 Juni 2009 04:14:19 schrieb Sean Bartell: > > When adding a new node/hex to the graph/maze, I pick an existing node and > > get all of its neighbour co-ordinates, filtering out co-ordinates that > > represent nodes already present in the graph. The problem is that, due to > > floating point errors, these co-ordinates are not be exact. If hex A has > > the co-ordinate for hex B in its list of adjacent hexes, hex B would not > > necessarily have the co-ordinate for hex A in its own list. Things get > > mismatched quickly. > > You won't be able to get it working easily with floating-point numbers. > Ideally, you would use integers for the code you're describing, then scale > them to the proper floating-point values later. Say the hexagons have side length 2, the centre of one is at (0,0) and one of its vertices at (2,0). Then the centre of any hexagon has coordinates (3*k,m*sqrt 3), for some integers k, m and any vertex has coordinates (i,j*sqrt 3) for integers i, j. So in this case, he could work with floating point values; using a large tolerance, he could build a gigantic grid before having false results. But of course, it is much better to use (k,m), resp. (i,j), as coordinates and translate that to floating point only for drawing.
Open this post in threaded view
|

## High precision doubles

 I am reading this and still don't understand what is the question. You should never operate two floating point numbers expecting to result zero. Period. Floating point numbers are intrinsically imprecise. Every time you write an interactive process with floating points in the exit conditions, you should use some tolerance, either relative or absolute. Absolute exit condition: abs (xnew - xold) < epsilon Relative exit condition (valid only when dealing with non-zero values) abs ((xold+xnew)/xnew) wrote: > Am Donnerstag 25 Juni 2009 04:14:19 schrieb Sean Bartell: > > > When adding a new node/hex to the graph/maze, I pick an existing node > and > > > get all of its neighbour co-ordinates, filtering out co-ordinates that > > > represent nodes already present in the graph. The problem is that, due > to > > > floating point errors, these co-ordinates are not be exact. If hex A > has > > > the co-ordinate for hex B in its list of adjacent hexes, hex B would > not > > > necessarily have the co-ordinate for hex A in its own list. Things get > > > mismatched quickly. > > > > You won't be able to get it working easily with floating-point numbers. > > Ideally, you would use integers for the code you're describing, then > scale > > them to the proper floating-point values later. > > Say the hexagons have side length 2, the centre of one is at (0,0) and one > of its vertices > at (2,0). > Then the centre of any hexagon has coordinates (3*k,m*sqrt 3), for some > integers k, m and > any vertex has coordinates (i,j*sqrt 3) for integers i, j. So in this case, > he could work > with floating point values; using a large tolerance, he could build a > gigantic grid before > having false results. > > But of course, it is much better to use (k,m), resp. (i,j), as coordinates > and translate > that to floating point only for drawing. > _______________________________________________ > Beginners mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/beginners> -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090625/01e28f93/attachment-0001.html
Open this post in threaded view
|

## High precision doubles

 oops: Relative exit condition (valid only when dealing with non-zero values) abs ((xold-xnew)/xnew) wrote: > I am reading this and still don't understand what is the question. You > should never operate two floating point numbers expecting to result zero. > Period. > > Floating point numbers are intrinsically imprecise. Every time you write an > interactive process with floating points in the exit conditions, you should > use some tolerance, either relative or absolute. > > Absolute exit condition: > > abs (xnew - xold) < epsilon > > Relative exit condition (valid only when dealing with non-zero values) > > abs ((xold+xnew)/xnew) > > If you cannot apply this, then either: > > 1) You are dealing with VERY small values, close to the minimal precision > (2.2250738585072014e-308, on 64-bit doubles), > > 2) You are dealing with small and big numbers, differing by 37 orders of > magnitude amongst them, when the small number will be set to 0 > > To solve this you should: > > for 1) Scale your numbers... double, multiply by 1024, whatever, as long as > they separate from the minimal precision. It is like putting your maze under > a HUGE microscope! > > for 2) Addition in situations as this one is like adding a pinch of salt on > the ocean. For multiplications, try using Log-domain operations... That > might work... Praying might work as well... > > > > Where epsilon is > > On Thu, Jun 25, 2009 at 09:17, Daniel Fischer <[hidden email]>wrote: > >> Am Donnerstag 25 Juni 2009 04:14:19 schrieb Sean Bartell: >> > > When adding a new node/hex to the graph/maze, I pick an existing node >> and >> > > get all of its neighbour co-ordinates, filtering out co-ordinates that >> > > represent nodes already present in the graph. The problem is that, due >> to >> > > floating point errors, these co-ordinates are not be exact. If hex A >> has >> > > the co-ordinate for hex B in its list of adjacent hexes, hex B would >> not >> > > necessarily have the co-ordinate for hex A in its own list. Things get >> > > mismatched quickly. >> > >> > You won't be able to get it working easily with floating-point numbers. >> > Ideally, you would use integers for the code you're describing, then >> scale >> > them to the proper floating-point values later. >> >> Say the hexagons have side length 2, the centre of one is at (0,0) and one >> of its vertices >> at (2,0). >> Then the centre of any hexagon has coordinates (3*k,m*sqrt 3), for some >> integers k, m and >> any vertex has coordinates (i,j*sqrt 3) for integers i, j. So in this >> case, he could work >> with floating point values; using a large tolerance, he could build a >> gigantic grid before >> having false results. >> >> But of course, it is much better to use (k,m), resp. (i,j), as coordinates >> and translate >> that to floating point only for drawing. >> _______________________________________________ >> Beginners mailing list >> [hidden email] >> http://www.haskell.org/mailman/listinfo/beginners>> > > > > -- > Rafael Gustavo da Cunha Pereira Pinto > Electronic Engineer, MSc. > -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090625/3f274a5e/attachment.html
Open this post in threaded view
|

## High precision doubles

 In reply to this post by Rafael Gustavo da Cunha Pereira Pinto-2 G'day all. Quoting Rafael Gustavo da Cunha Pereira Pinto <[hidden email]>: > I am reading this and still don't understand what is the question. You > should never operate two floating point numbers expecting to result zero. > Period. WARNING: Advanced material follows. A 32-bit integer fits losslessly in the mantissa of a Double.  Any of the basic integer operations which work correctly on 32-bit integers must also work correctly when that integer is stored in a Double.  You are allowed to assume this. Cheers, Andrew Bromage
Open this post in threaded view
|

## High precision doubles

 Point noted, it doesn't seem to be the case for the original question, as he is doing some square roots. On Fri, Jun 26, 2009 at 04:00, <[hidden email]> wrote: > G'day all. > > Quoting Rafael Gustavo da Cunha Pereira Pinto <[hidden email] > >: > >  I am reading this and still don't understand what is the question. You >> should never operate two floating point numbers expecting to result zero. >> Period. >> > > WARNING: Advanced material follows. > > A 32-bit integer fits losslessly in the mantissa of a Double.  Any of > the basic integer operations which work correctly on 32-bit integers > must also work correctly when that integer is stored in a Double.  You > are allowed to assume this. > > Cheers, > Andrew Bromage > > _______________________________________________ > Beginners mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/beginners> -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090626/7ab78cc4/attachment.html
Open this post in threaded view
|