expand

[frederic han]

Bonjour a tous,

quelle difference y a t'il entre normal et expand, je pensais que normal faisait en plus des simplifications, mais j'ai voulu essayer ton test:

f1:=(x+y+z+1)^10+1
P1:=expand(f1*(f1+1)) est tres long (13s) et
P2:=normal(f1*(f1+1)) est immediat bien que les 2 aient le meme nombre de termes
(nops(P1) et nops(P2))

ca m'etonne un peu qu'il y ait une telle difference.

Fred

[parisse]

C'est parce que expand se fait au niveau symbolique (dsitributivité, collect des termes), alors que normal se fait en traduisant en polynôme multivariable (avec en plus coefficients simplifiés en tenant compte des éventuelles extensions algébriques), et est donc en général beaucoup plus efficace.

[frederic han]

OK, j'ai encore une question,

je voulais faire quelques tests, et je trouve bizarre.

sur une machine qui factorise p1 en 7s avec f1 de degre 30, je trouve bizarre de ne pas y arriver avec f1 de degre 31. (interruption apres 5min)

c'est normal?

Fred

[parisse]

A priori je dirais non, mais ca va être difficile de tester, vu que pour moi ça met déjà 30 secondes pour n=25. Si tu as le courage, tu peux essayer de tester quelle branche de code est prise dans gausspol.cc, vers la ligne 4622, il y a une description de l'algo de factorisation multi-variables, en particulier, est-ce qu'il passe par et réussit try_hensel_lift_factor (de ezgcd.cc), peut-etre qu'il y a une borne mal positionnée et qui est dépassée quelque part. Si j'ai le temps ce week-end je jetterai un coup d'oeil.

[frederic han]

Salut,

j'ai essaye avec gdb et j'ai fait control C lorsque les messages semblaient bloques.
[New Thread 805e8e580 (LWP 100066)]
[Thread 805e8e580 (LWP 100066) exited]
[New Thread 805e8eac0 (LWP 100068)]
[Thread 805e8eac0 (LWP 100068) exited]
[New Thread 805e8e740 (LWP 100066)]
[Thread 805e8e740 (LWP 100066) exited]
[New Thread 805e8ec80 (LWP 100068)]
[Thread 805e8ec80 (LWP 100068) exited]
[New Thread 805c38180 (LWP 100066)]
[Thread 805c38180 (LWP 100066) exited]
^C
Program received signal SIGINT, Interrupt.
[Switching to Thread 805c37e00 (LWP 100061)]
0x000000080391bff8 in __gmpn_mul_basecase () from /usr/local/lib/libgmp.so.10
(gdb) bt

#0 0x000000080391bff8 in __gmpn_mul_basecase () from /usr/local/lib/libgmp.so.10
#1 0x00007ffffebf2680 in ?? ()
#2 0x000000000000001a in ?? ()
#3 0x000000000000001a in ?? ()
#4 0x0000000808eab000 in ?? ()
#5 0x00000000000001a0 in ?? ()
#6 0x000000000000001a in ?? ()
#7 0x00000008039281c2 in __gmpn_toom22_mul () from /usr/local/lib/libgmp.so.10
#8 0x000000080391b9e5 in __gmpn_mul_n () from /usr/local/lib/libgmp.so.10
#9 0x00000008039298d5 in __gmpn_toom42_mul () from /usr/local/lib/libgmp.so.10
#10 0x0000000803918dca in __gmpn_mul () from /usr/local/lib/libgmp.so.10
#11 0x0000000803902c9d in __gmpz_aorsmul () from /usr/local/lib/libgmp.so.10
#12 0x00000008010ab573 in giac::type_operator_plus_times () from /usr/local/lib/libgiac.so.0
#13 0x0000000800ad4293 in giac::smallmult<giac::gen, unsigned int, int> () from /usr/local/lib/libgiac.so.0
#14 0x0000000800ad56a2 in giac::smallmulpoly_interpolate<giac::gen, unsigned int> () from /usr/local/lib/libgiac.so.0
#15 0x0000000800ad5408 in giac::smallmulpoly_interpolate<giac::gen, unsigned int> () from /usr/local/lib/libgiac.so.0
#16 0x0000000800ad5408 in giac::smallmulpoly_interpolate<giac::gen, unsigned int> () from /usr/local/lib/libgiac.so.0
#17 0x0000000800ad58f1 in giac::smallmulpoly_interpolate<giac::gen, unsigned int> () from /usr/local/lib/libgiac.so.0
#18 0x0000000800a4f87a in giac::mulpoly () from /usr/local/lib/libgiac.so.0
#19 0x0000000800cab613 in giac::try_hensel_lift_factor () from /usr/local/lib/libgiac.so.0
#20 0x0000000800a75d6e in giac::do_factor () from /usr/local/lib/libgiac.so.0
#21 0x0000000800a78534 in giac::factor () from /usr/local/lib/libgiac.so.0
#22 0x0000000800a32985 in giac::factor () from /usr/local/lib/libgiac.so.0
#23 0x0000000800a338be in giac::var_factor () from /usr/local/lib/libgiac.so.0
#24 0x0000000800a34108 in giac::factor () from /usr/local/lib/libgiac.so.0
#25 0x0000000800a34476 in giac::factor () from /usr/local/lib/libgiac.so.0
#26 0x0000000800a34d0e in giac::factorcollect () from /usr/local/lib/libgiac.so.0
#27 0x0000000800a35452 in giac::_factor () from /usr/local/lib/libgiac.so.0
#28 0x0000000800feaba0 in giac::unary_function_eval::operator() () from /usr/local/lib/libgiac.so.0
#29 0x0000000800c5eb62 in giac::symbolic::eval () from /usr/local/lib/libgiac.so.0
#30 0x0000000801090d4d in giac::gen::in_eval () from /usr/local/lib/libgiac.so.0
#31 0x0000000801091340 in giac::gen::eval () from /usr/local/lib/libgiac.so.0
#32 0x0000000800f9f638 in giac::protecteval () from /usr/local/lib/libgiac.so.0
#33 0x0000000800e1d22d in giac::in_thread_eval () from /usr/local/lib/libgiac.so.0
#34 0x000000080368f511 in pthread_getprio () from /lib/libthr.so.3
#35 0x00007ffffe9f7000 in ?? ()
Error accessing memory address 0x7ffffebf7000: Bad address.
(gdb)

Ca aide?

Fred

[parisse]

Donc il entre bien dans le try_hensel_lift_factor et c'est surement a une des etapes du lift de la factorisation qu'il doit bloquer. Tu peux faire f 19 dans gdb puis lister la frame appelante (l) et voir ou ca se trouve dans le source (c'est dans ezgcd.cc), ensuite il faudrait afficher la valeur des variables. Mais ca ne suffira sans doute pas, il faudra probalement faire une execution en pas a pas depuis le debut de try_hensel_lift pour voir ou ca bloque et pourquoi.

[parisse]

Apparamment, c'est un mauvais choix d'algorithme de multiplication, ici par interpolation de Lagrange (dans la remontée de Hensel au degré 18). Le mieux est probablement de désactiver l'algo de Lagrange pour le moment: dans gausspol.cc, ligne 729, en mettant 0 && dans le test. Ensuite ca a l'air de factoriser.

[frederic han]

Effectivement, ca marche bien!

Je n'ai pas pu tester en 64 bits, mais avec mon binaire 32bits passe partout, sur une meme machine:

installee en 64bits, ainsi que maple14 :

j'ai mesure cela:

n maple14 xcas_user-linux32
25 14s 6s
30 22.5s 19s
31 43s 22s
32 50s 25s

Fred