On Wednesday, 18 December 2013 at 01:27:37 UTC, Chris Cain wrote:
> Just to step up your idea to something a bit closer to complete (still have not thrown it into a compiler or anything yet):
> http://www.dpaste.dzfl.pl/19c80ff9

Thinking about this a bit more, it might also be really cool if the way to make an Interval was using an IntervalBuilder or something of the like (as opposed to the current constructor that takes a "shape" template parameter). Then it'd be natural to have intervals without certain bounds being constructed (you'd just not specify the lowerbound while building it).

Of course, then it'd be almost completely unique in phobos since nothing else uses the builder pattern. That may or may not be an issue.

On Tuesday, 17 December 2013 at 21:57:54 UTC, Andrei Alexandrescu wrote:
> In an interval arithmetic approach numbers would compare actually equal, i.e. 10 == IntervalInt(5, 100) would be true.


Why is that? I would think that 10 == Interval(10,10), but interval(5,100).contains(10) ? True interval arithmetic is difficult to implement though, since !(a<b) does not imply (a>=b) if I got it right… So you you might have to introduce a tri-boolean type to represent uncertainty, or prevent those operations, or accept inconsistencies…  Also f(a) should be the min/max values of f over the interval a… Tricky to compute, you can try numerically…

On 12/17/13 5:58 PM, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:
> On Tuesday, 17 December 2013 at 21:57:54 UTC, Andrei Alexandrescu wrote:
>> In an interval arithmetic approach numbers would compare actually
>> equal, i.e. 10 == IntervalInt(5, 100) would be true.
>
>
> Why is that? I would think that 10 == Interval(10,10), but
> interval(5,100).contains(10) ?

Yah, defining == my way would make it non-transitive.

> True interval arithmetic is difficult to
> implement though, since !(a<b) does not imply (a>=b) if I got it right…

I didn't peruse the wikipedia page in detail but it seems a lot of interval arithmetic is well-defined.

> So you you might have to introduce a tri-boolean type

That would be good too for distinct reasons.


Andrei

On Wednesday, 18 December 2013 at 02:17:06 UTC, Andrei Alexandrescu wrote:
> On 12/17/13 5:58 PM, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:
>> Why is that? I would think that 10 == Interval(10,10), but
>> interval(5,100).contains(10) ?
>
> Yah, defining == my way would make it non-transitive.
>
>> True interval arithmetic is difficult to
>> implement though, since !(a<b) does not imply (a>=b) if I got it right…
>
> I didn't peruse the wikipedia page in detail but it seems a lot of interval arithmetic is well-defined.

But it is counter-intuitive since an interval represent uncertainty?

[5,5] == [5,5] => true
[1,5] != [1,5]  => false? // counter-intuitive
[0,5] < [6,10] => true
[0,5] < [2,10] => uncertain

>> So you you might have to introduce a tri-boolean type
>
> That would be good too for distinct reasons.

I wrote libraries for both tribool and fuzzybool for D 7 years ago to see how D worked for ADTs. I guess I could rewrite those to be more modern and make it available as a starting point. I believe I also started on (or planned) to do fuzzy numbers. Fuzzy numbers are related to intervals, but have a triangular membership function. You use it for representing hazy values like "pretty" or "intelligent" (the same person can be both smart and stupid at the same time). There are more than one definition, each with trade-offs.

e.g.:
fast = FuzzyNumber(40,60,70)
slow = FuzzyNumber(1,10,40)

However, one deficiency in D is (or was) that you cannot make comparison operators return non-bool values?

Anyway, I think it might be a good idea to implement Intervals, Fuzzynumber, Tribool and Fuzzylogic in a manner that is consistent.

On Wednesday, 18 December 2013 at 08:58:07 UTC, Ola Fosheim Grøstad wrote:
> [1,5] != [1,5]  => false? // counter-intuitive

(a bit unclear there, [1,5]!=[1,5] is uncertain/true, but not false which we might first assume)

On 12/18/13 12:58 AM, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:
> On Wednesday, 18 December 2013 at 02:17:06 UTC, Andrei Alexandrescu wrote:
>> On 12/17/13 5:58 PM, "Ola Fosheim Grøstad"
>> <ola.fosheim.grostad+dlang@gmail.com>" wrote:
>>> Why is that? I would think that 10 == Interval(10,10), but
>>> interval(5,100).contains(10) ?
>>
>> Yah, defining == my way would make it non-transitive.
>>
>>> True interval arithmetic is difficult to
>>> implement though, since !(a<b) does not imply (a>=b) if I got it right…
>>
>> I didn't peruse the wikipedia page in detail but it seems a lot of
>> interval arithmetic is well-defined.
>
> But it is counter-intuitive since an interval represent uncertainty?
>
> [5,5] == [5,5] => true
> [1,5] != [1,5]  => false? // counter-intuitive

Within the tolerance allowed, they are equal.

> [0,5] < [6,10] => true
> [0,5] < [2,10] => uncertain

That would be false.

The whole trick is to define primitives such that they have the fundamental properties (transitivity, (anti-)symmetry etc).

>>> So you you might have to introduce a tri-boolean type
>>
>> That would be good too for distinct reasons.
>
> I wrote libraries for both tribool and fuzzybool

There's been a discussion on fast tristate logic recently in here.


Andrei

On Wednesday, 18 December 2013 at 17:29:19 UTC, Andrei Alexandrescu wrote:
> Within the tolerance allowed, they are equal.

No, "a != a" is only false for singeltons ([3,3] etc)

>> [0,5] < [6,10] => true
>> [0,5] < [2,10] => uncertain
>
> That would be false.

Interval-arithmetic is used for approximate calculations with upper-lower bounds, so it should not be false because then you make the wrong approximation. If the approximation is uncertain you need to track that or throw an exception when intervals overlap.

> The whole trick is to define primitives such that they have the fundamental properties (transitivity, (anti-)symmetry etc).

The trick is to make the algebra useful for the domain it is used in. Some properties we are used to from regular real numbers will almost always break, so you have to decide based on usefulness.

Ola.

On Wednesday, 18 December 2013 at 17:29:19 UTC, Andrei Alexandrescu wrote:
> There's been a discussion on fast tristate logic recently in here.

Thanks for the tip. It uses one of the implementations I tested too, a LUT in a shift register. However, I think I found the regular lookup-table to be faster on x86 (takes one instruction):

e.g. AND:

static ubyte[16] lut = [0,0,0,0, 0,1,2,2, 0,2,2,2, 0,2,2,2];
value = lut[x*4+y]; //turn off boundary checks

On 12/18/13 10:02 AM, "Ola Fosheim Grøstad" > The trick is to make the algebra useful for the domain it is used in.
> Some properties we are used to from regular real numbers will almost
> always break, so you have to decide based on usefulness.

I don't think so. Algebraic properties have been derived from desirable and useful properties and have long shown good returns. Breaking algebraic properties based on ad-hoc arguments of usefulness will guarantee the type won't work with many standard algorithms (sort etc) and will never cease to surprise its users.

Andrei

On Wednesday, 18 December 2013 at 19:47:05 UTC, Andrei Alexandrescu wrote:
> I don't think so. Algebraic properties have been derived from desirable and useful properties and have long shown good returns.

No, when you change the foundation/definitions some of the theorems will break. That always happens. I can't think of a single example where that does not happen.

Some theorems are more important to uphold than others, it is a good thing to avoid breaking DeMorgans for instance.

> Breaking algebraic properties based on ad-hoc arguments of usefulness will guarantee the type won't work with many standard algorithms (sort etc) and will never cease to surprise its users.

Not sure what you mean by ad-hoc? It is so by definition? You are the one arguing for ad hoc… It does not make sense to turn to interval-algebra if you want range-like-ad-hoc-programmers-semantics? If you implement interval-algebra it should be… interval-algebra, and usable a such?