[GiNaC-list] factor() hangs on a simple expression, randomly

[Richard B. Kreckel]

Hi Vitaly,

On 11/30/2017 05:16 PM, Vitaly Magerya wrote:
>     $ ginsh
>     ginsh - GiNaC Interactive Shell (GiNaC V1.7.2)
>       __,  _______  Copyright (C) 1999-2017 Johannes Gutenberg University Mainz,
>      (__) *       | Germany.  This is free software with ABSOLUTELY NO WARRANTY.
>       ._) i N a C | You are welcome to redistribute it under certain conditions.
>     <-------------' For details type `warranty;'.
> 
>     Type ?? for a list of help topics.
>     > factor((2*x-l)^2*(-1+6*x-l)*(-1+3*x-l)*(-2+4*x-l)*(1+4*x-l)*(4*x-l)*(2+4*x-l));
> 
> At this point ginsh either hangs (80% of cases), or gives the correct
> result (20% of cases).
> 
> As you can see the expression is already factored, so a hang is pretty
> unexpected here. Note that if you'll drop two of the factors from that
> expression, GiNaC won't hang anymore.
I'm not an expert in factorization, but apparently multivariate Hensel
lifting keeps failing (in file factor.cpp).

You're right that this is unexpected. GiNaC first does a square-free
factorization and finds the terms (2*x-l)^2 and the expanded form of all
the rest, i.e. of
(-1+6*x-l)*(-1+3*x-l)*(-2+4*x-l)*(1+4*x-l)*(4*x-l)*(2+4*x-l). The
factorization of the rest then fails, depending on the order it finds
the symbols x and l.

Try the easier test case with the (2*x-l)^2 removed.

No idea why it doesn't factor the product term by term, first. I suppose
this is an easy and risk-free optimization! Can you try to send a patch?
I'ld be happy to review it and help, but have not the time to do it
myself, I'm afraid.

All my best,
   -richy.
-- 
Richard B. Kreckel
<https://in.terlu.de/~kreckel/>