High precision doubles

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Aaron MacDonald
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
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Andrew Hunter-3
On Wed, Jun 24, 2009 at 08:46:04PM -0300, Aaron MacDonald wrote:
> Is there anything in Haskell that can represent doubles with higher
>                                                 ^^^^^^^

No, I'm pretty sure "double precision" will be double precision
everywhere (systems not supporting IEEE-754 notwithstanding.)  Want to
represent floating point numbers more precisely?  That's feasible.

> 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?
>

Some systems have support for "long doubles", typically an 80-bit type
on x86; I don't know if Haskell provides any access to this.  I doubt
it.  If you want a more sledgehammerish approach, packages like HMPFR:

http://hackage.haskell.org/package/hmpfr

can provide arbitrary precision calculations.  They're slow, though.  

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?

For way more information, consult "What Every Computer Scientist
Should Know About Floating-Point Arithmetic."

http://docs.sun.com/source/806-3568/ncg_goldberg.html

HTH,
AHH
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Aaron MacDonald

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.
Reply | Threaded
Open this post in threaded view
|

High precision doubles

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090624/f275bdb5/attachment.html
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Daniel Fischer-4
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.
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Rafael Gustavo da Cunha Pereira Pinto-2
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) <epsilon


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090625/01e28f93/attachment-0001.html
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Rafael Gustavo da Cunha Pereira Pinto-2
oops:

Relative exit condition (valid only when dealing with non-zero values)

abs ((xold-xnew)/xnew) <epsilon



On Thu, Jun 25, 2009 at 10:24, Rafael Gustavo da Cunha Pereira Pinto <
[hidden email]> 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) <epsilon
>
>
> 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
Reply | Threaded
Open this post in threaded view
|

High precision doubles

ajb@spamcop.net
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
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Rafael Gustavo da Cunha Pereira Pinto-2
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
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Matthew Eastman
In reply to this post by Aaron MacDonald
This is a coincidence. I just finished writing a hexagonal (and  
square) maze generator.

I used Wilson's algorithm, which builds a spanning tree by performing  
a random walk from each cell not in the maze until it reaches a cell  
that is in the maze. It then adds the path and goes at it again until  
every cell is in the maze.

If you're using a grid, even one without bounds, it makes sense to use  
integer coordinates and map them to floating point when you need to,  
like some others have suggested.

The grid I used looked something like this:
      ___     ___
  ___/   \___/   \___
/   \___/   \___/   \
\___/2,2\___/   \___/
/1,2\___/3,2\___/   \
\___/2,1\___/   \___/
/1,1\___/3,1\___/   \
\___/   \___/   \___/

It would work with negative numbers as well, if you need the grid to  
be able to expand in every direction.

You move north, south, east, or west by adding to or subtracting from  
the x and y co-ordinates.
If the x coordinate is even, you add 1 to y when you move north-east  
or north-west.
If the x coordinate is odd, you subtract 1 from y when you move south-
east or south-west.

Then when you're testing whether a cell is in your maze you just need  
to check the (x,y) integer pair and not have to worry about floating  
point precision, and you can get all the cells adjacent to a specific  
cell by adding to and subtracting from the x or y value of a cell.

I found it easier to keep track of which walls each cell has instead  
of which cells it's adjacent to, but either one works.

Just for fun, one of the mazes it made:

      ___     ___     ___     ___     ___
  ___/   \___/   \___/   \___/   \___/   \___
/   \       \   /       /       /   \       \
\       \___/    ___/    ___/       /   \   /
/   \___/    ___    \       \___/   \   /   \
\   /   \___/   \   /   \   /   \___    \   /
/       /    ___/   \___/    ___    \___/   \
\___/       /   \___    \___/   \___    \   /
/   \   /            ___     ___/   \___/   \
\___    \___/   \       \   /            ___/
/    ___    \___/   \___/   \___/   \___    \
\___/   \___/   \___/   \___/   \___/   \___/

On 24-Jun-09, at 10:10 PM, Aaron MacDonald wrote:

>
> 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.
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners

Reply | Threaded
Open this post in threaded view
|

High precision doubles

Felipe Lessa
On Sun, Jun 28, 2009 at 10:34:51PM -0400, Matthew Eastman wrote:

> Just for fun, one of the mazes it made:
>
>      ___     ___     ___     ___     ___
>  ___/   \___/   \___/   \___/   \___/   \___
> /   \       \   /       /       /   \       \
> \       \___/    ___/    ___/       /   \   /
> /   \___/    ___    \       \___/   \   /   \
> \   /   \___/   \   /   \   /   \___    \   /
> /       /    ___/   \___/    ___    \___/   \
> \___/       /   \___    \___/   \___    \   /
> /   \   /            ___     ___/   \___/   \
> \___    \___/   \       \   /            ___/
> /    ___    \___/   \___/   \___/   \___    \
> \___/   \___/   \___/   \___/   \___/   \___/

This is beautiful!  Do you plan releasing something to Hackage?

--
Felipe.
Reply | Threaded
Open this post in threaded view
|

High precision doubles

Matthew Eastman
Sure, I can put it on Hackage. I'll have to figure out how to use  
Cabal, and tidy up the code, but I'll upload it sooner or later.

On 28-Jun-09, at 10:55 PM, Felipe Lessa wrote:

> On Sun, Jun 28, 2009 at 10:34:51PM -0400, Matthew Eastman wrote:
>> Just for fun, one of the mazes it made:
>>
>>     ___     ___     ___     ___     ___
>> ___/   \___/   \___/   \___/   \___/   \___
>> /   \       \   /       /       /   \       \
>> \       \___/    ___/    ___/       /   \   /
>> /   \___/    ___    \       \___/   \   /   \
>> \   /   \___/   \   /   \   /   \___    \   /
>> /       /    ___/   \___/    ___    \___/   \
>> \___/       /   \___    \___/   \___    \   /
>> /   \   /            ___     ___/   \___/   \
>> \___    \___/   \       \   /            ___/
>> /    ___    \___/   \___/   \___/   \___    \
>> \___/   \___/   \___/   \___/   \___/   \___/
>
> This is beautiful!  Do you plan releasing something to Hackage?
>
> --
> Felipe.
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners