Speed up special cases of square-free factorization.
authorRichard Kreckel <kreckel@ginac.de>
Wed, 24 Jan 2018 21:37:24 +0000 (22:37 +0100)
committerRichard Kreckel <kreckel@ginac.de>
Wed, 24 Jan 2018 21:37:24 +0000 (22:37 +0100)
commit4ffb3cbb3ab5f642e461bcbf8fb29743752c5d58
treef9e4a88eb6465dbad3c31b7e636daf26bf079ebb
parent51c4b683827bc6fc427cb5c8ca789a4c9465e021
Speed up special cases of square-free factorization.

Square-free factorization of polynomials containing a factor which is
a high power P of a symbol x did scale like O(P) in space and time.
This patch introduces a shortcut in Yun's algorithm, such that the
computation is only O(1) in space and time.

This makes it possible to compute, say sqrfree(x^P + x^(P+1)) =>
(1+x)*x^P with P=123456789.

Found this to be a bottleneck while debugging one of Vitaly Magerya's
examples.
ginac/normal.cpp