Maxima 5.16.3 release --- enourmous slowdown of gf-package

On Wed, Aug 27, 2008 at 09:45:39PM -0600, Robert Dodier wrote:
> On 8/26/08, Oliver Kullmann <O.Kullmann at swansea.ac.uk> wrote:
> 
> >  field : [2,8,x^8+x^4+x^3+x+1];
> >  apply(gf_set,field);
> >  Evaluation took 0.1280 seconds (0.1272 elapsed) using 840.867 KB.
> >  (%o3) true
> >
> >  and now in 5.16.3:
> >
> >  apply(gf_set,field);
> >  Evaluation took 4.7883 seconds (4.9496 elapsed) using 42.714 MB.
> >  (%o58) true
> 
> Oliver, I believe the difference in behavior can be attributed
> to a change in the behavior of the ifactors function:
> in Maxima 5.15, ifactors(1) => [] (an empty list), while in 5.16,
> ifactors(1) => [[1, 1]]. (This new return value makes sense to me
> so I don't see any need to change it back.)
>

But it is clearly false: 1 is not a prime number, and in any number
theory book (that cares about such details) you find that the
unique(!) prime decomposition of 1 is given by the empty product!

(At http://en.wikipedia.org/wiki/Prime_number you find a few remarks
on "1 as a prime number".)

> The [[1, 1]] from ifactors makes gf_findprim act differently: there
> is a loop it goes through many times.  GF_VERBOSE:true shows that.
> 
> I find the following change to gf.mac seems to speed up gf greatly
> without changing the expected behavior as indicated by gf_test.
> 
> I'll commit this patch to cvs trunk and 5.16 release branch,
> although I'm not promising to make another release on the branch.
> 
> Please try this modification and let me know how it turns out for you.
>

Yet it seems that modification was not done? (Can't find it.)

In any way, I would prefer, in case Maxima keeps the changed ifactors(1)-value,
to correct ifactors, providing a trivial change that returns ifactors(n) = []
if n=1 and ifactors(n) otherwise (you know, I care about "0-correctness"
and "empty-correctness").

Of course, if now people are starting using the wrong new result ... ??

(But I definitely think that Maxima should care not to break such a fundamental
result as the uniqueness of prime factorisation of integers!)

Oliver
 
> best
> 
> Robert Dodier
> 
> PS. Here is the patch.
> 
> --- share/contrib/gf/gf.mac 16 Jul 2008 05:36:45 -0000  1.3
> +++ share/contrib/gf/gf.mac 28 Aug 2008 03:32:29 -0000
> @@ -411,7 +411,7 @@
>    block([f,fastf,slowf,found:false,fastCase,
>           lf,lfastf,lslowf,decomp,main_powers,q,elt,leng,i,test,fast_test,j,blist,sig,genn2l],
>    sig:?even(gf_exp),
> -  fastf : ifactors(gf_char-1), /* "fast" factors of gf_char-1 */
> +  fastf : if gf_char=2 then [] else ifactors(gf_char-1), /* "fast"
> factors of gf_char-1 */
>    lfastf : length(fastf),
>    fastf : makelist(fastf[i][1],i,1, lfastf),
>    fastfex : makelist([fastf[i],true,(gf_char-1)/fastf[i]],i,1,lfastf),

-- 
Dr. Oliver Kullmann
Computer Science Department
Swansea University
Faraday Building, Singleton Park
Swansea SA2 8PP, UK
http://cs.swan.ac.uk/~csoliver/