inserting non-algebraic kernels

[Qian Yun]

[sin x for x in 1..10^4];

For fricas-1.3.13, it takes 15s, after recent optimizations,
it takes 7s.

But for non-algebraic kernels, we can do better.

For Expression Integer, (not EXPR EXPR INT), when the kernel
is not algebraic, its representation is canonical.

Thus, when inserting a non-algebraic new kernel, if the binary
search returns no match, then we are sure it is a new kernel,
we can insert it directly without the need to do linear search.

The above analysis is sound, right?

- Qian

[Waldek Hebisch]

On Fri, Jun 26, 2026 at 11:40:03AM +0800, Qian Yun wrote:
> [sin x for x in 1..10^4];
>
> For fricas-1.3.13, it takes 15s, after recent optimizations,
> it takes 7s.
>
> But for non-algebraic kernels, we can do better.
>
> For Expression Integer, (not EXPR EXPR INT), when the kernel
> is not algebraic, its representation is canonical.

Actually there is trouble due to custom comparisons for
some operators (but that can be handled the same as now).

> Thus, when inserting a non-algebraic new kernel, if the binary
> search returns no match, then we are sure it is a new kernel,
> we can insert it directly without the need to do linear search.
>
> The above analysis is sound, right?

I do not think so. Not having true order means potential lack
of transitivity. So kernel that we look for may be in almost
any position relative to kernels in the path of binary search.

--
Waldek Hebisch

[Qian Yun]

On 6/26/26 7:37 PM, Waldek Hebisch wrote:
>
>> Thus, when inserting a non-algebraic new kernel, if the binary
>> search returns no match, then we are sure it is a new kernel,
>> we can insert it directly without the need to do linear search.
>>
>> The above analysis is sound, right?
>
> I do not think so. Not having true order means potential lack
> of transitivity. So kernel that we look for may be in almost
> any position relative to kernels in the path of binary search.
>

Assuming in a session we only have non-algebraic kernels.
Then current order is a true order.

Now considering adding some algebraic kernels.
Then "smaller?" as lexicographical order, is still a true order.
It's the involvement of "=" makes two lexicographical different
expression/kernel the same, making the latter inputted one
automatically transform to firstly inputted one.

But the result of kernel cache is still a true order,
if we are comparing a non-algebraic kernel to them.

- Qian

[Waldek Hebisch]

On Fri, Jun 26, 2026 at 08:12:44PM +0800, Qian Yun wrote:
> On 6/26/26 7:37 PM, Waldek Hebisch wrote:
> >
> >> Thus, when inserting a non-algebraic new kernel, if the binary
> >> search returns no match, then we are sure it is a new kernel,
> >> we can insert it directly without the need to do linear search.
> >>
> >> The above analysis is sound, right?
> >
> > I do not think so. Not having true order means potential lack
> > of transitivity. So kernel that we look for may be in almost
> > any position relative to kernels in the path of binary search.
> >
>
> Assuming in a session we only have non-algebraic kernels.
> Then current order is a true order.

Yes.

> Now considering adding some algebraic kernels.
> Then "smaller?" as lexicographical order, is still a true order.

It is not clear to me what you mean here.

> It's the involvement of "=" makes two lexicographical different
> expression/kernel the same, making the latter inputted one
> automatically transform to firstly inputted one.

And here.

> But the result of kernel cache is still a true order,
> if we are comparing a non-algebraic kernel to them.

Only if there are no comparisons with algebraic kernels.

--
Waldek Hebisch

[Qian Yun]

On 6/26/26 9:38 PM, Waldek Hebisch wrote:
> On Fri, Jun 26, 2026 at 08:12:44PM +0800, Qian Yun wrote:
>> On 6/26/26 7:37 PM, Waldek Hebisch wrote:
>>>
>>>> Thus, when inserting a non-algebraic new kernel, if the binary
>>>> search returns no match, then we are sure it is a new kernel,
>>>> we can insert it directly without the need to do linear search.
>>>>
>>>> The above analysis is sound, right?
>>>
>>> I do not think so. Not having true order means potential lack
>>> of transitivity. So kernel that we look for may be in almost
>>> any position relative to kernels in the path of binary search.
>>>
>>
>> Assuming in a session we only have non-algebraic kernels.
>> Then current order is a true order.
>
> Yes.
>
>> Now considering adding some algebraic kernels.
>> Then "smaller?" as lexicographical order, is still a true order.
>
> It is not clear to me what you mean here.

For 2 expression ea and eb, we may have smaller?(ea,eb) is true
but ea=eb is also true.

Now for the kernels already in the cache: ka and kb, they are
never equal, and when coerced into EXPR, they have "smaller?"
as the true order.

>> It's the involvement of "=" makes two lexicographical different
>> expression/kernel the same, making the latter inputted one
>> automatically transform to firstly inputted one.
>
> And here.
>
>> But the result of kernel cache is still a true order,
>> if we are comparing a non-algebraic kernel to them.
>
> Only if there are no comparisons with algebraic kernels.
>

Now for a new non-algebraic kernel kc, if the binary search shows
no equals, then we can say it is not in the kernel cache,
because the kernel cache is strictly ordered by "smaller?".

- Qian

[Waldek Hebisch]

On Fri, Jun 26, 2026 at 09:58:13PM +0800, Qian Yun wrote:
> On 6/26/26 9:38 PM, Waldek Hebisch wrote:
> > On Fri, Jun 26, 2026 at 08:12:44PM +0800, Qian Yun wrote:
> >> On 6/26/26 7:37 PM, Waldek Hebisch wrote:
> >>>
> >>>> Thus, when inserting a non-algebraic new kernel, if the binary
> >>>> search returns no match, then we are sure it is a new kernel,
> >>>> we can insert it directly without the need to do linear search.
> >>>>
> >>>> The above analysis is sound, right?
> >>>
> >>> I do not think so. Not having true order means potential lack
> >>> of transitivity. So kernel that we look for may be in almost
> >>> any position relative to kernels in the path of binary search.
> >>>
> >>
> >> Assuming in a session we only have non-algebraic kernels.
> >> Then current order is a true order.
> >
> > Yes.
> >
> >> Now considering adding some algebraic kernels.
> >> Then "smaller?" as lexicographical order, is still a true order.
> >
> > It is not clear to me what you mean here.
>
> For 2 expression ea and eb, we may have smaller?(ea,eb) is true
> but ea=eb is also true.
>
> Now for the kernels already in the cache: ka and kb, they are
> never equal, and when coerced into EXPR, they have "smaller?"
> as the true order.

I am affraid you jump to conclusions without justification.
IIRC we had an example of expression such that smaller?(c, a)
holds, but we also have smaller?(a, b) and smaller?(b, c).
In such case and assuming b is in the cache and used for
binary search a will be inserted below b and c will be
inserted above b. Later search for a may find c on its
path and conseqently binary search will look for a
above c so above b, that is in wrong part.

More generally, let us assume subset K0 of "nice" kernels.
AFAICS validity of binary search for K0 implies the
following: for each kernels a, c in K0 such that smaller?(a, b)
and each c in K we have two implications:
- smaller?(c, a) implies smaller?(c, b)
- smaller?(b, c) implies smaller?(a, c)

AFAICS this in only necessary condition, sufficient condition
looks much more complicated.

> >> It's the involvement of "=" makes two lexicographical different
> >> expression/kernel the same, making the latter inputted one
> >> automatically transform to firstly inputted one.
> >
> > And here.
> >
> >> But the result of kernel cache is still a true order,
> >> if we are comparing a non-algebraic kernel to them.
> >
> > Only if there are no comparisons with algebraic kernels.
> >
>
> Now for a new non-algebraic kernel kc, if the binary search shows
> no equals, then we can say it is not in the kernel cache,
> because the kernel cache is strictly ordered by "smaller?".

You may be confused by how 'smaller?' works. Kernels in the
cache are ordered by position, this is linear order. 'smaller?'
for kernels just uses position, so also is linear order. But
insertion uses 'triage'. If triage were linear order, then
kernels would be sorted with respect to 'triage'. But since
'triage' is not a linear order 'smaller?' and 'triage' may
give differnt results. Since for insertion we use 'triage',
fact that 'smaller?' is a linear order on kernels does not
help much.

Also, not that 'triage?' uses 'smaller?' for expression.
If you have kernels like 'sin(e1)', 'sin(e2)', ... etc,
'triage(sin(ei), sin(ej)' will be -1 if and only if
'smaller?(ei, ej)' holds. So 'triage' has the same
problems as 'smaller?' for expressions.

--
Waldek Hebisch

[Qian Yun]

On 6/27/26 12:40 AM, Waldek Hebisch wrote:
>
> I am affraid you jump to conclusions without justification.
> IIRC we had an example of expression such that smaller?(c, a)
> holds, but we also have smaller?(a, b) and smaller?(b, c).

Other than the example I give at 2020-Dec-7 (which is in
EXPR COMPLEX INT), is there an example in EXPR INT?

The above "smaller?" fails to be a true order is caused by its
definition "smaller?(numer(x)*denom(y),denom(x)*numer(y))",
right?

If changed to my suggestion
denom(x) = denom(y) => smaller?(numer(x), numer(y))
smaller?(denom(x), denom(y))
then it is a true order.

>>
>> Now for a new non-algebraic kernel kc, if the binary search shows
>> no equals, then we can say it is not in the kernel cache,
>> because the kernel cache is strictly ordered by "smaller?".
>
> You may be confused by how 'smaller?' works. Kernels in the
> cache are ordered by position, this is linear order. 'smaller?'
> for kernels just uses position, so also is linear order. But
> insertion uses 'triage'. If triage were linear order, then
> kernels would be sorted with respect to 'triage'. But since
> 'triage' is not a linear order 'smaller?' and 'triage' may
> give differnt results. Since for insertion we use 'triage',
> fact that 'smaller?' is a linear order on kernels does not
> help much.
>

If my above argument holds, that smaller?$EXPR can be a true order,
then for the kernels already in cache, "triage" is also a true order.
Right?

- Qian

[Waldek Hebisch]

On Sat, Jun 27, 2026 at 07:48:41AM +0800, Qian Yun wrote:
> On 6/27/26 12:40 AM, Waldek Hebisch wrote:
> >
> > I am affraid you jump to conclusions without justification.
> > IIRC we had an example of expression such that smaller?(c, a)
> > holds, but we also have smaller?(a, b) and smaller?(b, c).
>
> Other than the example I give at 2020-Dec-7 (which is in
> EXPR COMPLEX INT), is there an example in EXPR INT?

We have sqrt(-1) in EXPR(INT), so essentially the same example
works. And there is earlier, more complicated example by
Kurt Pagani.

> The above "smaller?" fails to be a true order is caused by its
> definition "smaller?(numer(x)*denom(y),denom(x)*numer(y))",
> right?

Core problem is that representation in EXPR is not canonical.
So the same element 'a' can be written as 'n/d' and '(n*t)/(d*t)'.
To be a well-defined function 'smaller?(n/d, b)' and
'smaller?((n*t)/(d*t), b)' should produce the same value
(and similar condition when numerator and denominator of
b are multiplied by a common factor). Definition above
fail this property for many t-s, but satisfies this it for
some notrivial t-s.

'smaller?' would be OK if we could find linear order on
expressions satisfying for all nonzero a, b, and t
condition (a < b) <=> (t*a < t*b) (where <=> means logical
equivalence). AFAICS there is no such linear order on
finite cyclic group and using algebraic extention we can
embed cyclic groups into Expression(Integer). Cyclic
subgroups seem to be the only obstacle to existence of
such an order. There is some hope that we can restric
set of needed t-s and build a good order.

Alternativly, we could define:

smaller?(x, y) ==
do_algreduc(x) <$Rep do_algreduc(y)

where 'do_algreduc' eliminates irrationalities from denominator
regargess of value of 'algreduc_flag'. Already eliminating
algebraic integers from denominator gets rid of biggest
problem, namely eliminate cyclic group of order bigger than 2.
So remaining cyclic group is {1, -1}...

> If changed to my suggestion
> denom(x) = denom(y) => smaller?(numer(x), numer(y))
> smaller?(denom(x), denom(y))
> then it is a true order.

This fails pretty badly the test above.

> >> Now for a new non-algebraic kernel kc, if the binary search shows
> >> no equals, then we can say it is not in the kernel cache,
> >> because the kernel cache is strictly ordered by "smaller?".
> >
> > You may be confused by how 'smaller?' works. Kernels in the
> > cache are ordered by position, this is linear order. 'smaller?'
> > for kernels just uses position, so also is linear order. But
> > insertion uses 'triage'. If triage were linear order, then
> > kernels would be sorted with respect to 'triage'. But since
> > 'triage' is not a linear order 'smaller?' and 'triage' may
> > give differnt results. Since for insertion we use 'triage',
> > fact that 'smaller?' is a linear order on kernels does not
> > help much.
> >
>
> If my above argument holds, that smaller?$EXPR can be a true order,
> then for the kernels already in cache, "triage" is also a true order.
> Right?

As I explained that is big if.

--
Waldek Hebisch

[Waldek Hebisch]

On Sat, Jun 27, 2026 at 02:50:26AM +0200, Waldek Hebisch wrote:
>
> Core problem is that representation in EXPR is not canonical.
> So the same element 'a' can be written as 'n/d' and '(n*t)/(d*t)'.
> To be a well-defined function 'smaller?(n/d, b)' and
> 'smaller?((n*t)/(d*t), b)' should produce the same value
> (and similar condition when numerator and denominator of
> b are multiplied by a common factor). Definition above
> fail this property for many t-s, but satisfies this it for
> some notrivial t-s.

<snip>

> Alternativly, we could define:
>
> smaller?(x, y) ==
> do_algreduc(x) <$Rep do_algreduc(y)
>
> where 'do_algreduc' eliminates irrationalities from denominator
> regargess of value of 'algreduc_flag'.

I have tried this. I get the following test times:
current trunk with just algreduc algreduc without
linear search
real 0m15.266s 2m7.091s 0m19.313s
user 1m29.209s 3m22.028s 1m32.056s
sys 0m5.879s 0m5.947s 0m6.054s

There are some test failures which I did not examine.

So, using algreduc makes comparisons _much_ slower. But ability
to use binary search without extra linear pass eliminates much
of the overhead and there is chance that such version would
scale better.

If you want to try the patch is in the attachement.


--
Waldek Hebisch

[Qian Yun]

On 6/27/26 8:50 AM, Waldek Hebisch wrote:
> On Sat, Jun 27, 2026 at 07:48:41AM +0800, Qian Yun wrote:
>> On 6/27/26 12:40 AM, Waldek Hebisch wrote:
>>>
>>> I am affraid you jump to conclusions without justification.
>>> IIRC we had an example of expression such that smaller?(c, a)
>>> holds, but we also have smaller?(a, b) and smaller?(b, c).
>>
>> Other than the example I give at 2020-Dec-7 (which is in
>> EXPR COMPLEX INT), is there an example in EXPR INT?
>
> We have sqrt(-1) in EXPR(INT), so essentially the same example
> works. And there is earlier, more complicated example by
> Kurt Pagani.

Not true.

x1 :=
(sqrt(-1)*x*exp(2*sqrt(-1)*x)-x)/((1+sqrt(-1))*exp(2*x*sqrt(-1))+1+sqrt(-1))
x2 := (-sqrt(-1)*(exp(sqrt(-1)*x))^2-sqrt(-1))/(2*exp(sqrt(-1)*x))
x3 := -2*exp(sqrt(-1)*x)/((exp(sqrt(-1)*x))^2-1)

The above is translated by %i->sqrt(-1).
smaller?(x2,x3) smaller?(x3,x1) smaller?(x2,x1) are all true.
No contradictions.

I guess the reason is that %i is computed in coefficient R, but
sqrt(-1) is not.


Can you give me a pointer to Kurt's example? That mail seemed
to happen before 2017. I can't find it.

>> The above "smaller?" fails to be a true order is caused by its
>> definition "smaller?(numer(x)*denom(y),denom(x)*numer(y))",
>> right?
>
> Core problem is that representation in EXPR is not canonical.
> So the same element 'a' can be written as 'n/d' and '(n*t)/(d*t)'.
> To be a well-defined function 'smaller?(n/d, b)' and
> 'smaller?((n*t)/(d*t), b)' should produce the same value
> (and similar condition when numerator and denominator of
> b are multiplied by a common factor). Definition above
> fail this property for many t-s, but satisfies this it for
> some notrivial t-s.

We can make "smaller?" a true order syntactically,
independent of "=" (which is semantic).

I mean, a total order in FRAC SMP Kernel is good enough.

We can have for x1:=sqrt(x)/x, x2=1/sqrt(x), they have
different order in "smaller?", but equal in "=".

We can never have a "smaller?" that's compatible to "=".

> 'smaller?' would be OK if we could find linear order on
> expressions satisfying for all nonzero a, b, and t
> condition (a < b) <=> (t*a < t*b) (where <=> means logical
> equivalence). AFAICS there is no such linear order on
> finite cyclic group and using algebraic extention we can
> embed cyclic groups into Expression(Integer). Cyclic
> subgroups seem to be the only obstacle to existence of
> such an order. There is some hope that we can restric
> set of needed t-s and build a good order.
>

We can't have a "smaller?" that's compatible with "=" for EXPR,
but we can have it for Kernel.

We have the input order.

Take above example, we can have x1 and x2 at the same time,
but we can't have Kernel sin(x1) and sin(x2) at the same time,
the latter inputted one will be replaced by the former one.

- Qian

[Waldek Hebisch]

Better variant: use 'do_algreduc' when kernels are inserted into
the cache (give saving since usually there are repeated comparisons
and it is enough to use 'do_algreduc' once).

Time for testsuite now is:

real 0m13.947s
user 1m24.984s
sys 0m5.660s

that is better than curent trunk.


--
Waldek Hebisch

[Waldek Hebisch]

On Sat, Jun 27, 2026 at 10:50:01AM +0800, Qian Yun wrote:
> On 6/27/26 8:50 AM, Waldek Hebisch wrote:
> > On Sat, Jun 27, 2026 at 07:48:41AM +0800, Qian Yun wrote:
> >> On 6/27/26 12:40 AM, Waldek Hebisch wrote:
> >>>
> >>> I am affraid you jump to conclusions without justification.
> >>> IIRC we had an example of expression such that smaller?(c, a)
> >>> holds, but we also have smaller?(a, b) and smaller?(b, c).
> >>
> >> Other than the example I give at 2020-Dec-7 (which is in
> >> EXPR COMPLEX INT), is there an example in EXPR INT?
> >
> > We have sqrt(-1) in EXPR(INT), so essentially the same example
> > works. And there is earlier, more complicated example by
> > Kurt Pagani.
>
> Not true.
>
> x1 :=
> (sqrt(-1)*x*exp(2*sqrt(-1)*x)-x)/((1+sqrt(-1))*exp(2*x*sqrt(-1))+1+sqrt(-1))
> x2 := (-sqrt(-1)*(exp(sqrt(-1)*x))^2-sqrt(-1))/(2*exp(sqrt(-1)*x))
> x3 := -2*exp(sqrt(-1)*x)/((exp(sqrt(-1)*x))^2-1)
>
> The above is translated by %i->sqrt(-1).
> smaller?(x2,x3) smaller?(x3,x1) smaller?(x2,x1) are all true.
> No contradictions.
>
> I guess the reason is that %i is computed in coefficient R, but
> sqrt(-1) is not.

OK, the specific example do not translate. But principle translates.

> Can you give me a pointer to Kurt's example? That mail seemed
> to happen before 2017. I can't find it.

I should have it in my notes, but I do not have them with me.
AFAIR Kurt complained about weird (wrong) behaviour which was
due to 'smalle?' failing to be an order.

> >> The above "smaller?" fails to be a true order is caused by its
> >> definition "smaller?(numer(x)*denom(y),denom(x)*numer(y))",
> >> right?
> >
> > Core problem is that representation in EXPR is not canonical.
> > So the same element 'a' can be written as 'n/d' and '(n*t)/(d*t)'.
> > To be a well-defined function 'smaller?(n/d, b)' and
> > 'smaller?((n*t)/(d*t), b)' should produce the same value
> > (and similar condition when numerator and denominator of
> > b are multiplied by a common factor). Definition above
> > fail this property for many t-s, but satisfies this it for
> > some notrivial t-s.
>
> We can make "smaller?" a true order syntactically,
> independent of "=" (which is semantic).
>
> I mean, a total order in FRAC SMP Kernel is good enough.

If you ensure canonical representation.

> We can have for x1:=sqrt(x)/x, x2=1/sqrt(x), they have
> different order in "smaller?", but equal in "=".
>
> We can never have a "smaller?" that's compatible to "=".

We can do that reducing to canonical form. As I wrote in
other mail, when we put kernel arguments in canonical form
this seem to give a speed improvement. And when
'smaller?' is not compatible with '=', then we need
linear search.

> > 'smaller?' would be OK if we could find linear order on
> > expressions satisfying for all nonzero a, b, and t
> > condition (a < b) <=> (t*a < t*b) (where <=> means logical
> > equivalence). AFAICS there is no such linear order on
> > finite cyclic group and using algebraic extention we can
> > embed cyclic groups into Expression(Integer). Cyclic
> > subgroups seem to be the only obstacle to existence of
> > such an order. There is some hope that we can restric
> > set of needed t-s and build a good order.
> >
>
> We can't have a "smaller?" that's compatible with "=" for EXPR,
> but we can have it for Kernel.
>
> We have the input order.
>
> Take above example, we can have x1 and x2 at the same time,
> but we can't have Kernel sin(x1) and sin(x2) at the same time,
> the latter inputted one will be replaced by the former one.

That replacement is in general due to linear search. This
thead started because you wanted to use only binary search
(OK, only in absence of algebraic kernels, but even if
argument has no algebraic kernels in general we need to
compare it to other arguments which may contain algebraic
kernels).

--
Waldek Hebisch

[Qian Yun]

On 6/27/26 7:42 PM, Waldek Hebisch wrote:
>
> OK, the specific example do not translate. But principle translates.
>

Well, SUP has true order. It seems that SMP also has true order.
Then FRAC SMP Kernel EXPR INT should have true order has well.
(Complex INT on the other hand does not have OrderedSet.)

So for EXPR INT e1,e2,e3, I don't think there will be
smaller?(e1,e2) smaller?(e2,e3) smaller?(e3,e1) be true at the same
time.

>>
>> We can never have a "smaller?" that's compatible to "=".
>
> We can do that reducing to canonical form. As I wrote in
> other mail, when we put kernel arguments in canonical form
> this seem to give a speed improvement. And when
> 'smaller?' is not compatible with '=', then we need
> linear search.
>

By "canonical form", you mean "setSimplifyDenomsFlag true".
The disadvantage is that sometimes the intermediate expression
swells, making the computation much longer, and result
expression huge. Right?

Also another minor disadvantage is that it forbids "1/(sqrt(x^2)-x)".

>>
>> We can't have a "smaller?" that's compatible with "=" for EXPR,
>> but we can have it for Kernel.
>>
>> We have the input order.
>>
>> Take above example, we can have x1 and x2 at the same time,
>> but we can't have Kernel sin(x1) and sin(x2) at the same time,
>> the latter inputted one will be replaced by the former one.
>
> That replacement is in general due to linear search. This
> thead started because you wanted to use only binary search
> (OK, only in absence of algebraic kernels, but even if
> argument has no algebraic kernels in general we need to
> compare it to other arguments which may contain algebraic
> kernels).
>

Yes, my idea is to skip linear search for non-algebraic kernels.

The comparison between algebraic kernels and non-algebraic kernels
has already been optimized recently.

- Qian

[Waldek Hebisch]

On Sat, Jun 27, 2026 at 08:34:13PM +0800, Qian Yun wrote:
> On 6/27/26 7:42 PM, Waldek Hebisch wrote:
> >>
> >> We can never have a "smaller?" that's compatible to "=".
> >
> > We can do that reducing to canonical form. As I wrote in
> > other mail, when we put kernel arguments in canonical form
> > this seem to give a speed improvement. And when
> > 'smaller?' is not compatible with '=', then we need
> > linear search.
> >
>
> By "canonical form", you mean "setSimplifyDenomsFlag true".

Not exactly. First, the patch is only doing this to arguments
of kernels, so other expression stay in normal form. And
second, that is canonical form which is implemented, but
there are other ones. For example, once we choose main
transcendental kernel we may consider our expression as an
algebraic function with this kernel as a variable. Then
we can determine number N such that values in N points
uniquely determine our function. Taking values is tricky
business, for normal values we need to recursively compute
canonicla form. And we may get poles. Such representation
would be hard to compute, but AFAICS one may get canonical
form in this way. In early days of computer algebra there
were proposals for various canonical representations,
modern system most of the time do not aim to have
canonical representation.

> The disadvantage is that sometimes the intermediate expression
> swells, making the computation much longer, and result
> expression huge. Right?

Concerning size, sometimes intermediate expressions are
larger, but typically seem to be smaller. Main trouble
is that removing irrationalities from denominators is
expensive (costs time).

> Also another minor disadvantage is that it forbids "1/(sqrt(x^2)-x)".

If done for all kernels, then yes.

> >> We can't have a "smaller?" that's compatible with "=" for EXPR,
> >> but we can have it for Kernel.
> >>
> >> We have the input order.
> >>
> >> Take above example, we can have x1 and x2 at the same time,
> >> but we can't have Kernel sin(x1) and sin(x2) at the same time,
> >> the latter inputted one will be replaced by the former one.
> >
> > That replacement is in general due to linear search. This
> > thead started because you wanted to use only binary search
> > (OK, only in absence of algebraic kernels, but even if
> > argument has no algebraic kernels in general we need to
> > compare it to other arguments which may contain algebraic
> > kernels).
> >
>
> Yes, my idea is to skip linear search for non-algebraic kernels.
>
> The comparison between algebraic kernels and non-algebraic kernels
> has already been optimized recently.

OK, so you are saying that in representation we have linear order.
Kernels, once inserted, have arguments of single form and are
sorted with respect to the order in representation. Seem to be
true. And you say that for arguments of a given kernel their
form is always canonical then you we can use order in the
representation. Makes sense.

Please understand that I want to be extra careful here.
Arguments of this sort many years ago led me to wrong conclusion
that binary search is enough. And possibly were used by orignal
Axiom developers to justify that one can terminate linear search
once new kernel is bigger than kernel at current position in
the cache (which is wrong too).

--
Waldek Hebisch

[Qian Yun]

On 6/28/26 12:34 AM, Waldek Hebisch wrote:
>>
>> Yes, my idea is to skip linear search for non-algebraic kernels.
>>
>> The comparison between algebraic kernels and non-algebraic kernels
>> has already been optimized recently.
>
> OK, so you are saying that in representation we have linear order.
> Kernels, once inserted, have arguments of single form and are
> sorted with respect to the order in representation. Seem to be
> true. And you say that for arguments of a given kernel their
> form is always canonical then you we can use order in the
> representation. Makes sense.
>
> Please understand that I want to be extra careful here.
> Arguments of this sort many years ago led me to wrong conclusion
> that binary search is enough. And possibly were used by orignal
> Axiom developers to justify that one can terminate linear search
> once new kernel is bigger than kernel at current position in
> the cache (which is wrong too).
>

I agree we should be extra careful here.

I'll think this over and we can merge this change piece by piece.

Also more extensive testing are needed.

- Qian