[PATCH] optimize =$EXPR

[Qian Yun]

Testing for equality (or inequality) of EPXR is
a core part of Kernel and other places.

I find that current situation can be improved.

To test equality, we do not need to compute (x-y)
in full, we can skip the denominator part, skip gcd,
skip potential "algreduc" (rationalizing the denominator),
save a few unnecessary "reduc" calls (only reduce on
necessary algebraic kernels).

I believe the following change doesn't break anything.

As a benchmark, for mapleok.input, the memory usage
drop from 13.5GB to 8.5GB, time usage from 14.5s to
12.2s.

- Qian

diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
index 6b9a11b5..86f94145 100644
--- a/src/algebra/expr.spad
+++ b/src/algebra/expr.spad
@@ -139,7 +139,8 @@
simplifyPower(denominator x, n::Integer)

smaller?(x : %, y : %) == smaller?(x, y)$Rep
- x : % = y : % == (x - y) =$Rep 0$Rep
+ x : % = y : % ==
+ numerator(x)*denominator(y) =$Rep
denominator(x)*numerator(y)
numer x == numer(x)$Rep
denom x == denom(x)$Rep

[Waldek Hebisch]

On Thu, Jun 11, 2026 at 06:33:03PM +0800, Qian Yun wrote:
> Testing for equality (or inequality) of EPXR is
> a core part of Kernel and other places.
>
> I find that current situation can be improved.
>
> To test equality, we do not need to compute (x-y)
> in full, we can skip the denominator part, skip gcd,

yes

> skip potential "algreduc" (rationalizing the denominator),
> save a few unnecessary "reduc" calls (only reduce on
> necessary algebraic kernels).

we definitely need 'reduc'. 'algreduc' is actually about
improving efficiency, because _correct_ alternatives are
more expensive.

> I believe the following change doesn't break anything.

AFAICS this is essentially the same as NAG version:

x:% = y:% == x =$Rep y

(where Rep is doing calculation which you expanded inline)
which was changed to current one because the simpler thing
is sometimes incorrect.

> As a benchmark, for mapleok.input, the memory usage
> drop from 13.5GB to 8.5GB, time usage from 14.5s to
> 12.2s.
>
> - Qian
>
> diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
> index 6b9a11b5..86f94145 100644
> --- a/src/algebra/expr.spad
> +++ b/src/algebra/expr.spad
> @@ -139,7 +139,8 @@
> simplifyPower(denominator x, n::Integer)
>
> smaller?(x : %, y : %) == smaller?(x, y)$Rep
> - x : % = y : % == (x - y) =$Rep 0$Rep
> + x : % = y : % ==
> + numerator(x)*denominator(y) =$Rep
> denominator(x)*numerator(y)
> numer x == numer(x)$Rep
> denom x == denom(x)$Rep
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/54bf5511-7487-41e1-8f1f-169128536449%40gmail.com.

--
Waldek Hebisch

[Waldek Hebisch]

On Thu, Jun 11, 2026 at 06:33:03PM +0800, Qian Yun wrote:

> Testing for equality (or inequality) of EPXR is
> a core part of Kernel and other places.
>
> I find that current situation can be improved.
>
> To test equality, we do not need to compute (x-y)
> in full, we can skip the denominator part, skip gcd,
> skip potential "algreduc" (rationalizing the denominator),
> save a few unnecessary "reduc" calls (only reduce on
> necessary algebraic kernels).
>
> I believe the following change doesn't break anything.

Look at commit 3255808d742077bc16f5ab47d658be3e80dcdf16

--
Waldek Hebisch

[Qian Yun]

On 6/11/26 7:44 PM, Waldek Hebisch wrote:
> On Thu, Jun 11, 2026 at 06:33:03PM +0800, Qian Yun wrote:
>> Testing for equality (or inequality) of EPXR is
>> a core part of Kernel and other places.
>>
>> I find that current situation can be improved.
>>
>> To test equality, we do not need to compute (x-y)
>> in full, we can skip the denominator part, skip gcd,
>
> yes
>
>> skip potential "algreduc" (rationalizing the denominator),
>> save a few unnecessary "reduc" calls (only reduce on
>> necessary algebraic kernels).
>
> we definitely need 'reduc'. 'algreduc' is actually about
> improving efficiency, because _correct_ alternatives are
> more expensive.
>

Not all 'reduc' are skipped, it used to happen for
commonk(x, y), now it is commonk(numer x, denom y)
and commonk(denom x, numer y) separately.
(The 'reduc' is only needed for multiplication, right?)

'algreduc' is not totally skipped, it is skipped
for denom(x)*denom(y).

- Qian

[Qian Yun]

On 6/11/26 7:44 PM, Waldek Hebisch wrote:
>

> AFAICS this is essentially the same as NAG version:
>
> x:% = y:% == x =$Rep y
>
> (where Rep is doing calculation which you expanded inline)
> which was changed to current one because the simpler thing
> is sometimes incorrect.
>

> Look at commit 3255808d742077bc16f5ab47d658be3e80dcdf16

It is not the same as old one, because I'm doing
multiplication in EXPR, not Rep. So 'reduc' is applied.

In theory, I didn't missing anything, right?

- Qian

[Waldek Hebisch]

I see, mutiplication in EXPR is probably good enough to pass
our existing tests, but this does not look right. Note that
we may have nested roots and mutiplying two roots may introduce
new denominators.

In general, representation of Expression is only normal: when
result of an operation is 0 it will give 0 at representation
level, but equal expressions may have different representations.

AFAICS the following should be OK:

algreduc((numer(x)*$Rep denom(y) -$Rep numer(y)*$Rep denom(x))::%,
commonk(x, y)) =$Rep 0

--
Waldek Hebisch

[Qian Yun]

On 6/11/26 11:48 PM, Waldek Hebisch wrote:
>
> I see, mutiplication in EXPR is probably good enough to pass
> our existing tests, but this does not look right. Note that
> we may have nested roots and mutiplying two roots may introduce
> new denominators.
>
> In general, representation of Expression is only normal: when
> result of an operation is 0 it will give 0 at representation
> level, but equal expressions may have different representations.
>
> AFAICS the following should be OK:
>
> algreduc((numer(x)*$Rep denom(y) -$Rep numer(y)*$Rep denom(x))::%,
> commonk(x, y)) =$Rep 0
>

Thanks, this works (need to tweak signature a bit), but the memory
usage grows from 8.5GB to 9.7GB compare to previous (flawed) version.

Profile shows lots of time and memory is spent in =$EXPR, reduc$EXPR.

As I see it, the purpose of 'reduc' is to simplify algebraic expression,
and the purpose of 'algreduc' is to rationalize the denominator
depending on getSimplifyDenomsFlag.

I can leave 'algreduc' alone. But for 'reduc', I think its
implementation is very inefficient. I think, in theory,
we can walk the variables of Rep to check for algebraic kernels
and do transformation if necessary.

I'll report back with numbers.

- Qian

[Waldek Hebisch]

On Fri, Jun 12, 2026 at 07:42:14AM +0800, Qian Yun wrote:
> On 6/11/26 11:48 PM, Waldek Hebisch wrote:
> >
> > I see, mutiplication in EXPR is probably good enough to pass
> > our existing tests, but this does not look right. Note that
> > we may have nested roots and mutiplying two roots may introduce
> > new denominators.
> >
> > In general, representation of Expression is only normal: when
> > result of an operation is 0 it will give 0 at representation
> > level, but equal expressions may have different representations.
> >
> > AFAICS the following should be OK:
> >
> > algreduc((numer(x)*$Rep denom(y) -$Rep numer(y)*$Rep denom(x))::%,
> > commonk(x, y)) =$Rep 0
> >
>
> Thanks, this works (need to tweak signature a bit), but the memory
> usage grows from 8.5GB to 9.7GB compare to previous (flawed) version.
>
> Profile shows lots of time and memory is spent in =$EXPR, reduc$EXPR.
>
> As I see it, the purpose of 'reduc' is to simplify algebraic expression,
> and the purpose of 'algreduc' is to rationalize the denominator
> depending on getSimplifyDenomsFlag.

Yes. Actually, above in test for equality we should be able to
replace 'algreduc' by 'reduc'.

> I can leave 'algreduc' alone. But for 'reduc', I think its
> implementation is very inefficient. I think, in theory,
> we can walk the variables of Rep to check for algebraic kernels
> and do transformation if necessary.

Hmm, that is what 'reduc' is essentially doing. But there is a
catch: reducing with respect to one kernel may expose other ones.
So we order kernels and start reduction from the most complex
one and then repeat this with simpler kernels. Also, we allow
arbitrary algebraic kernels and do not require minimal polynomials
to be monic, so reduction is more complex than in case of roots.

--
Waldek Hebisch

[Qian Yun]

On 6/12/26 8:42 AM, Waldek Hebisch wrote:
>
>> I can leave 'algreduc' alone. But for 'reduc', I think its
>> implementation is very inefficient. I think, in theory,
>> we can walk the variables of Rep to check for algebraic kernels
>> and do transformation if necessary.
>
> Hmm, that is what 'reduc' is essentially doing. But there is a
> catch: reducing with respect to one kernel may expose other ones.
> So we order kernels and start reduction from the most complex
> one and then repeat this with simpler kernels. Also, we allow
> arbitrary algebraic kernels and do not require minimal polynomials
> to be monic, so reduction is more complex than in case of roots.
>

Because 'reduc' is called by every + - * / =, any tiny
optimization could be helpful in the end.

My current plan is to do search and replace in parallel,
say for alg_ker1^n1*alg_ker2^n2, do transformation for them
in one loop. Then loop on the result until no transformation
are needed. This should save many memory allocations.

Also this opens doors for optimization like
sum([e1,e2,e3,...]), mul([e1,e2,e3,...]).

- Qian

[Qian Yun]

I planed to do transformation at monomial level instead of smp level.
Turns out this doesn't work.

But the following works, by avoiding unnecessary division (gcd).
This saves memory usage of mapleok.input by around 30%.
The =$EXPR optimization saves another 30%.
The kernel cache recycle patch saves around 30%.

So 3 patches together, for mapleok.input, memory usage drops
from 13.5GB to 5.1GB, time drops from 15s to 8s.

- Qian

diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad

index 6b9a11b5..94a24e9e 100644
--- a/src/algebra/expr.spad
+++ b/src/algebra/expr.spad
@@ -384,7 +384,9 @@
reduc(x, l) ==
for k in l repeat
p := minPoly k
- x := evl(numer x, k, p) /$Rep evl(denom x, k, p)
+ d := degree p
+ if degree(numer x, k) >= d or degree(denom x, k) >=
d then
+ x := evl(numer x, k, p) /$Rep evl(denom x, k, p)
x

evl0(p, k) ==

[Waldek Hebisch]

Yes, good.

> The =$EXPR optimization saves another 30%.
> The kernel cache recycle patch saves around 30%.
>
> So 3 patches together, for mapleok.input, memory usage drops
> from 13.5GB to 5.1GB, time drops from 15s to 8s.
>
> - Qian
>
> diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
> index 6b9a11b5..94a24e9e 100644
> --- a/src/algebra/expr.spad
> +++ b/src/algebra/expr.spad
> @@ -384,7 +384,9 @@
> reduc(x, l) ==
> for k in l repeat
> p := minPoly k
> - x := evl(numer x, k, p) /$Rep evl(denom x, k, p)
> + d := degree p
> + if degree(numer x, k) >= d or degree(denom x, k) >=
> d then
> + x := evl(numer x, k, p) /$Rep evl(denom x, k, p)
> x
>
> evl0(p, k) ==
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/41614faa-0cc7-4957-877f-71eb453f4680%40gmail.com.

--
Waldek Hebisch

[Qian Yun]

Just thought of this shortcut optimization.

This is valid, right? I can't think of any exception.

This saves 5% memory for mapleok.input.

- Qian

diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad

index 768acf85..ed89a42f 100644
--- a/src/algebra/expr.spad
+++ b/src/algebra/expr.spad
@@ -102,6 +102,7 @@
(x : % - y : %) : % == algreduc(x -$Rep y, commonk(x, y))
x : % / y : % == algreduc(x /$Rep y, commonk(x, y))

x : % = y : % ==

+ denom(x) = denom(y) => numer(x) = numer(y)
-- we only need to care about the numerator of (x - y)
res := (numer(x)*denom(y) - numer(y)*denom(x))::Rep
zero?(reduc(res, commonk(x, y)))$Rep

[Waldek Hebisch]

On Sun, Jun 14, 2026 at 06:31:34PM +0800, Qian Yun wrote:
> Just thought of this shortcut optimization.
>
> This is valid, right? I can't think of any exception.
>
> This saves 5% memory for mapleok.input.

Yes, looks good.

> diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
> index 768acf85..ed89a42f 100644
> --- a/src/algebra/expr.spad
> +++ b/src/algebra/expr.spad
> @@ -102,6 +102,7 @@
> (x : % - y : %) : % == algreduc(x -$Rep y, commonk(x, y))
> x : % / y : % == algreduc(x /$Rep y, commonk(x, y))
> x : % = y : % ==
> + denom(x) = denom(y) => numer(x) = numer(y)
> -- we only need to care about the numerator of (x - y)
> res := (numer(x)*denom(y) - numer(y)*denom(x))::Rep
> zero?(reduc(res, commonk(x, y)))$Rep
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/114b6d6f-9db3-4945-9371-2689c2c052f1%40gmail.com.

--
Waldek Hebisch

[Qian Yun]

I keep finding new things down this rabbit hole...

After latest patch, profiler shows smaller?$EXPR
takes a lot of time. So I took a look.

triage$Kernel calls smaller?$EXPR.
It is used to sort the kernels.

smaller?$EXPR calls
smaller?(numer(x)*denom(y), numer(y)*denom(x))

Well, we know there is no well defined order in EXPR.

The multiplication is expensive, we can change it to

smaller?(x : %, y : %) ==

denom(x) = denom(y) => smaller?(numer(x), numer(y))
smaller?(denom(x), denom(y))

This should also have the side effect that kernels with same
denom will appear near together?

Anyway, this change will reduce memory usage of mapleok.input
by 20%.

But there are 2 regression test failures in rsimp.output.

But they are good failures, the new results are simpler than
the old ones! (I checked, their values are correct.)

11: EQUL: (rs4, (30*sqrt(11)::eI + 11*sqrt(15))*a7715/11)
+--+ +--+ +--+
(2 \|15 + \|11 )\|28
Output1: ----------------------
2
+--+
+--+ +--+ |77
(11 \|15 + 30 \|11 ) |--
\|15
Output2: --------------------------
11

29: EQUL: (rs13, (6*sqrt(11) - 11*sqrt(3))*a12096_1331/6)
6+-+ +--+ +-+6+-+
Output1: \|7 \|11 - 2 \|3 \|7
+-----+
+--+ +-+ |12096
(6 \|11 - 11 \|3 ) 6|-----
\| 1331
Output2: ----------------------------
6

(for rs4, sqrt(28) can be further simplified to 2*sqrt(7))
(for rs13, it is negative, but the absolute value is correct.)

I'm too excited to share this finding. I haven't check further yet.
I hope this change does not have unwanted side effects, so it is safe
to be included.

- Qian

[Waldek Hebisch]

On Sun, Jun 14, 2026 at 10:40:59PM +0800, Qian Yun wrote:
> I keep finding new things down this rabbit hole...
>
> After latest patch, profiler shows smaller?$EXPR
> takes a lot of time. So I took a look.
>
> triage$Kernel calls smaller?$EXPR.
> It is used to sort the kernels.
>
> smaller?$EXPR calls
> smaller?(numer(x)*denom(y), numer(y)*denom(x))
>
> Well, we know there is no well defined order in EXPR.
>
> The multiplication is expensive, we can change it to
> smaller?(x : %, y : %) ==
> denom(x) = denom(y) => smaller?(numer(x), numer(y))
> smaller?(denom(x), denom(y))
>
> This should also have the side effect that kernels with same
> denom will appear near together?

That looks problematic to me. Namely, if we have two different
representations x1 and x2 of the same value, than modified variant
will give them some order, that is smaller?(x1, x2) or
smaller?(x2, x1) will be true. Original version gives false
in such case.

To put it differently, 'smaller?' is not true order, but is
not far from one. The modification above makes difference from
order much worse.

Let me add that for Expression(Integer) doing 'algreduc' with
'algreduc_flag$Lisp' set to true will produce representation
which almost canonical, that is canonical up to choice of
kernels. With canonical representaion we would get true
linear order using any of definitions above. But, 'algreduc'
may be quite expensive.

> Anyway, this change will reduce memory usage of mapleok.input
> by 20%.
>
> But there are 2 regression test failures in rsimp.output.
>
> But they are good failures, the new results are simpler than
> the old ones! (I checked, their values are correct.)

Yes, result of 'rsimp' is non-unique. Its correctness should
not depend on order of kernels, while exact form may depend
on order.

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/a9d72260-59e8-4e8f-a41d-3dfd31418ae0%40gmail.com.

--
Waldek Hebisch

[Qian Yun]

On 6/15/26 8:49 AM, Waldek Hebisch wrote:
> On Sun, Jun 14, 2026 at 10:40:59PM +0800, Qian Yun wrote:
>> I keep finding new things down this rabbit hole...
>>
>> After latest patch, profiler shows smaller?$EXPR
>> takes a lot of time. So I took a look.
>>
>> triage$Kernel calls smaller?$EXPR.
>> It is used to sort the kernels.
>>
>> smaller?$EXPR calls
>> smaller?(numer(x)*denom(y), numer(y)*denom(x))
>>
>> Well, we know there is no well defined order in EXPR.
>>
>> The multiplication is expensive, we can change it to
>> smaller?(x : %, y : %) ==
>> denom(x) = denom(y) => smaller?(numer(x), numer(y))
>> smaller?(denom(x), denom(y))
>>
>> This should also have the side effect that kernels with same
>> denom will appear near together?
>
> That looks problematic to me. Namely, if we have two different
> representations x1 and x2 of the same value, than modified variant
> will give them some order, that is smaller?(x1, x2) or
> smaller?(x2, x1) will be true. Original version gives false
> in such case.

We can leave smaller?$EXPR aside for now.

In Kernel:

triage(k1, k2) ==
height(k1) ~= height(k2) => B2Z(height(k1) < height(k2))
operator(k1) ~= operator(k2) => B2Z(operator(k1) < operator(k2))
(n1 := #(argument k1)) ~= (n2 := #(argument k2)) => B2Z(n1 < n2)
for x1 in argument(k1) for x2 in argument(k2) repeat
x1 ~= x2 => return B2Z(smaller?(x1, x2))
0


There is already a check that x1~=x2.
So in this case, it's perfectly fine to use the method above
to determine order?

- Qian

[Waldek Hebisch]

Probably. OTOH it looks to me that 'x1 ~= x2' already did all
expensive things needed for 'smaller?'. So replacing both
by their definitions and reusing subexpressions should be
as fast as what you propose.

--
Waldek Hebisch

[Qian Yun]

On 6/15/26 8:49 AM, Waldek Hebisch wrote:
>

> That looks problematic to me. Namely, if we have two different
> representations x1 and x2 of the same value, than modified variant
> will give them some order, that is smaller?(x1, x2) or
> smaller?(x2, x1) will be true. Original version gives false
> in such case.
>

Should 'smaller?' have this property?

Currently we have:

e1 := 1/sqrt(x)
e2 := sqrt(x)/x
test(e1=e2) -- is true
smaller?(e1,e2) -- is true
smaller?(e2,e1) -- is false

- Qian

[Qian Yun]

On 6/15/26 9:58 AM, Waldek Hebisch wrote:
>>
>> We can leave smaller?$EXPR aside for now.
>>
>> In Kernel:
>>
>> triage(k1, k2) ==
>> height(k1) ~= height(k2) => B2Z(height(k1) < height(k2))
>> operator(k1) ~= operator(k2) => B2Z(operator(k1) < operator(k2))
>> (n1 := #(argument k1)) ~= (n2 := #(argument k2)) => B2Z(n1 < n2)
>> for x1 in argument(k1) for x2 in argument(k2) repeat
>> x1 ~= x2 => return B2Z(smaller?(x1, x2))
>> 0
>>
>>
>> There is already a check that x1~=x2.
>> So in this case, it's perfectly fine to use the method above
>> to determine order?
>
> Probably. OTOH it looks to me that 'x1 ~= x2' already did all
> expensive things needed for 'smaller?'. So replacing both
> by their definitions and reusing subexpressions should be
> as fast as what you propose.
>

That can be done, preserve the old behavior, doesn't break
anything and saves memory.


However for the new approach:

I looked over the differences of "make all" in src/input
before and after this change.

Most changes are display order change.

Other changes seems to be correct, and simpler.
(Most happens in mapleok.input and rsimp.input.)

I haven't checked out the reason behind this.

One thought: we need a test suite that has more coverage.


Current smaller? does this:
compares numer(x)*denom(y) with numer(y)*denom(x)

This doesn't make much sense. The "smaller?" seems to
do comparison with the complexity of expression.
And the cross multiplication doesn't "preserve" complexity.

At least my proposed version is doing comparison
lexicographical.

Another point of view: the comparison in Kernel
is doing field by field comparison, consider expr
as "a/b", with "/" being operator, then doing field by field
comparison on "b", then "a".

Anyway, this change is very disruptive. More thought and
testing should go with it.

- Qian

[Qian Yun]

New optimization for today:

If x and y does not have common algebraic kernels, either:

1. they don't have algebraic kernels at all, so they are
canonical under FRAC SMP, so previous check is enough.

2. they have different algebraic kernels. Then there's
no way they can be equal.

For mapleok.input, this saves around 30% memory and 15% time.

- Qian

diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad

index ed89a42f..08fecfcc 100644
--- a/src/algebra/expr.spad
+++ b/src/algebra/expr.spad
@@ -103,9 +103,11 @@

x : % / y : % == algreduc(x /$Rep y, commonk(x, y))

x : % = y : % ==

denom(x) = denom(y) => numer(x) = numer(y)

+ lk := commonk(x, y)
+ empty? lk => false

-- we only need to care about the numerator of (x - y)
res := (numer(x)*denom(y) - numer(y)*denom(x))::Rep

- zero?(reduc(res, commonk(x, y)))$Rep
+ zero?(reduc(res, lk))$Rep

number?(x : %) : Boolean ==
if R has RetractableTo(Integer) then

[Waldek Hebisch]

On Tue, Jun 16, 2026 at 05:58:08PM +0800, Qian Yun wrote:
> New optimization for today:
>
> If x and y does not have common algebraic kernels, either:
>
> 1. they don't have algebraic kernels at all, so they are
> canonical under FRAC SMP, so previous check is enough.

That is true for Expression(Integer) and probably also for
Expression(Complex(Integer)), but may fail for more general
coefficients. Internally we sometimes use
Expression(Expression(Integer))...

So any such thing must be conditional, limited to "good"
coefficients.

> 2. they have different algebraic kernels. Then there's
> no way they can be equal.

That looks obvious, but I have seen various strange examples,
so it would be better to have a proof.

This certainly fails for say Expression(AlgebraicNumber).

> For mapleok.input, this saves around 30% memory and 15% time.
>
> - Qian
>
> diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
> index ed89a42f..08fecfcc 100644
> --- a/src/algebra/expr.spad
> +++ b/src/algebra/expr.spad
> @@ -103,9 +103,11 @@
> x : % / y : % == algreduc(x /$Rep y, commonk(x, y))
> x : % = y : % ==
> denom(x) = denom(y) => numer(x) = numer(y)
> + lk := commonk(x, y)
> + empty? lk => false
> -- we only need to care about the numerator of (x - y)
> res := (numer(x)*denom(y) - numer(y)*denom(x))::Rep
> - zero?(reduc(res, commonk(x, y)))$Rep
> + zero?(reduc(res, lk))$Rep
>
> number?(x : %) : Boolean ==
> if R has RetractableTo(Integer) then
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/74de9c95-3b7a-483e-a7d1-0cc6e473f9d9%40gmail.com.

--
Waldek Hebisch

[Qian Yun]

On 6/16/26 7:30 PM, Waldek Hebisch wrote:
> On Tue, Jun 16, 2026 at 05:58:08PM +0800, Qian Yun wrote:
>> New optimization for today:
>>
>> If x and y does not have common algebraic kernels, either:
>>
>> 1. they don't have algebraic kernels at all, so they are
>> canonical under FRAC SMP, so previous check is enough.
>
> That is true for Expression(Integer) and probably also for
> Expression(Complex(Integer)), but may fail for more general
> coefficients. Internally we sometimes use
> Expression(Expression(Integer))...
>
> So any such thing must be conditional, limited to "good"
> coefficients.

Good catch! Yes, limiting to Expression(Integer) is good enough
for 99% situations. See attachment for the updated version.

>> 2. they have different algebraic kernels. Then there's
>> no way they can be equal.
>
> That looks obvious, but I have seen various strange examples,
> so it would be better to have a proof.
>

In EXPR(INT), for x,y doesn't share any common algebraic kernels,
then 'reduc' will do nothing for numer(x)*denom(y)-numer(y)*denom(x).

=$EXPR returns true for x,y
<=> numer(x)*denom(y)-numer(y)*denom(x) = 0
<=> numer(x)/denom(x)=numer(y)/denom(y)
<=> numer(x)=numer(y) and deonm(x)=denom(y)
(Since FRAC will strip gcd from them).

- Qian

[Qian Yun]

Or to summarize it, it is the noZeroDivisors property.
So that when two coefficients multiple, they don't vanish.
However EXPR(INT) and AN claim they have noZeroDivisors,
but they are not. e.g. (x+sqrt(x^2))*(x-sqrt(x^2))

- Qian

[Qian Yun]

Some updates:

The following 'smaller?' change causes some test result
to change differently than before, here is the reason:

1. for mapleok.input changes, for example:

in1378a:=integrate(z*acoth(1-(1-z)^(1/2)), z= 0..1,"noPole")

Used to be:
- 12 log(4) - 3 log(- 1) + 20
(65) -----------------------------
12

Now is:
- 3 log(4) + 5
(65) --------------
3

The reason is that, for definite integration, firstly
indefinite integration is done, then calls limit,
which calls mrv_limit, which calls 'normalize' before
anything else.

The different comes from 'normalize'.

'normalize' tries to find algebraic relations between kernels,
it does so by trying to represent latter kernels in 'tower'
by previous ones.

So the differences of kernel ordering have an impact there.

My patch causes kernels with complex denominator more likely
to be represented by kernels without complex denominator.

2. for rsimp.out changes

The difference comes from ordering in 'factorList',
for example in 'rsimp1_gen_2' called by 'rsimp_gen_2'
called by 'rsimp2_gen' called by 'rsimp'.

The order in 'factorList' is determined by 'smaller?'.
Also it seems that the factorization itself depends
on order.

Maybe in AlgebraicNumber, we can have more meaningful
'smaller?' defined?


So in the above cases, order in Expression matters,
and seems that different orders are both "correct",
just the result might be more complex or simpler.

I still believe the changed version does a better job.

- Qian

[Qian Yun]

Any comments on this updated version of patch?

Also on the "smaller?" change? Can that go in after
extensive testing?

- Qian

On 6/16/26 8:07 PM, Qian Yun wrote:

[Waldek Hebisch]

On Wed, Jun 24, 2026 at 06:07:00PM +0800, Qian Yun wrote:
> Any comments on this updated version of patch?

OK. Main thing is that as you wrote when there are no
common algebraic kernels, then 'reduc' is a no-op, so
we have equality in Rep. For Expression(Integer)
Rep is canonical, so equality in Rep means equality of
numerator and denominator.

> Also on the "smaller?" change? Can that go in after
> extensive testing?

I need to think about this a bit longer, will answer later.

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/0d96bc55-47bc-401f-9302-60819b0f115a%40gmail.com.

--
Waldek Hebisch