AInterval

[Ralf Hemmecke]

Hi Waldek,

I've just created a pull request factoring out some interval arithmetic
that is not necessarily bound to floating point operatioons.

https://github.com/fricas/fricas/pull/200

If you accept, I will reformat to fit the FriCAS style, i.e. using

foo : Type

instead of

foo: Type

Ralf

[Waldek Hebisch]

Looks good. But I have some doubt about 'error?'. Namely,
various q-functions allow doing things without checking,
so 'qinterval' in principle may create an interval where
lower bound is bigger than the upper bound. But usual
convention is that it is responsibility of user of
q-functions to ensure that arguments are valid. And other
functions just assume that they deal with valid things.
Do you intend/need to create invalid intervals? If not,
then 'error?' looks redundant.

--
Waldek Hebisch

[Waldek Hebisch]

On Fri, Jun 20, 2025 at 10:55:32PM +0200, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:

BTW, did you think about making it a bit more general? IIUC
addition works the same for OrderedAbelianSemiGroup, subtraction
probably needs OrderedAbelianGroup, multiplicative operations
should work for Join(OrderedAbelianSemiGroup, SemiRng).

Also, AFAICS when you have Ring as an argument, then the result
is valid SemiRing.

This just a suggestion, if you do not want to generalize, then
it is fine.

--
Waldek Hebisch

[Ralf Hemmecke]

While looking into the generalization of AInterval, I realized that abs
is defined in OrderedRing.

https://fricas.github.io/api/OrderedRing.html#index-1

Technically, it would be OK to define it already in OrderedAbelianGroup.

Basically the definition is

abs(x) == if x>0 then x else -x

so why is there need to have a multiplication in the structure?

Ralf

[Waldek Hebisch]

Right, current location of abs is a historical artifact.

--
Waldek Hebisch

[Ralf Hemmecke]

Ooops. In OrderedRing I find

positive? x == x>0
negative? x == x<0
sign x ==
positive? x => 1
negative? x => -1
zero? x => 0
error "x satisfies neither positive?, negative? or zero?"
abs x ==
positive? x => x
negative? x => -x
zero? x => 0
error "x satisfies neither positive?, negative? or zero?"

If a ring is equipped with a total order, how can this error case ever
occur? It would mean there are elements that are neither 0 nor smaller
nor bigger than 0. What kind of total order is this?

Or is it taking care of the Float domain? But Float is only a fake ring
for convenience. In the long run I would like to take away the Ring
property from Float.

Anyway, if I now provide a patch in moving the above functions to
OrderedAbelianGroup, I would like to remove this error case. But I fear
that this might change something in other places of FriCAS.

Suggestions?

Ralf

[Waldek Hebisch]

On Sat, Jun 21, 2025 at 01:40:15PM +0200, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> Ooops. In OrderedRing I find
>
> positive? x == x>0
> negative? x == x<0
> sign x ==
> positive? x => 1
> negative? x => -1
> zero? x => 0
> error "x satisfies neither positive?, negative? or zero?"
> abs x ==
> positive? x => x
> negative? x => -x
> zero? x => 0
> error "x satisfies neither positive?, negative? or zero?"
>
> If a ring is equipped with a total order, how can this error case ever
> occur? It would mean there are elements that are neither 0 nor smaller nor
> bigger than 0. What kind of total order is this?
>
> Or is it taking care of the Float domain? But Float is only a fake ring for
> convenience. In the long run I would like to take away the Ring property
> from Float.

AFAICS Float has honest linear order. That could be for DoubleFloat
where due to IEEE thing hardware will return stupid results. But I
suspect that this is just "defensive" coding.

BTW: DoubleFloat should use hardware or system abs and sign, so our
definitions above should not matter for it.

> Anyway, if I now provide a patch in moving the above functions to
> OrderedAbelianGroup, I would like to remove this error case. But I fear that
> this might change something in other places of FriCAS.

I would probably write:

abs(x) ==
x < 0 => -x
x

and similar for sign. But error case does not bother me too much.
If there are bugs in say comparison routine, than getting error
is slightly better than propagating further wrong result.

Your current patch is reasonable. But it is also reasonable to
eliminate error cases.

BTW: You can find a few 'error "impossible"' instructions that
I wrote. Assuming that there are no errors in coding and
reasoning they will be never executed. But practice is
imperfect, and some of those actually produced error message.

--
Waldek Hebisch

[Ralf Hemmecke]

I just realized that

%%% (155) -> OrderedRing has OrderedSemiGroup

(155) false

Isn´t that something we should correct?

See attached patch.

Ralf

[Ralf Hemmecke]

We have a view places where the introduction of OrderedField would make
sense?

Opinions?

Ralf

grep '\<Field\>' *.spad | grep '\<OrderedRing\>'
crfp.spad: -- R : Join(Field, OrderedRing, CharacteristicZero)
crfp.spad: R : Join(Field, OrderedRing)
numeigen.spad: Par : Join(Field, OrderedRing) -- it will be NF or RN
numeigen.spad: Par : Join(Field, OrderedRing) -- Float or
RationalNumber
numeigen.spad: Par : Join(Field, OrderedRing) -- Float or
RationalNumber
numsolve.spad: Par : Join(Field, OrderedRing) -- will be Float or RN
numsolve.spad: Par : Join(Field, OrderedRing ) -- it will be NF or RN
numsolve.spad: Par : Join(OrderedRing, Field) -- RN or NewFloat
numsolve.spad: Par : Join(Field, OrderedRing)
reclos.spad: TheField : Join(OrderedRing, Field)
reclos.spad: TheField : Join(OrderedRing, Field)
reclos.spad: TheField : Join(OrderedRing, Field, RealConstant)
sf.spad: Join(Field, OrderedRing, RealConstant, RetractableTo Integer,
sf.spad:++ it is defined to be a join of a Field and OrderedRing, some of

[Waldek Hebisch]

On Sun, Jun 22, 2025 at 12:43:21PM +0200, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> We have a view places where the introduction of OrderedField would make
> sense?
>
> Opinions?

I tried to avoid having too many categories. Mathematically
OrderedField does not say more than Join(Field, OrderedRing).
But Spad compiler distinguishes the two, if you require
OrderedField for an argument, then Join(Field, OrderedRing)
is not enough. So requiring OrderedField we need to assert
it explicitely. Note that it does not work well with conditional
exports, we would need extra conditional rules for OrderedField
while currently rules for OrderedRing and Field are enough.

This probably does not make much difference for ordered fields,
but as a general rule due to propagation of conditions longish
Join-s in domain conditions are preferable to "shortcuts" like
OrderedField.

--
Waldek Hebisch

[Waldek Hebisch]

Yes. Please commit.

--
Waldek Hebisch

[Ralf Hemmecke]

On 6/21/25 00:02, Waldek Hebisch wrote:
> BTW, did you think about making it a bit more general?....

> Also, AFAICS when you have Ring as an argument, then the result
> is valid SemiRing.

I've just tried to make AIntervalCategory more general.

I hope I got the conditions and export categories correct.
Would be nice if someone could re-check.

https://github.com/fricas/fricas/pull/200

Ralf

[Waldek Hebisch]

ATM I did not look at conditions and categories. However,
I have noticed a different issue. Namely, Interval is
supposed to be an implementation of interval artithmetic.
Which means that interval obtained as result of
interval arithmetic is supposed to contain interval
computed using infinitely precise artithmtic. Since
operations in Float are approximate it means that
results of arithmetic operations on intervals need to be
enlarged to compensate for effect of rounding. This
is done by use of roundUp and roundDown in qinterval.

I did not check if roundUp and roundDown _always_ lead
to correct result, but without them results are clearly
incorrect.

So, most of operations in Interval should stay the same.

--
Waldek Hebisch

[Waldek Hebisch]

On Mon, Jun 23, 2025 at 12:29:20AM +0200, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> On 6/21/25 00:02, Waldek Hebisch wrote:
> > BTW, did you think about making it a bit more general?....
> > Also, AFAICS when you have Ring as an argument, then the result
> > is valid SemiRing.
>
> I've just tried to make AIntervalCategory more general.
>
> I hope I got the conditions and export categories correct.
> Would be nice if someone could re-check.

I think that instead of

if R has OrderedSemiGroup then
SemiRng
....

you need

if R has OrderedSemiGroup and R has SemiRng then
SemiRng
...

That is SemiGroup and AbelianSemiGroup do not imply distributivity,
so SemiRng assert more than this.

Similarly for OrderedMonoid.

Also, do you really mean Field without ordering restrictions for
unit?, inv and '/'? AFAICS on any field one can introduce
structure of OrderedAbelianGroup by using a well-ordered basis
over rational numbers and lexicograpic order on corresonding
vectors. But a lot of fields do not have order consitent
with field operations.

--
Waldek Hebisch

[Ralf Hemmecke]

On 6/23/25 02:00, Waldek Hebisch wrote:
> I think that instead of
>
> if R has OrderedSemiGroup then
> SemiRng
> ....
>
> you need
>
> if R has OrderedSemiGroup and R has SemiRng then
> SemiRng
> ...
>
> That is SemiGroup and AbelianSemiGroup do not imply distributivity,
> so SemiRng assert more than this.

Ah, right. I was paying too much attention on minimality and missed
that. Thanks.

> Also, do you really mean Field without ordering restrictions for
> unit?

I also corrected this. There are two commits, because I pushed too early
without realizing that there was still an error after the first patch. :-(

Ralf

[Ralf Hemmecke]

On 6/23/25 01:22, Waldek Hebisch wrote:
> ATM I did not look at conditions and categories. However,
> I have noticed a different issue. Namely, Interval is
> supposed to be an implementation of interval artithmetic.
> Which means that interval obtained as result of
> interval arithmetic is supposed to contain interval
> computed using infinitely precise artithmtic. Since
> operations in Float are approximate it means that
> results of arithmetic operations on intervals need to be
> enlarged to compensate for effect of rounding. This
> is done by use of roundUp and roundDown in qinterval.

Right. That is why qInterval has no default implementation. And Interval
does not inherit anything from AInterval only from AIntervalCategory.
AInterval is for the exact case, Interval for Floating point intervals.

> I did not check if roundUp and roundDown _always_ lead
> to correct result, but without them results are clearly
> incorrect.

Yes. But roundUp and roundDown are implemented / used in Interval and
there is no default package for IntervalCategory.

> So, most of operations in Interval should stay the same.

Yes, when I first designed AIntervalCategory, I had in mind that the
semantics of Interval should not change. Of course, I could have made a
mistake, but then it would have been unintentional.

Maybe I should come up with a number of tests?

Ralf

[Waldek Hebisch]

On Mon, Jun 23, 2025 at 08:12:06AM +0200, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> On 6/23/25 01:22, Waldek Hebisch wrote:
> > ATM I did not look at conditions and categories. However,
> > I have noticed a different issue. Namely, Interval is
> > supposed to be an implementation of interval artithmetic.
> > Which means that interval obtained as result of
> > interval arithmetic is supposed to contain interval
> > computed using infinitely precise artithmtic. Since
> > operations in Float are approximate it means that
> > results of arithmetic operations on intervals need to be
> > enlarged to compensate for effect of rounding. This
> > is done by use of roundUp and roundDown in qinterval.
>
> Right. That is why qInterval has no default implementation. And Interval
> does not inherit anything from AInterval only from AIntervalCategory.
> AInterval is for the exact case, Interval for Floating point intervals.

OK, your patch removes implementations of '+', '-', '*' but
defaults in AIntervalCategory call qinterval from Interval.

> > I did not check if roundUp and roundDown _always_ lead
> > to correct result, but without them results are clearly
> > incorrect.
>
> Yes. But roundUp and roundDown are implemented / used in Interval and there
> is no default package for IntervalCategory.
>
> > So, most of operations in Interval should stay the same.
>
> Yes, when I first designed AIntervalCategory, I had in mind that the
> semantics of Interval should not change. Of course, I could have made a
> mistake, but then it would have been unintentional.
>
> Maybe I should come up with a number of tests?

That is actually tricky. In case on Interval what matters are
tiny 1 bit differences which occur in special cases.

--
Waldek Hebisch

[Waldek Hebisch]

Looks OK now.

--
Waldek Hebisch