smallest double eps

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

smallest double eps

Tamas K Papp
Hi,

Is there a built-in constant in Haskell (or, if it is
compiler-specific, in ghc) that gives the smallest positive floating
point number x such that 1+x /= x?  Some languages refer to that as
double.eps or similar.  I need it for numeric algorithms.

Thanks,

Tamas
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Joachim Breitner-2
Hi,

Am Freitag, den 29.09.2006, 19:30 -0400 schrieb Tamas K Papp:
> the smallest positive floating point number x such that 1+x /= x?
That would be the smallest positive number, woudn't it?

Do you mean the smalles postive number x with 1+x /= 1?

Greetings,
Joachim


--
Joachim Breitner
  e-Mail: [hidden email]
  Homepage: http://www.joachim-breitner.de
  ICQ#: 74513189
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Tamas K Papp
On Sat, Sep 30, 2006 at 12:20:16AM +0000, Joachim Breitner wrote:
> Hi,
>
> Am Freitag, den 29.09.2006, 19:30 -0400 schrieb Tamas K Papp:
> > the smallest positive floating point number x such that 1+x /= x?
> That would be the smallest positive number, woudn't it?
>
> Do you mean the smalles postive number x with 1+x /= 1?

Hi Joachim,

Specifically, I would be happy with the smallest Double that makes the
statement true.  I need it as a convergence bound for an iterative
algorithm.  Anyhow, thanks for the clarification, but I would be
happier with an answer.

Tamas
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Lennart Augustsson
Haskell doesn't provide such a value, but you could easily compute it  
from from the values given in the RealFloat class.  It tells you the  
base, number of digits in mantissa, etc.

As for using such an eps in a convergence test I'd be very careful.  
How do you know that your iteration doesn't make the value bounce  
back and forth with more than eps?

        -- Lennart

On Sep 29, 2006, at 20:26 , Tamas K Papp wrote:

> On Sat, Sep 30, 2006 at 12:20:16AM +0000, Joachim Breitner wrote:
>> Hi,
>>
>> Am Freitag, den 29.09.2006, 19:30 -0400 schrieb Tamas K Papp:
>>> the smallest positive floating point number x such that 1+x /= x?
>> That would be the smallest positive number, woudn't it?
>>
>> Do you mean the smalles postive number x with 1+x /= 1?
>
> Hi Joachim,
>
> Specifically, I would be happy with the smallest Double that makes the
> statement true.  I need it as a convergence bound for an iterative
> algorithm.  Anyhow, thanks for the clarification, but I would be
> happier with an answer.
>
> Tamas
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Tamas K Papp
On Fri, Sep 29, 2006 at 09:26:27PM -0400, Lennart Augustsson wrote:

> As for using such an eps in a convergence test I'd be very careful.  
> How do you know that your iteration doesn't make the value bounce  
> back and forth with more than eps?

Hi Lennart,

Thanks for the answer, I will try it.

I am not using eps, but rather a value derived from eps by analyzing
the algorithm (eg eps^0.25).  Your answer will help me calculate that
directly.

Thanks,

Tamas
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Chad Scherrer
In reply to this post by Tamas K Papp
Tamas,

You might want to read Joachim's post more carefully - he's trying to
help you, and I think he makes a good point.

-Chad

> > Am Freitag, den 29.09.2006, 19:30 -0400 schrieb Tamas K Papp:
> > > the smallest positive floating point number x such that 1+x /= x?
> > That would be the smallest positive number, woudn't it?
> >
> > Do you mean the smalles postive number x with 1+x /= 1?
>
> Hi Joachim,
>
> Specifically, I would be happy with the smallest Double that makes the
> statement true.  I need it as a convergence bound for an iterative
> algorithm.  Anyhow, thanks for the clarification, but I would be
> happier with an answer.
>
> Tamas
>
>
> ------------------------------
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> End of Haskell-Cafe Digest, Vol 37, Issue 92
> ********************************************
>


--

Chad Scherrer

"Time flies like an arrow; fruit flies like a banana" -- Groucho Marx
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Tamas K Papp
On Fri, Sep 29, 2006 at 06:53:35PM -0700, Chad Scherrer wrote:

> Tamas,
>
> You might want to read Joachim's post more carefully - he's trying to
> help you, and I think he makes a good point.

Chad,

If his point is that there is no smallest positive number, then I
think I understand it, thanks.  I should have said that I was looking
for the smallest positive number Double can represent, but thought
that was clear from the context.

If this is not his point, I'd really appreciate an explanation.

Thanks,

Tamas
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Lennart Augustsson
Hang on, hang on, now I'm getting confused.

First you asked for the smallest (positive) x such that
    1+x /= x
which is around x=4.5e15.
Then Joachim wondered if you wanted
    1+x /= 1
which is around x=2.2e-16.
But not you claim to be looking for the smallest positive number that  
a Double can represent.  Which is a totally different beast.  The  
smallest possible Double depends on if you want to accept  
denormalized numbers or not.  If you don't, then it's about x=4.5e-308.

Now what is the number you are looking for?

        -- Lennart

On Sep 29, 2006, at 22:02 , Tamas K Papp wrote:

> On Fri, Sep 29, 2006 at 06:53:35PM -0700, Chad Scherrer wrote:
>
>> Tamas,
>>
>> You might want to read Joachim's post more carefully - he's trying to
>> help you, and I think he makes a good point.
>
> Chad,
>
> If his point is that there is no smallest positive number, then I
> think I understand it, thanks.  I should have said that I was looking
> for the smallest positive number Double can represent, but thought
> that was clear from the context.
>
> If this is not his point, I'd really appreciate an explanation.
>
> Thanks,
>
> Tamas
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Tamas K Papp
On Sat, Sep 30, 2006 at 04:19:50AM -0400, Lennart Augustsson wrote:
> Hang on, hang on, now I'm getting confused.
>
> First you asked for the smallest (positive) x such that
>    1+x /= x
> which is around x=4.5e15.
> Then Joachim wondered if you wanted
>    1+x /= 1
> which is around x=2.2e-16.

Oops, sorry, there was a typo in my original post.  I was looking for
the latter.

Thanks for the help,

Tamas
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Chad Scherrer
In reply to this post by Tamas K Papp
>
> Hang on, hang on, now I'm getting confused.
>
> First you asked for the smallest (positive) x such that
>     1+x /= x
> which is around x=4.5e15.
> Then Joachim wondered if you wanted
>     1+x /= 1
> which is around x=2.2e-16.
> But not you claim to be looking for the smallest positive number that
> a Double can represent.  Which is a totally different beast.  The
> smallest possible Double depends on if you want to accept
> denormalized numbers or not.  If you don't, then it's about x=4.5e-308.
>
> Now what is the number you are looking for?
>
>         -- Lennart
>

This is the point I was confused about also. Joachim seemed to be
correcting what might have been a misstatement of the problem.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Brian Hulley
In reply to this post by Lennart Augustsson
Lennart Augustsson wrote:
> Hang on, hang on, now I'm getting confused.
>
> First you asked for the smallest (positive) x such that
>    1+x /= x
> which is around x=4.5e15.

1 + 0 /= 0

0 is smaller than 4.5e15

So I don't understand this at all...

Regards, Brian.
--
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Thomas Davie

On 30 Sep 2006, at 17:19, Brian Hulley wrote:

> Lennart Augustsson wrote:
>> Hang on, hang on, now I'm getting confused.
>> First you asked for the smallest (positive) x such that
>>    1+x /= x
>> which is around x=4.5e15.
>
> 1 + 0 /= 0
>
> 0 is smaller than 4.5e15
>
> So I don't understand this at all...

But then 0 isn't positive.

Bob
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Brian Hulley
Thomas Davie wrote:

> On 30 Sep 2006, at 17:19, Brian Hulley wrote:
>
>> Lennart Augustsson wrote:
>>> Hang on, hang on, now I'm getting confused.
>>> First you asked for the smallest (positive) x such that
>>>    1+x /= x
>>> which is around x=4.5e15.
>>
>> 1 + 0 /= 0
>>
>> 0 is smaller than 4.5e15
>>
>> So I don't understand this at all...
>
> But then 0 isn't positive.

Why not?
In any case every positive number nust satisfy the above inequation so what
about 0.1, which is certainly smaller than 4500000000000000?

Regards, Brian.
--
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com 

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Bryan Burgers
> >>> Hang on, hang on, now I'm getting confused.
> >>> First you asked for the smallest (positive) x such that
> >>>    1+x /= x
> >>> which is around x=4.5e15.
> >>
> >> 1 + 0 /= 0
> >>
> >> 0 is smaller than 4.5e15
> >>
> >> So I don't understand this at all...
> >
> > But then 0 isn't positive.
>
> Why not?
> In any case every positive number nust satisfy the above inequation so what
> about 0.1, which is certainly smaller than 4500000000000000?

In math, every positive number must satisfy the above inequation, that
is true. But as Chad said, the smallest number in Haskell (at least
according to my GHC, it could be different with different processors,
right?) that satisfies the equation is 2.2e-16.

> 1 + 2.2e-16 /= 1
True
> 1 + 2.2e-17 /= 1
False

This is because the Double type only holds so much precision. After
getting small enough, the type just can't hold any more precision, and
the value is essentially 0.

> last $ takeWhile (\x -> 1 + x /= 1) (iterate (/2) 1)
2.220446049250313e-16
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Brandon Moore
Bryan Burgers wrote:

>> >>> Hang on, hang on, now I'm getting confused.
>> >>> First you asked for the smallest (positive) x such that
>> >>>    1+x /= x
>> >>> which is around x=4.5e15.
>> >>
>> >> 1 + 0 /= 0
>> >>
>> >> 0 is smaller than 4.5e15
>> >>
>> >> So I don't understand this at all...
>> >
>> > But then 0 isn't positive.
>>
>> Why not?
>> In any case every positive number nust satisfy the above inequation
>> so what
>> about 0.1, which is certainly smaller than 4500000000000000?
People are confusing equality and inequality -
the nontrivial thing here is to find the smallest positive x
that satisfies the equation 1 + x == x.
> In math, every positive number must satisfy the above inequation, that
> is true. But as Chad said, the smallest number in Haskell (at least
> according to my GHC, it could be different with different processors,
> right?) that satisfies the equation is 2.2e-16.
And you've changed the subject - the stuff above was talking about
x + 1 /= x, you're demonstrating solutions to a different problem,
finding the smallest
x such that 1 + x == 1. That's the number often called epsilon.
>> 1 + 2.2e-16 /= 1
> True
>> 1 + 2.2e-17 /= 1
> False
Let's stop confusing ourselves about this.

Brandon
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Victor Bandur
In reply to this post by Tamas K Papp
-------- Forwarded Message --------
From: Victor Bandur <[hidden email]>
Reply-To: [hidden email]
To: Brandon Moore <[hidden email]>
Subject: Re: [Haskell-cafe] smallest double eps
Date: Sat, 30 Sep 2006 20:17:05 -0400

Hi all,

I'm new to this mailing list, so my response may be a little out of
place, but I think either what's being asked is what is the smallest x
such that 1 + x /= 1 (machine epsilon,) or the largest such that 1+x /=
x.  The bounds seem to be confused.

Victor

On Sat, 2006-30-09 at 16:10 -0700, Brandon Moore wrote:

> Bryan Burgers wrote:
> >> >>> Hang on, hang on, now I'm getting confused.
> >> >>> First you asked for the smallest (positive) x such that
> >> >>>    1+x /= x
> >> >>> which is around x=4.5e15.
> >> >>
> >> >> 1 + 0 /= 0
> >> >>
> >> >> 0 is smaller than 4.5e15
> >> >>
> >> >> So I don't understand this at all...
> >> >
> >> > But then 0 isn't positive.
> >>
> >> Why not?
> >> In any case every positive number nust satisfy the above inequation
> >> so what
> >> about 0.1, which is certainly smaller than 4500000000000000?
> People are confusing equality and inequality -
> the nontrivial thing here is to find the smallest positive x
> that satisfies the equation 1 + x == x.
> > In math, every positive number must satisfy the above inequation, that
> > is true. But as Chad said, the smallest number in Haskell (at least
> > according to my GHC, it could be different with different processors,
> > right?) that satisfies the equation is 2.2e-16.
> And you've changed the subject - the stuff above was talking about
> x + 1 /= x, you're demonstrating solutions to a different problem,
> finding the smallest
> x such that 1 + x == 1. That's the number often called epsilon.
> >> 1 + 2.2e-16 /= 1
> > True
> >> 1 + 2.2e-17 /= 1
> > False
> Let's stop confusing ourselves about this.
>
> Brandon
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: smallest double eps

Grady Lemoine
In reply to this post by Bryan Burgers
> > last $ takeWhile (\x -> 1 + x /= 1) (iterate (/2) 1)
> 2.220446049250313e-16

This works because of the way IEEE floating-point numbers are
represented, so it's good for the majority of machines, but it is
technically a hack, in that it depends on a representation of
floating-point numbers in some form akin to the IEEE (1.mantissa
bits)*2^(exponent).  It would be nice for those of us interested in
doing numerical work in Haskell if we could have machine epsilon
available from the language, in case we're running on a machine where
that assumption doesn't hold.  I don't know where this would belong --
the Numeric library seems mainly concerned with reading and showing
numbers, and System is more about interacting with the OS than making
statements about the properties of the underlying hardware.

--Grady Lemoine
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe