harry | 16 Jun 09:26 2013
Picon

Proposal: Warn when using Enum instance of Float or Double

The Enum instances for Float and Double have dubious semantics which cause
endless confusion, e.g.
http://stackoverflow.com/questions/13203471/the-math-behind-1-0999999999999999-in-haskell,
http://stackoverflow.com/questions/9810002/floating-point-list-generator,
http://stackoverflow.com/questions/7290438/haskell-ranges-and-floats,
http://stackoverflow.com/questions/10328435/how-to-solve-floating-point-number-getting-wrong-in-list-haskell,
and many more.

I would therefore like to propose that the usage of an Enum instance of
Float or Double generate a compiler warning, such as "The Enum instance of
Float is subject to rounding errors". Deadline: 2 weeks.

Pedantic question: Should it be the Enum instance _of_ Float or _for_ Float?

--
View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance-of-Float-or-Double-tp5731620.html
Sent from the Haskell - Libraries mailing list archive at Nabble.com.
wren ng thornton | 16 Jun 09:32 2013

Re: Proposal: Warn when using Enum instance of Float or Double

On 6/16/13 3:26 AM, harry wrote:
> The Enum instances for Float and Double have dubious semantics which cause
> endless confusion, e.g.
> http://stackoverflow.com/questions/13203471/the-math-behind-1-0999999999999999-in-haskell,
> http://stackoverflow.com/questions/9810002/floating-point-list-generator,
> http://stackoverflow.com/questions/7290438/haskell-ranges-and-floats,
> http://stackoverflow.com/questions/10328435/how-to-solve-floating-point-number-getting-wrong-in-list-haskell,
> and many more.
>
> I would therefore like to propose that the usage of an Enum instance of
> Float or Double generate a compiler warning, such as "The Enum instance of
> Float is subject to rounding errors". Deadline: 2 weeks.

+1.

> Pedantic question: Should it be the Enum instance _of_ Float or _for_
Float?

"for".

--

-- 
Live well,
~wren
Henning Thielemann | 16 Jun 11:12 2013
Picon

Re: Proposal: Warn when using Enum instance of Float or Double


On Sun, 16 Jun 2013, harry wrote:

> The Enum instances for Float and Double have dubious semantics which cause
> endless confusion, e.g.
> http://stackoverflow.com/questions/13203471/the-math-behind-1-0999999999999999-in-haskell,
> http://stackoverflow.com/questions/9810002/floating-point-list-generator,
> http://stackoverflow.com/questions/7290438/haskell-ranges-and-floats,
> http://stackoverflow.com/questions/10328435/how-to-solve-floating-point-number-getting-wrong-in-list-haskell,
> and many more.
>
> I would therefore like to propose that the usage of an Enum instance of
> Float or Double generate a compiler warning, such as "The Enum instance of
> Float is subject to rounding errors". Deadline: 2 weeks.

I would also like to see these instances be removed or deprecated. 
Unfortunately, GHC currently does not allow to DEPRECATE an instance. With 
this feature one might also tag intentionally omitted instances, like Num 
instance for (or 'of' :-) functions:
    http://hackage.haskell.org/trac/ghc/ticket/7775
Simon Peyton-Jones | 17 Jun 09:59 2013
Picon

RE: Proposal: Warn when using Enum instance of Float or Double

I don't think it would be that hard to add DEPRECATE for instances.  A bit fiddly, and what should the syntax
be.. but not really hard.  I can offer advice if someone wants to undertake it.

It's a cost/benefit question: how often will it be used?

Simon

| -----Original Message-----
| From: libraries-bounces <at> haskell.org [mailto:libraries-
| bounces <at> haskell.org] On Behalf Of Henning Thielemann
| Sent: 16 June 2013 10:12
| To: harry
| Cc: libraries <at> haskell.org
| Subject: Re: Proposal: Warn when using Enum instance of Float or Double
| 
| 
| On Sun, 16 Jun 2013, harry wrote:
| 
| > The Enum instances for Float and Double have dubious semantics which
| cause
| > endless confusion, e.g.
| > http://stackoverflow.com/questions/13203471/the-math-behind-1-
| 0999999999999999-in-haskell,
| > http://stackoverflow.com/questions/9810002/floating-point-list-
| generator,
| > http://stackoverflow.com/questions/7290438/haskell-ranges-and-floats,
| > http://stackoverflow.com/questions/10328435/how-to-solve-floating-
| point-number-getting-wrong-in-list-haskell,
| > and many more.
| >
(Continue reading)

harry | 17 Jun 11:04 2013
Picon

RE: Proposal: Warn when using Enum instance of Float or Double

Simon Peyton-Jones wrote
> I don't think it would be that hard to add DEPRECATE for instances.  A bit
> fiddly, and what should the syntax be.. but not really hard.  I can offer
> advice if someone wants to undertake it.

The instances in question are part of prelude - could they be deprecated by
GHC before haskell' deprecates them in a future language standard?

--
View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance-of-Float-or-Double-tp5731620p5731684.html
Sent from the Haskell - Libraries mailing list archive at Nabble.com.
harry | 17 Jun 11:09 2013
Picon

RE: Proposal: Warn when using Enum instance of Float or Double

Simon Peyton-Jones wrote
> I don't think it would be that hard to add DEPRECATE for instances.  A bit
> fiddly, and what should the syntax be.. but not really hard.  I can offer
> advice if someone wants to undertake it.
> 
> It's a cost/benefit question: how often will it be used?

I've already proposed deprecation to prime, but they probably aren't going
to do it unless GHC can actually implement said deprecation.

In response to "how often will it be used", would it assist with changes to
the class hierarchy?

--
View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance-of-Float-or-Double-tp5731620p5731685.html
Sent from the Haskell - Libraries mailing list archive at Nabble.com.
Roman Cheplyaka | 16 Jun 23:33 2013

Re: Proposal: Warn when using Enum instance of Float or Double

Hi,

This is the mailing list for libraries changes proposals.

What's the library you're proposing a change to, and what is the change
itself?

In other words, let's say your proposal gets accepted — what's next?

Roman

* harry <voldermort <at> hotmail.com> [2013-06-16 00:26:05-0700]
> The Enum instances for Float and Double have dubious semantics which cause
> endless confusion, e.g.
> http://stackoverflow.com/questions/13203471/the-math-behind-1-0999999999999999-in-haskell,
> http://stackoverflow.com/questions/9810002/floating-point-list-generator,
> http://stackoverflow.com/questions/7290438/haskell-ranges-and-floats,
> http://stackoverflow.com/questions/10328435/how-to-solve-floating-point-number-getting-wrong-in-list-haskell,
> and many more.
> 
> I would therefore like to propose that the usage of an Enum instance of
> Float or Double generate a compiler warning, such as "The Enum instance of
> Float is subject to rounding errors". Deadline: 2 weeks.
> 
> Pedantic question: Should it be the Enum instance _of_ Float or _for_ Float?
> 
> 
> 
> 
> --
(Continue reading)

harry | 17 Jun 09:16 2013
Picon

Re: Proposal: Warn when using Enum instance of Float or Double

Roman Cheplyaka-2 wrote
> Hi,
> 
> This is the mailing list for libraries changes proposals.
> 
> What's the library you're proposing a change to, and what is the change
> itself?
> 
> In other words, let's say your proposal gets accepted — what's next?
> 
> Roman

This is really more of a compiler change, but when I've submitted such
proposals through GHC's trac in the past, I was directed to move it to the
libraries list.

OTOH, one possible implementation is that GHC will add a pragma allowing for
warnings to be attached to usages of specific instances, in which case it
really is a library change as well.

--
View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance-of-Float-or-Double-tp5731620p5731677.html
Sent from the Haskell - Libraries mailing list archive at Nabble.com.

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
harry | 24 Jun 10:18 2013
Picon

Re: Proposal: Warn when using Enum instance of Float or Double

Coming to the end of the discussion period, and given that
- Deprecation isn't an option, because this is part of the Haskell report
- The libraries submission process is the correct place for this
can this be considered a consensus in favour?

--
View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance-of-Float-or-Double-tp5731620p5732003.html
Sent from the Haskell - Libraries mailing list archive at Nabble.com.
Edward A Kmett | 24 Jun 18:37 2013
Picon

Re: Proposal: Warn when using Enum instance of Float or Double

Right now, I'd view it as consensus that it is out of scope for the libraries <at>  process without such a
capability in any existing compiler to make it work.

On Jun 24, 2013, at 4:18 AM, harry <voldermort <at> hotmail.com> wrote:

> Coming to the end of the discussion period, and given that
> - Deprecation isn't an option, because this is part of the Haskell report
> - The libraries submission process is the correct place for this
> can this be considered a consensus in favour?
> 
> 
> 
> --
> View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance-of-Float-or-Double-tp5731620p5732003.html
> Sent from the Haskell - Libraries mailing list archive at Nabble.com.
> 
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
Twan van Laarhoven | 5 Jul 15:50 2013
Picon

Proposal: fix Enum Double instance

Hello All,

I would like to make a counterproposal in the Enum Double debate: Instead of 
deprecating or removing the instances, how about just fixing them?

A perfect instance for Enum Double is not possible, because arithmetic is 
inexact. But you can actually get awfully close. I.e. instead of allowing the 
final value to be at most step/2 past the end, we can allow it to be at most 
about 2e-16*step past the end. In many practical applications this is close 
enough to not be a problem.

Now for some more detail on the design:

* First of all, Haskell's enumFromThenTo is stupid, because calculating 
step=then-from destroys numerical accuracy. So I will focus on implementing a 
function enumFromStepTo. You can still implement enumFromThenTo on top of it. 
But it might also make sense to expose enumFromStepTo.

* It is possible to write an exact instance for Rational. It is IMO unacceptable 
that Haskell currently does not use this correct instance. I will use this 
Rational instance as a baseline for comparison.

     instance EnumFromStepTo Rational where
       enumFromStepTo f s t
         | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
         | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
         | otherwise = []

* Writing a loop naively, by recursing with from' = from+step will result in 
accumulating the error of the addition. On the other hand, Doubles can represent 
(Continue reading)

Felipe Almeida Lessa | 5 Jul 18:14 2013
Picon

Re: Proposal: fix Enum Double instance

+1, it can't get better than this.

On Fri, Jul 5, 2013 at 10:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
> Hello All,
>
>
> I would like to make a counterproposal in the Enum Double debate: Instead of
> deprecating or removing the instances, how about just fixing them?
>
> A perfect instance for Enum Double is not possible, because arithmetic is
> inexact. But you can actually get awfully close. I.e. instead of allowing
> the final value to be at most step/2 past the end, we can allow it to be at
> most about 2e-16*step past the end. In many practical applications this is
> close enough to not be a problem.
>
>
>
> Now for some more detail on the design:
>
> * First of all, Haskell's enumFromThenTo is stupid, because calculating
> step=then-from destroys numerical accuracy. So I will focus on implementing
> a function enumFromStepTo. You can still implement enumFromThenTo on top of
> it. But it might also make sense to expose enumFromStepTo.
>
> * It is possible to write an exact instance for Rational. It is IMO
> unacceptable that Haskell currently does not use this correct instance. I
> will use this Rational instance as a baseline for comparison.
>
>     instance EnumFromStepTo Rational where
>       enumFromStepTo f s t
(Continue reading)

Ivan Lazar Miljenovic | 6 Jul 01:30 2013
Picon

Re: Proposal: fix Enum Double instance

Also +1 from me, including exporting enumFromStepTo (I typically want
this a lot more than enumFromThenTo, and having to calculate what the
"then" value is tends to get rather tedious).

On 6 July 2013 02:14, Felipe Almeida Lessa <felipe.lessa <at> gmail.com> wrote:
> +1, it can't get better than this.
>
> On Fri, Jul 5, 2013 at 10:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
>> Hello All,
>>
>>
>> I would like to make a counterproposal in the Enum Double debate: Instead of
>> deprecating or removing the instances, how about just fixing them?
>>
>> A perfect instance for Enum Double is not possible, because arithmetic is
>> inexact. But you can actually get awfully close. I.e. instead of allowing
>> the final value to be at most step/2 past the end, we can allow it to be at
>> most about 2e-16*step past the end. In many practical applications this is
>> close enough to not be a problem.
>>
>>
>>
>> Now for some more detail on the design:
>>
>> * First of all, Haskell's enumFromThenTo is stupid, because calculating
>> step=then-from destroys numerical accuracy. So I will focus on implementing
>> a function enumFromStepTo. You can still implement enumFromThenTo on top of
>> it. But it might also make sense to expose enumFromStepTo.
>>
>> * It is possible to write an exact instance for Rational. It is IMO
(Continue reading)

Evan Laforge | 6 Jul 06:18 2013
Picon

Re: Proposal: fix Enum Double instance

+1 from me too, as I mentioned on the other thread, I switched to
using my own equivalent of enumFromStepTo years ago.

On Fri, Jul 5, 2013 at 4:30 PM, Ivan Lazar Miljenovic
<ivan.miljenovic <at> gmail.com> wrote:
> Also +1 from me, including exporting enumFromStepTo (I typically want
> this a lot more than enumFromThenTo, and having to calculate what the
> "then" value is tends to get rather tedious).
>
> On 6 July 2013 02:14, Felipe Almeida Lessa <felipe.lessa <at> gmail.com> wrote:
>> +1, it can't get better than this.
>>
>> On Fri, Jul 5, 2013 at 10:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
>>> Hello All,
>>>
>>>
>>> I would like to make a counterproposal in the Enum Double debate: Instead of
>>> deprecating or removing the instances, how about just fixing them?
>>>
>>> A perfect instance for Enum Double is not possible, because arithmetic is
>>> inexact. But you can actually get awfully close. I.e. instead of allowing
>>> the final value to be at most step/2 past the end, we can allow it to be at
>>> most about 2e-16*step past the end. In many practical applications this is
>>> close enough to not be a problem.
>>>
>>>
>>>
>>> Now for some more detail on the design:
>>>
>>> * First of all, Haskell's enumFromThenTo is stupid, because calculating
(Continue reading)

Carter Schonwald | 6 Jul 07:09 2013
Picon

Re: Proposal: fix Enum Double instance

+1 from me, I always think in terms of start, delta step, end anyways, this is definite a more natural api surface, as well as making the floating point story much saner. 


On Sat, Jul 6, 2013 at 12:18 AM, Evan Laforge <qdunkan <at> gmail.com> wrote:
+1 from me too, as I mentioned on the other thread, I switched to
using my own equivalent of enumFromStepTo years ago.

On Fri, Jul 5, 2013 at 4:30 PM, Ivan Lazar Miljenovic
<ivan.miljenovic <at> gmail.com> wrote:
> Also +1 from me, including exporting enumFromStepTo (I typically want
> this a lot more than enumFromThenTo, and having to calculate what the
> "then" value is tends to get rather tedious).
>
> On 6 July 2013 02:14, Felipe Almeida Lessa <felipe.lessa <at> gmail.com> wrote:
>> +1, it can't get better than this.
>>
>> On Fri, Jul 5, 2013 at 10:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
>>> Hello All,
>>>
>>>
>>> I would like to make a counterproposal in the Enum Double debate: Instead of
>>> deprecating or removing the instances, how about just fixing them?
>>>
>>> A perfect instance for Enum Double is not possible, because arithmetic is
>>> inexact. But you can actually get awfully close. I.e. instead of allowing
>>> the final value to be at most step/2 past the end, we can allow it to be at
>>> most about 2e-16*step past the end. In many practical applications this is
>>> close enough to not be a problem.
>>>
>>>
>>>
>>> Now for some more detail on the design:
>>>
>>> * First of all, Haskell's enumFromThenTo is stupid, because calculating
>>> step=then-from destroys numerical accuracy. So I will focus on implementing
>>> a function enumFromStepTo. You can still implement enumFromThenTo on top of
>>> it. But it might also make sense to expose enumFromStepTo.
>>>
>>> * It is possible to write an exact instance for Rational. It is IMO
>>> unacceptable that Haskell currently does not use this correct instance. I
>>> will use this Rational instance as a baseline for comparison.
>>>
>>>     instance EnumFromStepTo Rational where
>>>       enumFromStepTo f s t
>>>         | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
>>>         | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
>>>         | otherwise = []
>>>
>>> * Writing a loop naively, by recursing with from' = from+step will result in
>>> accumulating the error of the addition. On the other hand, Doubles can
>>> represent integer numbers exactly up to 2^53, so it is better to use values
>>> from+i*step.
>>>
>>> * Assume for simplicity that step>0. The stopping condition will then be of
>>> the form  from+i*step-to > 0. When this quantity is 0 then the final value
>>> should be included, otherwise it shouldn't be.
>>>
>>> * Now for an error analysis. Assume that we start with
>>>    f,s,t :: Rational
>>>   and call
>>>    let f' = fromRational f
>>>    let s' = fromRational s
>>>    let t' = fromRational t
>>>    enumFromThenTo f' s' t'
>>>
>>>  The fromRational function rounds a rational number to the nearest
>>> representable Double. The relative error in f' is therefore bounded by abs
>>> (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two
>>> adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the
>>> result of an addition or multiplication operation will also be rounded to
>>> the nearest representable Double.
>>>
>>>  So, the total error in our stopping condition is bounded by
>>>  err(f+i*s-t)
>>>    ≤ ε * abs f             -- representing f
>>>    + ε * i * abs s         -- representing s, amplified by i
>>>    + ε * i * abs s         -- error in calculating (*), i * s
>>>    + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
>>>    + ε * abs t             -- representing t
>>>    + ε * abs (f + i*s - t) -- error in calculating (-)
>>>
>>>  Note that the last term of the bound is the thing we are bounding. So we
>>> can handle that by picking a slightly larger epsilon, eps = ε/(1-ε).
>>>
>>>  This leads to the following implementation of enumFromStepTo:
>>>
>>>     enumFromStepToEps eps !f !s !t = go 0
>>>       where
>>>       go i
>>>         | s >= 0 && x <= t = x : go (i+1)
>>>         | s <  0 && x >= t = x : go (i+1)
>>>         | abs (x - t) < eps * bound = [x]
>>>         | otherwise = []
>>>         where
>>>         x = f + i * s
>>>         bound = abs f + 2 * abs (i * s) + abs t + abs x
>>>
>>>   with eps = 1.12e-16 :: Double
>>>   or   eps = 5.97e-8 :: Float
>>>
>>> I have done extensive experiments with this implementation and many
>>> variants, and I believe it will work in all cases.
>>>
>>> Now for enumFromTo, i.e. step=1 we could make a special case, since we know
>>> that step is exactly equal to 1, so there is no representation error. We
>>> could get rid of the multiplication, and replace i*s by 0 in the error
>>> calculation.
>>>
>>> Another issue that remains is enumFromThenTo. If we take
>>>   step = then - from
>>> then the relative error in step is bounded by
>>>   |step' - step| ≤ ε * (|then| + |from| + |then - from|).
>>> This error gets multiplied by i, so it can unfortunately become quite large.
>>>
>>> I think it would be best if we use the more general
>>>
>>>     enumFromStepToEps' !eps !f !s !sErr !t = go 0
>>>       where
>>>       go i
>>>         | s >= 0 && x <= t = x : go (i+1)
>>>         | s <  0 && x >= t = x : go (i+1)
>>>         | abs (x - t) < eps * bound = [x]
>>>         | otherwise = []
>>>         where
>>>         x = f + i * s
>>>         bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x
>>>
>>>    enumFromStepTo f s t = enumFromStepToEps' eps f s s t
>>>    enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
>>>    enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
>>>                               (abs h + abs f + abs (h - f)) t
>>>
>>>
>>> I have also looked at what other language implementations do. So far I have
>>> found that:
>>>  * Octave uses a similar method, with the bound
>>>      3 * double_epsilon * max (abs x) (abs t),
>>>    which is less tight than my bound.
>>>    see
>>> http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525
>>>
>>>  * numpy just uses an array with length ceil((to-from)/step)
>>>    see
>>> https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
>>>    It therefore suffers from numerical inaccuracies:
>>>    $ python
>>>    >>> from numpy import arange
>>>    >>> notone = 9/7. - 1/7. - 1/7.
>>>    >>> notone
>>>    1.0000000000000002
>>>    >>> len(arange(1,1))
>>>    0
>>>    >>> len(arange(1,notone))
>>>    1
>>>
>>>
>>> In summary:
>>>  * change Enum Rational to the always correct implementation
>>>  * change Enum Double and Enum Float to the almost-always correct
>>> implementation propose above.
>>>  * (optional) expose the enumFromStepTo function.
>>>
>>>
>>>
>>> Twan
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries <at> haskell.org
>>> http://www.haskell.org/mailman/listinfo/libraries
>>
>>
>>
>> --
>> Felipe.
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries <at> haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
>
>
>
> --
> Ivan Lazar Miljenovic
> Ivan.Miljenovic <at> gmail.com
> http://IvanMiljenovic.wordpress.com
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Henning Thielemann | 6 Jul 19:12 2013
Picon

Re: Proposal: fix Enum Double instance


On Fri, 5 Jul 2013, Twan van Laarhoven wrote:

> I would like to make a counterproposal in the Enum Double debate: Instead of 
> deprecating or removing the instances, how about just fixing them?
>
> A perfect instance for Enum Double is not possible, because arithmetic is 
> inexact. But you can actually get awfully close. I.e. instead of allowing the 
> final value to be at most step/2 past the end, we can allow it to be at most 
> about 2e-16*step past the end. In many practical applications this is close 
> enough to not be a problem.

That is, it will make problems with numerical inaccuracies more seldom, 
i.e. harder to detect?

Why is it important to use the enumFrom* functions, i.e. [x..] syntax? Why 
not using 'takeWhile (<y) $ iterate (d+) x' ?
Edward A Kmett | 7 Jul 19:17 2013
Picon

Re: Proposal: fix Enum Double instance

+1 from me. 

The massive cancellation destroying significant figures of significand in enumFromThenTo has always
driven me nuts.

Sent from my iPhone

On Jul 5, 2013, at 8:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:

> Hello All,
> 
> 
> I would like to make a counterproposal in the Enum Double debate: Instead of deprecating or removing the
instances, how about just fixing them?
> 
> A perfect instance for Enum Double is not possible, because arithmetic is inexact. But you can actually
get awfully close. I.e. instead of allowing the final value to be at most step/2 past the end, we can allow it
to be at most about 2e-16*step past the end. In many practical applications this is close enough to not be a problem.
> 
> 
> 
> Now for some more detail on the design:
> 
> * First of all, Haskell's enumFromThenTo is stupid, because calculating step=then-from destroys
numerical accuracy. So I will focus on implementing a function enumFromStepTo. You can still implement
enumFromThenTo on top of it. But it might also make sense to expose enumFromStepTo.
> 
> * It is possible to write an exact instance for Rational. It is IMO unacceptable that Haskell currently
does not use this correct instance. I will use this Rational instance as a baseline for comparison.
> 
>    instance EnumFromStepTo Rational where
>      enumFromStepTo f s t
>        | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
>        | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
>        | otherwise = []
> 
> * Writing a loop naively, by recursing with from' = from+step will result in accumulating the error of the
addition. On the other hand, Doubles can represent integer numbers exactly up to 2^53, so it is better to
use values from+i*step.
> 
> * Assume for simplicity that step>0. The stopping condition will then be of the form  from+i*step-to > 0.
When this quantity is 0 then the final value should be included, otherwise it shouldn't be.
> 
> * Now for an error analysis. Assume that we start with
>   f,s,t :: Rational
>  and call
>   let f' = fromRational f
>   let s' = fromRational s
>   let t' = fromRational t
>   enumFromThenTo f' s' t'
> 
> The fromRational function rounds a rational number to the nearest representable Double. The relative
error in f' is therefore bounded by abs (f-f') ≤ ε * abs f, where ε is the half the maximum distance
between two adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the result of an addition
or multiplication operation will also be rounded to the nearest representable Double.
> 
> So, the total error in our stopping condition is bounded by
> err(f+i*s-t)
>   ≤ ε * abs f             -- representing f
>   + ε * i * abs s         -- representing s, amplified by i
>   + ε * i * abs s         -- error in calculating (*), i * s
>   + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
>   + ε * abs t             -- representing t
>   + ε * abs (f + i*s - t) -- error in calculating (-)
> 
> Note that the last term of the bound is the thing we are bounding. So we can handle that by picking a slightly
larger epsilon, eps = ε/(1-ε).
> 
> This leads to the following implementation of enumFromStepTo:
> 
>    enumFromStepToEps eps !f !s !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + 2 * abs (i * s) + abs t + abs x
> 
>  with eps = 1.12e-16 :: Double
>  or   eps = 5.97e-8 :: Float
> 
> I have done extensive experiments with this implementation and many variants, and I believe it will work
in all cases.
> 
> Now for enumFromTo, i.e. step=1 we could make a special case, since we know that step is exactly equal to 1,
so there is no representation error. We could get rid of the multiplication, and replace i*s by 0 in the
error calculation.
> 
> Another issue that remains is enumFromThenTo. If we take
>  step = then - from
> then the relative error in step is bounded by
>  |step' - step| ≤ ε * (|then| + |from| + |then - from|).
> This error gets multiplied by i, so it can unfortunately become quite large.
> 
> I think it would be best if we use the more general
> 
>    enumFromStepToEps' !eps !f !s !sErr !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x
> 
>   enumFromStepTo f s t = enumFromStepToEps' eps f s s t
>   enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
>   enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
>                              (abs h + abs f + abs (h - f)) t
> 
> 
> I have also looked at what other language implementations do. So far I have found that:
> * Octave uses a similar method, with the bound
>     3 * double_epsilon * max (abs x) (abs t),
>   which is less tight than my bound.
>   see
http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525 
> 
> * numpy just uses an array with length ceil((to-from)/step)
>   see https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
>   It therefore suffers from numerical inaccuracies:
>   $ python
>   >>> from numpy import arange
>   >>> notone = 9/7. - 1/7. - 1/7.
>   >>> notone
>   1.0000000000000002
>   >>> len(arange(1,1))
>   0
>   >>> len(arange(1,notone))
>   1
> 
> 
> In summary:
> * change Enum Rational to the always correct implementation
> * change Enum Double and Enum Float to the almost-always correct implementation propose above.
> * (optional) expose the enumFromStepTo function.
> 
> 
> 
> Twan
> 
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Edward Kmett | 8 Jul 04:46 2013
Picon

Re: Proposal: fix Enum Double instance

There is a pretty big potential problem with this.


Not every type that is enumerable admits a torsor where you can talk about forward differences.

What would the enumFromStepTo function mean for, say, Ordering or for most derived Enum instances?

-Edward

On Sun, Jul 7, 2013 at 12:17 PM, Edward A Kmett <ekmett <at> gmail.com> wrote:
+1 from me.

The massive cancellation destroying significant figures of significand in enumFromThenTo has always driven me nuts.

Sent from my iPhone

On Jul 5, 2013, at 8:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:

> Hello All,
>
>
> I would like to make a counterproposal in the Enum Double debate: Instead of deprecating or removing the instances, how about just fixing them?
>
> A perfect instance for Enum Double is not possible, because arithmetic is inexact. But you can actually get awfully close. I.e. instead of allowing the final value to be at most step/2 past the end, we can allow it to be at most about 2e-16*step past the end. In many practical applications this is close enough to not be a problem.
>
>
>
> Now for some more detail on the design:
>
> * First of all, Haskell's enumFromThenTo is stupid, because calculating step=then-from destroys numerical accuracy. So I will focus on implementing a function enumFromStepTo. You can still implement enumFromThenTo on top of it. But it might also make sense to expose enumFromStepTo.
>
> * It is possible to write an exact instance for Rational. It is IMO unacceptable that Haskell currently does not use this correct instance. I will use this Rational instance as a baseline for comparison.
>
>    instance EnumFromStepTo Rational where
>      enumFromStepTo f s t
>        | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
>        | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
>        | otherwise = []
>
> * Writing a loop naively, by recursing with from' = from+step will result in accumulating the error of the addition. On the other hand, Doubles can represent integer numbers exactly up to 2^53, so it is better to use values from+i*step.
>
> * Assume for simplicity that step>0. The stopping condition will then be of the form  from+i*step-to > 0. When this quantity is 0 then the final value should be included, otherwise it shouldn't be.
>
> * Now for an error analysis. Assume that we start with
>   f,s,t :: Rational
>  and call
>   let f' = fromRational f
>   let s' = fromRational s
>   let t' = fromRational t
>   enumFromThenTo f' s' t'
>
> The fromRational function rounds a rational number to the nearest representable Double. The relative error in f' is therefore bounded by abs (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the result of an addition or multiplication operation will also be rounded to the nearest representable Double.
>
> So, the total error in our stopping condition is bounded by
> err(f+i*s-t)
>   ≤ ε * abs f             -- representing f
>   + ε * i * abs s         -- representing s, amplified by i
>   + ε * i * abs s         -- error in calculating (*), i * s
>   + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
>   + ε * abs t             -- representing t
>   + ε * abs (f + i*s - t) -- error in calculating (-)
>
> Note that the last term of the bound is the thing we are bounding. So we can handle that by picking a slightly larger epsilon, eps = ε/(1-ε).
>
> This leads to the following implementation of enumFromStepTo:
>
>    enumFromStepToEps eps !f !s !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + 2 * abs (i * s) + abs t + abs x
>
>  with eps = 1.12e-16 :: Double
>  or   eps = 5.97e-8 :: Float
>
> I have done extensive experiments with this implementation and many variants, and I believe it will work in all cases.
>
> Now for enumFromTo, i.e. step=1 we could make a special case, since we know that step is exactly equal to 1, so there is no representation error. We could get rid of the multiplication, and replace i*s by 0 in the error calculation.
>
> Another issue that remains is enumFromThenTo. If we take
>  step = then - from
> then the relative error in step is bounded by
>  |step' - step| ≤ ε * (|then| + |from| + |then - from|).
> This error gets multiplied by i, so it can unfortunately become quite large.
>
> I think it would be best if we use the more general
>
>    enumFromStepToEps' !eps !f !s !sErr !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x
>
>   enumFromStepTo f s t = enumFromStepToEps' eps f s s t
>   enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
>   enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
>                              (abs h + abs f + abs (h - f)) t
>
>
> I have also looked at what other language implementations do. So far I have found that:
> * Octave uses a similar method, with the bound
>     3 * double_epsilon * max (abs x) (abs t),
>   which is less tight than my bound.
>   see http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525
>
> * numpy just uses an array with length ceil((to-from)/step)
>   see https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
>   It therefore suffers from numerical inaccuracies:
>   $ python
>   >>> from numpy import arange
>   >>> notone = 9/7. - 1/7. - 1/7.
>   >>> notone
>   1.0000000000000002
>   >>> len(arange(1,1))
>   0
>   >>> len(arange(1,notone))
>   1
>
>
> In summary:
> * change Enum Rational to the always correct implementation
> * change Enum Double and Enum Float to the almost-always correct implementation propose above.
> * (optional) expose the enumFromStepTo function.
>
>
>
> Twan
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
John Lato | 8 Jul 06:18 2013
Picon

Re: Proposal: fix Enum Double instance

My understanding was that the proposal required enumFromStepTo as a separate function (i.e. not a class method) with a Num constraint on the types.  So the function wouldn't be available for Ordering or derived Enum instances unless they also had a Num instance.

John

On Mon, Jul 8, 2013 at 10:46 AM, Edward Kmett <ekmett <at> gmail.com> wrote:
There is a pretty big potential problem with this.

Not every type that is enumerable admits a torsor where you can talk about forward differences.

What would the enumFromStepTo function mean for, say, Ordering or for most derived Enum instances?

-Edward

On Sun, Jul 7, 2013 at 12:17 PM, Edward A Kmett <ekmett <at> gmail.com> wrote:
+1 from me.

The massive cancellation destroying significant figures of significand in enumFromThenTo has always driven me nuts.

Sent from my iPhone

On Jul 5, 2013, at 8:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:

> Hello All,
>
>
> I would like to make a counterproposal in the Enum Double debate: Instead of deprecating or removing the instances, how about just fixing them?
>
> A perfect instance for Enum Double is not possible, because arithmetic is inexact. But you can actually get awfully close. I.e. instead of allowing the final value to be at most step/2 past the end, we can allow it to be at most about 2e-16*step past the end. In many practical applications this is close enough to not be a problem.
>
>
>
> Now for some more detail on the design:
>
> * First of all, Haskell's enumFromThenTo is stupid, because calculating step=then-from destroys numerical accuracy. So I will focus on implementing a function enumFromStepTo. You can still implement enumFromThenTo on top of it. But it might also make sense to expose enumFromStepTo.
>
> * It is possible to write an exact instance for Rational. It is IMO unacceptable that Haskell currently does not use this correct instance. I will use this Rational instance as a baseline for comparison.
>
>    instance EnumFromStepTo Rational where
>      enumFromStepTo f s t
>        | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
>        | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
>        | otherwise = []
>
> * Writing a loop naively, by recursing with from' = from+step will result in accumulating the error of the addition. On the other hand, Doubles can represent integer numbers exactly up to 2^53, so it is better to use values from+i*step.
>
> * Assume for simplicity that step>0. The stopping condition will then be of the form  from+i*step-to > 0. When this quantity is 0 then the final value should be included, otherwise it shouldn't be.
>
> * Now for an error analysis. Assume that we start with
>   f,s,t :: Rational
>  and call
>   let f' = fromRational f
>   let s' = fromRational s
>   let t' = fromRational t
>   enumFromThenTo f' s' t'
>
> The fromRational function rounds a rational number to the nearest representable Double. The relative error in f' is therefore bounded by abs (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the result of an addition or multiplication operation will also be rounded to the nearest representable Double.
>
> So, the total error in our stopping condition is bounded by
> err(f+i*s-t)
>   ≤ ε * abs f             -- representing f
>   + ε * i * abs s         -- representing s, amplified by i
>   + ε * i * abs s         -- error in calculating (*), i * s
>   + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
>   + ε * abs t             -- representing t
>   + ε * abs (f + i*s - t) -- error in calculating (-)
>
> Note that the last term of the bound is the thing we are bounding. So we can handle that by picking a slightly larger epsilon, eps = ε/(1-ε).
>
> This leads to the following implementation of enumFromStepTo:
>
>    enumFromStepToEps eps !f !s !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + 2 * abs (i * s) + abs t + abs x
>
>  with eps = 1.12e-16 :: Double
>  or   eps = 5.97e-8 :: Float
>
> I have done extensive experiments with this implementation and many variants, and I believe it will work in all cases.
>
> Now for enumFromTo, i.e. step=1 we could make a special case, since we know that step is exactly equal to 1, so there is no representation error. We could get rid of the multiplication, and replace i*s by 0 in the error calculation.
>
> Another issue that remains is enumFromThenTo. If we take
>  step = then - from
> then the relative error in step is bounded by
>  |step' - step| ≤ ε * (|then| + |from| + |then - from|).
> This error gets multiplied by i, so it can unfortunately become quite large.
>
> I think it would be best if we use the more general
>
>    enumFromStepToEps' !eps !f !s !sErr !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x
>
>   enumFromStepTo f s t = enumFromStepToEps' eps f s s t
>   enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
>   enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
>                              (abs h + abs f + abs (h - f)) t
>
>
> I have also looked at what other language implementations do. So far I have found that:
> * Octave uses a similar method, with the bound
>     3 * double_epsilon * max (abs x) (abs t),
>   which is less tight than my bound.
>   see http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525
>
> * numpy just uses an array with length ceil((to-from)/step)
>   see https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
>   It therefore suffers from numerical inaccuracies:
>   $ python
>   >>> from numpy import arange
>   >>> notone = 9/7. - 1/7. - 1/7.
>   >>> notone
>   1.0000000000000002
>   >>> len(arange(1,1))
>   0
>   >>> len(arange(1,notone))
>   1
>
>
> In summary:
> * change Enum Rational to the always correct implementation
> * change Enum Double and Enum Float to the almost-always correct implementation propose above.
> * (optional) expose the enumFromStepTo function.
>
>
>
> Twan
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Edward Kmett | 8 Jul 06:36 2013
Picon

Re: Proposal: fix Enum Double instance

Sadly this technically requires a language extension over Haskell 98/2010: ConstrainedClassMethods


http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/type-class-extensions.html#class-method-types

GHC seems to be somewhat lax about requiring that extension on code in practice these days, but it does have implications when it comes to other approaches to implementing a compiler for Haskell.

-Edward

On Sun, Jul 7, 2013 at 11:18 PM, John Lato <jwlato <at> gmail.com> wrote:
My understanding was that the proposal required enumFromStepTo as a separate function (i.e. not a class method) with a Num constraint on the types.  So the function wouldn't be available for Ordering or derived Enum instances unless they also had a Num instance.

John


On Mon, Jul 8, 2013 at 10:46 AM, Edward Kmett <ekmett <at> gmail.com> wrote:
There is a pretty big potential problem with this.

Not every type that is enumerable admits a torsor where you can talk about forward differences.

What would the enumFromStepTo function mean for, say, Ordering or for most derived Enum instances?

-Edward

On Sun, Jul 7, 2013 at 12:17 PM, Edward A Kmett <ekmett <at> gmail.com> wrote:
+1 from me.

The massive cancellation destroying significant figures of significand in enumFromThenTo has always driven me nuts.

Sent from my iPhone

On Jul 5, 2013, at 8:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:

> Hello All,
>
>
> I would like to make a counterproposal in the Enum Double debate: Instead of deprecating or removing the instances, how about just fixing them?
>
> A perfect instance for Enum Double is not possible, because arithmetic is inexact. But you can actually get awfully close. I.e. instead of allowing the final value to be at most step/2 past the end, we can allow it to be at most about 2e-16*step past the end. In many practical applications this is close enough to not be a problem.
>
>
>
> Now for some more detail on the design:
>
> * First of all, Haskell's enumFromThenTo is stupid, because calculating step=then-from destroys numerical accuracy. So I will focus on implementing a function enumFromStepTo. You can still implement enumFromThenTo on top of it. But it might also make sense to expose enumFromStepTo.
>
> * It is possible to write an exact instance for Rational. It is IMO unacceptable that Haskell currently does not use this correct instance. I will use this Rational instance as a baseline for comparison.
>
>    instance EnumFromStepTo Rational where
>      enumFromStepTo f s t
>        | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
>        | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
>        | otherwise = []
>
> * Writing a loop naively, by recursing with from' = from+step will result in accumulating the error of the addition. On the other hand, Doubles can represent integer numbers exactly up to 2^53, so it is better to use values from+i*step.
>
> * Assume for simplicity that step>0. The stopping condition will then be of the form  from+i*step-to > 0. When this quantity is 0 then the final value should be included, otherwise it shouldn't be.
>
> * Now for an error analysis. Assume that we start with
>   f,s,t :: Rational
>  and call
>   let f' = fromRational f
>   let s' = fromRational s
>   let t' = fromRational t
>   enumFromThenTo f' s' t'
>
> The fromRational function rounds a rational number to the nearest representable Double. The relative error in f' is therefore bounded by abs (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the result of an addition or multiplication operation will also be rounded to the nearest representable Double.
>
> So, the total error in our stopping condition is bounded by
> err(f+i*s-t)
>   ≤ ε * abs f             -- representing f
>   + ε * i * abs s         -- representing s, amplified by i
>   + ε * i * abs s         -- error in calculating (*), i * s
>   + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
>   + ε * abs t             -- representing t
>   + ε * abs (f + i*s - t) -- error in calculating (-)
>
> Note that the last term of the bound is the thing we are bounding. So we can handle that by picking a slightly larger epsilon, eps = ε/(1-ε).
>
> This leads to the following implementation of enumFromStepTo:
>
>    enumFromStepToEps eps !f !s !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + 2 * abs (i * s) + abs t + abs x
>
>  with eps = 1.12e-16 :: Double
>  or   eps = 5.97e-8 :: Float
>
> I have done extensive experiments with this implementation and many variants, and I believe it will work in all cases.
>
> Now for enumFromTo, i.e. step=1 we could make a special case, since we know that step is exactly equal to 1, so there is no representation error. We could get rid of the multiplication, and replace i*s by 0 in the error calculation.
>
> Another issue that remains is enumFromThenTo. If we take
>  step = then - from
> then the relative error in step is bounded by
>  |step' - step| ≤ ε * (|then| + |from| + |then - from|).
> This error gets multiplied by i, so it can unfortunately become quite large.
>
> I think it would be best if we use the more general
>
>    enumFromStepToEps' !eps !f !s !sErr !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x
>
>   enumFromStepTo f s t = enumFromStepToEps' eps f s s t
>   enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
>   enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
>                              (abs h + abs f + abs (h - f)) t
>
>
> I have also looked at what other language implementations do. So far I have found that:
> * Octave uses a similar method, with the bound
>     3 * double_epsilon * max (abs x) (abs t),
>   which is less tight than my bound.
>   see http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525
>
> * numpy just uses an array with length ceil((to-from)/step)
>   see https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
>   It therefore suffers from numerical inaccuracies:
>   $ python
>   >>> from numpy import arange
>   >>> notone = 9/7. - 1/7. - 1/7.
>   >>> notone
>   1.0000000000000002
>   >>> len(arange(1,1))
>   0
>   >>> len(arange(1,notone))
>   1
>
>
> In summary:
> * change Enum Rational to the always correct implementation
> * change Enum Double and Enum Float to the almost-always correct implementation propose above.
> * (optional) expose the enumFromStepTo function.
>
>
>
> Twan
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Edward Kmett | 8 Jul 06:39 2013
Picon

Re: Proposal: fix Enum Double instance

Rather that would be the extension required if you wanted to implement this as an overloadable method in the class.


Implementing it separately and then wiring up enumFromThenTo in terms of it still leaves you with the annoying initial massive cancellation of your significand, so you wind up taking very precise steps of the wrong size. ;)

-Edward

On Sun, Jul 7, 2013 at 11:36 PM, Edward Kmett <ekmett <at> gmail.com> wrote:
Sadly this technically requires a language extension over Haskell 98/2010: ConstrainedClassMethods

http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/type-class-extensions.html#class-method-types

GHC seems to be somewhat lax about requiring that extension on code in practice these days, but it does have implications when it comes to other approaches to implementing a compiler for Haskell.

-Edward


On Sun, Jul 7, 2013 at 11:18 PM, John Lato <jwlato <at> gmail.com> wrote:
My understanding was that the proposal required enumFromStepTo as a separate function (i.e. not a class method) with a Num constraint on the types.  So the function wouldn't be available for Ordering or derived Enum instances unless they also had a Num instance.

John


On Mon, Jul 8, 2013 at 10:46 AM, Edward Kmett <ekmett <at> gmail.com> wrote:
There is a pretty big potential problem with this.

Not every type that is enumerable admits a torsor where you can talk about forward differences.

What would the enumFromStepTo function mean for, say, Ordering or for most derived Enum instances?

-Edward

On Sun, Jul 7, 2013 at 12:17 PM, Edward A Kmett <ekmett <at> gmail.com> wrote:
+1 from me.

The massive cancellation destroying significant figures of significand in enumFromThenTo has always driven me nuts.

Sent from my iPhone

On Jul 5, 2013, at 8:50 AM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:

> Hello All,
>
>
> I would like to make a counterproposal in the Enum Double debate: Instead of deprecating or removing the instances, how about just fixing them?
>
> A perfect instance for Enum Double is not possible, because arithmetic is inexact. But you can actually get awfully close. I.e. instead of allowing the final value to be at most step/2 past the end, we can allow it to be at most about 2e-16*step past the end. In many practical applications this is close enough to not be a problem.
>
>
>
> Now for some more detail on the design:
>
> * First of all, Haskell's enumFromThenTo is stupid, because calculating step=then-from destroys numerical accuracy. So I will focus on implementing a function enumFromStepTo. You can still implement enumFromThenTo on top of it. But it might also make sense to expose enumFromStepTo.
>
> * It is possible to write an exact instance for Rational. It is IMO unacceptable that Haskell currently does not use this correct instance. I will use this Rational instance as a baseline for comparison.
>
>    instance EnumFromStepTo Rational where
>      enumFromStepTo f s t
>        | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
>        | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
>        | otherwise = []
>
> * Writing a loop naively, by recursing with from' = from+step will result in accumulating the error of the addition. On the other hand, Doubles can represent integer numbers exactly up to 2^53, so it is better to use values from+i*step.
>
> * Assume for simplicity that step>0. The stopping condition will then be of the form  from+i*step-to > 0. When this quantity is 0 then the final value should be included, otherwise it shouldn't be.
>
> * Now for an error analysis. Assume that we start with
>   f,s,t :: Rational
>  and call
>   let f' = fromRational f
>   let s' = fromRational s
>   let t' = fromRational t
>   enumFromThenTo f' s' t'
>
> The fromRational function rounds a rational number to the nearest representable Double. The relative error in f' is therefore bounded by abs (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the result of an addition or multiplication operation will also be rounded to the nearest representable Double.
>
> So, the total error in our stopping condition is bounded by
> err(f+i*s-t)
>   ≤ ε * abs f             -- representing f
>   + ε * i * abs s         -- representing s, amplified by i
>   + ε * i * abs s         -- error in calculating (*), i * s
>   + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
>   + ε * abs t             -- representing t
>   + ε * abs (f + i*s - t) -- error in calculating (-)
>
> Note that the last term of the bound is the thing we are bounding. So we can handle that by picking a slightly larger epsilon, eps = ε/(1-ε).
>
> This leads to the following implementation of enumFromStepTo:
>
>    enumFromStepToEps eps !f !s !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + 2 * abs (i * s) + abs t + abs x
>
>  with eps = 1.12e-16 :: Double
>  or   eps = 5.97e-8 :: Float
>
> I have done extensive experiments with this implementation and many variants, and I believe it will work in all cases.
>
> Now for enumFromTo, i.e. step=1 we could make a special case, since we know that step is exactly equal to 1, so there is no representation error. We could get rid of the multiplication, and replace i*s by 0 in the error calculation.
>
> Another issue that remains is enumFromThenTo. If we take
>  step = then - from
> then the relative error in step is bounded by
>  |step' - step| ≤ ε * (|then| + |from| + |then - from|).
> This error gets multiplied by i, so it can unfortunately become quite large.
>
> I think it would be best if we use the more general
>
>    enumFromStepToEps' !eps !f !s !sErr !t = go 0
>      where
>      go i
>        | s >= 0 && x <= t = x : go (i+1)
>        | s <  0 && x >= t = x : go (i+1)
>        | abs (x - t) < eps * bound = [x]
>        | otherwise = []
>        where
>        x = f + i * s
>        bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x
>
>   enumFromStepTo f s t = enumFromStepToEps' eps f s s t
>   enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
>   enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
>                              (abs h + abs f + abs (h - f)) t
>
>
> I have also looked at what other language implementations do. So far I have found that:
> * Octave uses a similar method, with the bound
>     3 * double_epsilon * max (abs x) (abs t),
>   which is less tight than my bound.
>   see http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525
>
> * numpy just uses an array with length ceil((to-from)/step)
>   see https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
>   It therefore suffers from numerical inaccuracies:
>   $ python
>   >>> from numpy import arange
>   >>> notone = 9/7. - 1/7. - 1/7.
>   >>> notone
>   1.0000000000000002
>   >>> len(arange(1,1))
>   0
>   >>> len(arange(1,notone))
>   1
>
>
> In summary:
> * change Enum Rational to the always correct implementation
> * change Enum Double and Enum Float to the almost-always correct implementation propose above.
> * (optional) expose the enumFromStepTo function.
>
>
>
> Twan
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries




_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
John Lato | 8 Jul 02:09 2013
Picon

Re: Proposal: fix Enum Double instance

+1 from me, and +1 for exposing enumFromStepTo.  Like many others, the current behavior has always bothered me.


On Fri, Jul 5, 2013 at 9:50 PM, Twan van Laarhoven <twanvl <at> gmail.com> wrote:
Hello All,


I would like to make a counterproposal in the Enum Double debate: Instead of deprecating or removing the instances, how about just fixing them?

A perfect instance for Enum Double is not possible, because arithmetic is inexact. But you can actually get awfully close. I.e. instead of allowing the final value to be at most step/2 past the end, we can allow it to be at most about 2e-16*step past the end. In many practical applications this is close enough to not be a problem.



Now for some more detail on the design:

* First of all, Haskell's enumFromThenTo is stupid, because calculating step=then-from destroys numerical accuracy. So I will focus on implementing a function enumFromStepTo. You can still implement enumFromThenTo on top of it. But it might also make sense to expose enumFromStepTo.

* It is possible to write an exact instance for Rational. It is IMO unacceptable that Haskell currently does not use this correct instance. I will use this Rational instance as a baseline for comparison.

    instance EnumFromStepTo Rational where
      enumFromStepTo f s t
        | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t
        | s <  0 && f >= t = f : enumFromStepTo (f + s) s t
        | otherwise = []

* Writing a loop naively, by recursing with from' = from+step will result in accumulating the error of the addition. On the other hand, Doubles can represent integer numbers exactly up to 2^53, so it is better to use values from+i*step.

* Assume for simplicity that step>0. The stopping condition will then be of the form  from+i*step-to > 0. When this quantity is 0 then the final value should be included, otherwise it shouldn't be.

* Now for an error analysis. Assume that we start with
   f,s,t :: Rational
  and call
   let f' = fromRational f
   let s' = fromRational s
   let t' = fromRational t
   enumFromThenTo f' s' t'

 The fromRational function rounds a rational number to the nearest representable Double. The relative error in f' is therefore bounded by abs (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the result of an addition or multiplication operation will also be rounded to the nearest representable Double.

 So, the total error in our stopping condition is bounded by
 err(f+i*s-t)
   ≤ ε * abs f             -- representing f
   + ε * i * abs s         -- representing s, amplified by i
   + ε * i * abs s         -- error in calculating (*), i * s
   + ε * abs (f + i*s)     -- error in calculating (+), f + (i*s)
   + ε * abs t             -- representing t
   + ε * abs (f + i*s - t) -- error in calculating (-)

 Note that the last term of the bound is the thing we are bounding. So we can handle that by picking a slightly larger epsilon, eps = ε/(1-ε).

 This leads to the following implementation of enumFromStepTo:

    enumFromStepToEps eps !f !s !t = go 0
      where
      go i
        | s >= 0 && x <= t = x : go (i+1)
        | s <  0 && x >= t = x : go (i+1)
        | abs (x - t) < eps * bound = [x]
        | otherwise = []
        where
        x = f + i * s
        bound = abs f + 2 * abs (i * s) + abs t + abs x

  with eps = 1.12e-16 :: Double
  or   eps = 5.97e-8 :: Float

I have done extensive experiments with this implementation and many variants, and I believe it will work in all cases.

Now for enumFromTo, i.e. step=1 we could make a special case, since we know that step is exactly equal to 1, so there is no representation error. We could get rid of the multiplication, and replace i*s by 0 in the error calculation.

Another issue that remains is enumFromThenTo. If we take
  step = then - from
then the relative error in step is bounded by
  |step' - step| ≤ ε * (|then| + |from| + |then - from|).
This error gets multiplied by i, so it can unfortunately become quite large.

I think it would be best if we use the more general

    enumFromStepToEps' !eps !f !s !sErr !t = go 0
      where
      go i
        | s >= 0 && x <= t = x : go (i+1)
        | s <  0 && x >= t = x : go (i+1)
        | abs (x - t) < eps * bound = [x]
        | otherwise = []
        where
        x = f + i * s
        bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x

   enumFromStepTo f s t = enumFromStepToEps' eps f s s t
   enumFromTo     f   t = enumFromStepToEps' eps f 1 0 t
   enumFromThenTo f h t = enumFromStepToEps' eps f (h - f)
                              (abs h + abs f + abs (h - f)) t


I have also looked at what other language implementations do. So far I have found that:
 * Octave uses a similar method, with the bound
     3 * double_epsilon * max (abs x) (abs t),
   which is less tight than my bound.
   see http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/Range.cc#l525

 * numpy just uses an array with length ceil((to-from)/step)
   see https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L2742
   It therefore suffers from numerical inaccuracies:
   $ python
   >>> from numpy import arange
   >>> notone = 9/7. - 1/7. - 1/7.
   >>> notone
   1.0000000000000002
   >>> len(arange(1,1))
   0
   >>> len(arange(1,notone))
   1


In summary:
 * change Enum Rational to the always correct implementation
 * change Enum Double and Enum Float to the almost-always correct implementation propose above.
 * (optional) expose the enumFromStepTo function.



Twan

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Gmane