On Mon, Jun 22, 2026 at 07:12:30AM +0800, Qian Yun wrote:
> What's your opinion on maximast/research/survey/ALGORITHM_SURVEY.md ?
>
> How accurate is it?
AFAICS it repeats many "known" things, but there are inaccuracies. As
I wrote, reference to Sutherland looks like AI hallucination.
I see no mention of Risch structure theorem. Maybe it is considered
as part of Risch algorithm, but it is usable and important well beyond
integration.
There is mention of our intef.spad and intrf.spad as implementing
transcendental integration, but in fact transcendental integration
needs several files. First there is integrat.spad and efstruct.spad,
before function get to intef.spad. There is intpar.spad (essential
for transcendental completeness) and rdeefx.spad (most deals with
integration in terms of special functions, but it is used also in
elementary case).
The survey repeats old inaccurate claims. The Risch–Norman heuristic
is frequently claimed to be fast and in a sense it is fast: on simple
integrands it runs much faster then expected from simple estimate of
compexity. But take more complicated integand and executation time
grows quite a lot. Both myself and Sympy folks noticed that execution
time grows quite a lot and at least in FriCAS on complicated integands
Risch is faster than Risch–Norman.
I did not look at Maple code (supposedy Maple usere can extract and
see significant part of source code) nor at Mathematica code, so
it is hard to make strong statements. Experiments show that they
do not have full implementation of transcendental part of Risch
algorithm, but IIUC after Risch–Norman fails Maple uses its
version of Risch and Mathematica also uses some version of Risch.
> On the other hand, maximast uses a tree-like structure to represent
> expressions, unlike fricas.
>
> Also, it doesn't have Lisp like lists -- without GC, you can't
> have Lisp like lists with reference counting. Let's see how far
> it can go.
I have noticed that some algorithms initially were implemented for
machine precision integers. That may be enough to test the code,
but in heavier use is going to overflow. And going to arbitrary
precision integers means that they will have to deal with memory
management. IIUC safe Rust is memory safe, that is does not allow
freeing memory when there are references and forces programmer
to free memory when last reference is lost (otherwise the program
will not compile). I wonder how they will handle this: structuring
program so that Rust rules are satisfied looks tricky.
--
Waldek Hebisch