Changeset d90ef2 in git

Timestamp:

Jul 3, 2019, 4:05:16 PM (5 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

0d47ce167ece3ca579dc431d2dbd03e5947e1aac

Parents:

d085ff19dc31e583deec9b63b69e20adf8e70887

Message:

use Flint-gcd for Q and Z/p (p>500)

Files:

• Tst/Short/gcd0_s.res.gz.uu (modified) (1 diff)
• Tst/Short/gcd0_s.stat (modified) (1 diff)
• libpolys/polys/clapsing.cc (modified) (3 diffs)

Tst/Short/gcd0_s.res.gz.uu

@@ -1 +1 @@
 begin 640 gcd0_s.res.gz
-M'XL("$-D15@``V=C9#!?<RYR97,`O5IM;^/(#?Z^OV*P*+"V9=E#SHND2VW@
-MBCL4"W0+%'O]TJ*Y56(Y$>I8.4OV.BWZW\L92:.18WOCY.Z`W6@D<C@<DD,^
-ME/SYIQ\^_I4Q!G,VG;[[W-SAA.[8W>V"_UQ.JK)B(2OOBTW%JJRL2K8L-H;(
-M;M/5[7:55GFQ+EF^9O^8.`EBXLN35M[WJQ7;KO-=NLG3*F/K8AU6FWR7IRN6
-M[=.'QU56LMOB(6/+3?%@%O@[,?//U6*RS/:LV#AQJE7/,GR_>KQ/#<N$L<]F
-M>K%DU7W6R4PW&7O8KJK\<95G"_8UK^Y9MLH>LG55.IG:RK0K_XU5A=TINUUE
-MI.SZSHA<9.OB(5^G5;$INWU&O7W&5LA/_N)D%KOA&W/S9?N!I>L%^[+[0,9K
-M=_KEMGC<I&69#7#*IS#\X.0E5AZ)**O%)[.#'?_S[6*2KYT"P'T%`&H%"O9#
-M\9U[B#T6ZQE6U!9I??',F]9(C^F&E*RRC3,3R&9VNKK;9#>;-+^EK5;9NK2S
-MR$RW]^F&<7)NQ7)C`6-E,OI35CD9M?L8&]QLVXA*5YLL73R1K+RLAHY3]S0G
-M6[LQ6?HO'__$WE-P3E;YS?LK1TGFC![^G*_S:C"\>F>N;#YO@WF=?9V45>J4
-M03YW0A'\Y;`^!"&S`;"!&1_OQXM'9WGLA3C*3CFD#5H5[M;%)ANP]WT)5^\9
-MZ46B.Y[O#A9QNT$]/TF*/,W)'(_%ZHDM9X,P44J.]M<R!(P312,1`N<H:(2A
-M1J#!L)-"YK(S[]PCX9E$U`%5FF-U>%8=#QF*K#O@8\9),'?/Q;Q]+@`%D<S%
-M465-E4*)>J(9.:KR=-!._I+8S/;V,K";VXO`;FV/@=G8WDV):N'+6O*+IL3>
-MBDF](AJ%ZU6AI4GN1$.SK8X&G0R)IRU')WI7K';6K_:\$6V]?;CQ#IJDZ%K.
-M`*8RBA,Y@F1TH6.E]'11$]\34_HOE3::<TDK`"ATK+ISRS2.$O.O<T_[Q'%[
-M,2CCB]TDDXO=I+S@5."Y:7KH*(5]1TVQ1Q6>'-FYBKQ3GHQTI8Q3!FA,'YB_
-M:/YV-E?&>+-!CQJ`1^_"\HZ>TMZ([(A>`*K$+A3NKY-0DZ0X!*!+%$)$%QV"
-MB0-57V08VU#0-@QHQ=!;47.KD16$5A!:.<).U-Y$<3`1>JHZ+35V6FH;HP.C
-M1$)>,^(#3(S\0)H['=AX58$T&LI`V)@-[![(K7W;:-G8#L"0KH$'=L])S1\'
-M=K-1?=%!;`5K*[?V!\GTI*D3ZC?A#5,Z+28RIG+49_`B6L=V?R`!%>=V68K%
-M.%+<6E\G%*'VN3F1W##59S*144,@?T0817:VIUQBMPI*:]XPDB^%%K%6&E6]
-M)XV1YK*FBEJ,:);`0&J,8Q[SOMR(]\.+HM"=F\A+35$/$$2B5^=P1B<X'=:U
-MAA'@,=5AEI)**1DYI<73`%P1C&1/E.J*8*2/%L&>^-.%L,?F1$;SLV0Z0"?T
-M[7B2S@PQ?VW1C.%9T8R]<Q'7%EWFF[(:UVFE@:0;Z&K`H%SE=_<527DH%OF2
-MD*G#/;$\7E%CU:NHHY2(`S-*NZGZ7%F-O>B.G^?K49M]1VWZ'37Y=^0"*7Z>
-MLU\R+?'R=@*GRVN"I\MKXN7L1+ZIO";JC>4UT9XN4;^\#NKZ2NXQ_@F[(IL*
-M_P;]&V_L?)G$E]3BI`MM4KOS[31]N9N`PVN\"QR]M85?E0<F2OL^IIV>J<S`
-ME2=+OZPR`X_.5F;@\=G*##PY79D!NMB%IL/Z2BU3P8IUW2>U!]AU>FQ-?9-3
-MSC1@IU+A;CC>OB`5MFQ.)!V%?^?43V^P>R;G9Z>H+CWN*#WNR!8[LL2N2X\`
-MVMMIU*;'CAP?YCT`+^K0]J)LE5+G;/H_:IY=`CSKO;KQ\HZMR974838-9FM5
-MZN]_/)Q9HVS3X=M6>B,FCE2C$T)'VVL<[0@Q;$<[4Y'E:-LY'FO8$6K9L(&N
-M^3R6/I;8NN>>L;"./TB0Q&B:+VD=3F-%8Q6(6#9C8<#0]EK24`>);H8R5%$[
-MQM!R"#L1I&S&PE,H;O"#T&ZU2,?M:F%#J)=S:^B@YJG7LX_M&I[<_B&@E54P
-MD#M2>8>!V`5R.-K*8-M6$_`:13"-HK$VJD:PR1FU26E'C5&]/0CT[-X8Q?(&
-M`NMA6!N3)F,].92U9RSS:.?)$H=Z8S`(=Z2MXY">ILJ#+"!T#_T(<W*J8:_3
-M!Q'U9L233E9R]&3[4LZ<[!Y;*]+TE^?('8X#TV*^"L"`%,\.LM<O@E1O`S`@
-M]5$``S+J`YBJ!3!5-S4^`V!`>NE&\=<`&%"O*W'**W%*G`0PH.1)``/**VU*
-MOP7`@(K>!F#`:S=!)<<!3#5LWQ$,+#+IO*3Y!=`$M!>T&CUH4EW@`"U>Y3?M
-MQ;56!]"D.H0F;7]X')IXS2'H^(701"?GH4G$ST.3",Y`D\B+RJ:1NPB:F/[M
-M5`+;#L>[%R2PELV)5"TT$=TS/3\[Q;-K%#^#'=&S=Y00>Z4GAE?"CAB/P(YJ
-MDZ[+VVR]R-85S6G-YN:\"%7$WT85\?$W%!![J"+^/5%%_!NABKB/*@;;X6@G
-MJ3[++95V&@O"&.99^PH2O%81D@MA1?(KPHJD#RMV5F>7`1,OKR0]2)'T(86<
-M\?&@&N^'/J1(>I`B.?+=J(:STD+;ZKXH'<`]\6D&DOICT>U]NKZC\UX5]?KN
-MXU.[-G+_DQ%R<'`&^?%&Q=_!F6S08W,BQ?PLN;,B<O5*.(-<'R8(Y)$G.'X;
-MG$&>'(4S"/PYG*D<$<X`&80N<2.(2]^<(\AGQ?";4Y2WHCX)8!"BDP`&(?9D
-M)&\!,&B:Q;<`&,0.5"#BL0\<?7^@N`"R('J!B3W80&X^L!B>`PWH?:=#?"%H
-M0#P/&E"<!PVDZ6G0@,*+/7$Y:"#;GDX36_/>X=MIHF5S(AUHD-TS/3\[Q;.K
-M>`8:4#P##2B[PH+RE:`!Y2%HN"G(8B[+.K:7X`24W\0)*(^_?4"IO<W\CC@!
-MY6^#$U#V<0+56D788"L)+$CZB^%6[%SZ]#X#HKH,(Z#Z]3`"*G&H-`;;G:-Z
-M2<1\.ZRCV03S?OS4"V;55K`E7#4#[(@4Z>8G-X-\7;%\QJ]8_D?SZ8FN0>"*
-ME*(S\%]W8_('S)80[*\']C-5F`]'3]>Y$ZJ-U7"VQ.#)X]C['!3"_W,WLOY9
-MA?GMQ+8<=!8P7]JLPH\S:P@8+[WH-?W4\6FTIWR1T0'[R&;,SNIHYD-.2@=P
-MSS[-RJ?_##YZ\Y(3`DT;9?7XA?8T_?1/&,._.B*<FN6E0M,_E>8W*_GR:?`X
-@AF'H[GX9@U_W(\^O4?-CCT8T\?WAW?\!_3\XS54E````
+M'XL("*JR'%T"`V=C9#!?<RYR97,`O5IMC]O(#?Z>7S$("L2V+'O(>9%TJ1>X
+MX@Y%@*9`D>N7%MV+LI9WA7JM/4M6O"WZW\L92:.1UW;6NW<')*N1R.%P2`[Y
+M4/*GGW[X\%?&&%RQ^?S-I_8.9W3';F^6_.=R5I45"UEY5VPK5F5E5;)5L35$
+M=I.N;W;KM,J+3<GR#?O'S$D0,U^>M/*^7Z_9;I/7Z39/JXQMBDU8;?,Z3]<L
+MVZ?W#^NL9#?%?<96V^+>+/!W8N:?JN5LE>U9L77B5*>>9?A^_7"7&I898Y_,
+M]&+%JKNLEYEN,W:_6U?YPSK/ENQK7MVQ;)W=9YNJ=#*UE6E7_ANK"KM3=K/.
+M2-G-K1&YS#;%?;Y)JV);]ON,!ON,K9"?_,7)+';#7\S-Y]T[EFZ6['/]CHS7
+M[?3S3?&P3<LR&^&<SV'\SLE+K#P245;+CV8'-?_SS7*6;YP"P'T%`!H%"O9#
+M\9U[B`,6ZQE6-!;I?/'$F]9(#^F6E*RRK3,3R'9VNK[=9E^V:7Y#6ZVR36EG
+MD9EN[M(MX^3<BN7&`L;*9/3'K'(R&O<Q-OJRZR(J76^S=/E(LO*R&CM./="<
+M;.W&9.F_?/@3>TO!.5OG7]Z^=Y3DBM'#G_--7HW&[]^8*[NZZH)YDWV=E57J
+ME$%^Y80B^,MA<PA"9@-@"PL^W4^7#\[R.`AQE+UR2!NT*MQNBFTV8F^'$MZ_
+M9:07B>YYOCM8Q.T&]=5)4N1I3N9X*-:/;+48A8E2<K*_EB%@G"@:B1`X1T$C
+M##4"#<:]%#*7G7GK'@G/)*()J-(<J\.SZGC(4&3=$9\R3H*Y>RZNNN<"4!#)
+M7!Q5-E0IE&@FFI&C*D\'[>2OB,UL;R\#N[F]".S6]AB8C>W=E*@1OFHD/VM*
+M[*V8-"NB4;A9%3J:Y$XTM-OJ:=#+D'C:<G2BZV)=6[_:\T:TS>[^BW?0)$77
+M:@$PEU&<R`DDDPL=*Z6GBYKYGIC3?ZFTT9Q+6@%`H6/5O5OF<928?[U[NB>.
+MVXM!&5_L)IE<[";E!:<"STWS0T<I'#IJC@.J\.3(WE7DG?)DI"MEG#)"8_K`
+M_$7SM[>Y,L9;C`;4`#QZ'Y:W])3V1F1']`)0)7:A<'^=A)HDQ2$`7:(0(KKH
+M$$P<J.8BP]B&@K9A0"N&WHJ:6XVL(+2"T,H1=J+V)HJ#B3!0U6FIL==2VQ@=
+M&242\IH1'V!BY`?2W.G`QJL*I-%0!L+&;&#W0&X=VD;+UG8`AG0-/+![3AK^
+M.+";C9J+#F(K6%NYC3](IB=-G5"_#6^8TVDQD3&7DR&#%]$ZMOL#":@XM\M2
+M+,:1XM;Z.J$(M<_-B>2&J3F3B8Q:`ODCPBBRLSWE$KM54%KSEI%\*;2(M=*H
+MFCUIC#27#54T8D2[!`928QSSF`_E1GP87A2%[MQ$7FJ*!H`@$H,ZAPLZP>FX
+MJ36,`(^I#HN45$K)R"DMG@;@BF`D!Z)47P0C?;0(#L2?+H0#-B<RNCI+I@-T
+M0M^>)^G-$/.7%LT8GA3-V#L7<6/15;XMJVF35EI(NH6^!HS*=7Y[5Y&4^V*9
+MKPB9.MP3R^,5-5:#BCI)B3@RH[2?JL^5U=B+[OAIOIYTV7?2I=])FW\G+I#B
+MISG[.=,2+V\G<+J\)GBZO"9>SD[DJ\IKHEY97A/MZ1(-R^NHJ:_D'N.?L"^R
+MJ?!OT+_QQLZ727Q)+4[ZT":U>]_.T^>["3B\Q+O`T5M;^%5Y9*)TZ&/:Z9G*
+M#%QYLO3S*C/PZ&QE!AZ?K<S`D].5&:"/76@[K*_4,A6LV#1]4G>`7:?'-M0W
+M.>5,`W8J%=;CZ>X9J;!C<R+I*/P[IWYZB_TS>75VBNK38TWIL29;U&2)ND^/
+M`-K;:=2EQYX<'^8]`"_JT/:B;)U2YVSZ/VJ>70(\Z[VF\?*.K<F5U&&V#69G
+M5>KO?SR<V:!LT^';5GHK9H[4H!-"1[MKG-2$&':3VE1D.=GUCL<&=H1:MFR@
+M&SZ/98@E=NZY9RQLX@\2)#&:YDM:A]-8T5@%(I;M6!@PM+N6--1!HMNA#%74
+MC3&T',).!"G;L?`4BEO\(+1;+=)QMUK8$IKEW!HZ:'B:]>QCNX8G=W@(:&45
+MC&1-*M<8B#J0X\E.!KNNFH#7*()I%(VU4;6"3<YH3$H[:HWJ[4&@9_?6*)8W
+M$-@,P\:8-!F;R:%L/&.9)[4G2QSJC<$HK$E;QR$]394'64#H`?H1YN14XT&G
+M#R(:S(AGO:SDZ,GVI9PYV0.V3J3I+\^1>QP'IL5\$8`!*9X<9*]?!*E>!V!`
+MZJ,`!F0T!#!5!V"J?FI\!L"`]-*-XB\!,*!>5N*45^*4.`E@0,F3``:45]J4
+M?@V``16]#L"`UVZ"2HX#F&K<O2,86632>TGS"Z`):"]H-7K0I+K``5J\R&_:
+MBVNM#J!)=0A-NO[P.#3QFD/0\3.AB4[.0Y.(GX<F$9R!)I$7E6TC=Q$T,?W;
+MJ02V&T_K9R2PCLV)5!TT$?TS?75VBF?7*'X".Z(G[R@A]DI/#"^$'3$>@1W5
+M-MV4-]EFF6TJFM.9S<UY%JJ(OXTJXN-O*"#V4$7\>Z**^#="%?$058QVXTDM
+MJ3[+'95V&@O"&.99]PH2O%81D@MA1?(KPHID""MJJ[/+@(F75Y(!I$B&D$(N
+M^'143?=C'U(D`TB1'/ENU,!9::%M=5>4#N">^#0#2?.QZ.8NW=S2>:^*9GWW
+M\:E;&[G_R0@Y.#B#_'BCXN_@3#88L#F1XNHLN;<B<O5".(-<'R8(Y)$G.'X=
+MG$&>'(4S"/PIG*D<$<X`&80^<2.(2]^<(\A+WYPC*&]%?1+`($0G`0Q"[,E(
+M7@-@T#2+KP$PB#VH0,1C'SB&_D!Q`61!]`(3!["!W'Q@,3P'&M#[3H?X3-"`
+M>!XTH#@/&DC3TZ`!A1=[XG+00+8]G29VYKW#M]-$Q^9$.M`@^V?ZZNP4SZ[B
+M"6A`\00TH.P+"\H7@@:4AZ#A2T$6<UG6L3T')Z#\)DY`>?SM`TKM;>9WQ`DH
+M?QN<@/+@[<-.U2+<R5I2U34O(':B=MG3^PJ(ZC*(@.K7@PBH#MX\$*39U8[H
+MI1#SY;")91/*^^GC()155[]6\+X=8$^D.#<_N!GEFXKE"_Z>Y7\T'Y[H&@2N
+M1"DZ`?]U-R9[P&(%P?YZ9#]2A?EX\GB=.Z':&`T7*PP>/8Z]ST$!_#]W(YL?
+M59A?3NS*46\`\YW-*ORPL':`Z<J+7=--'9]&>\J7&1VO#VS![*R>9C[CI'3\
+M]NSCHGS\S^B#-R\Y(=`T45:/7VA/\X__A"G\JR?"J5E>(C3=4VE^L9*O'D</
+@4QB'[NZ7*?A5/_+\&K4_]6A%$]\?WOP?W`?7NE,E````
 `
 end

Tst/Short/gcd0_s.stat

@@ -1 @@
-1 >> tst_memory_0 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:201344
-1 >> tst_memory_1 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-1 >> tst_memory_2 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-1 >> tst_timer :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:4
-2 >> tst_memory_0 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:241896
-2 >> tst_memory_1 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-2 >> tst_memory_2 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-2 >> tst_timer :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2
-3 >> tst_memory_0 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:322168
-3 >> tst_memory_1 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-3 >> tst_memory_2 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-3 >> tst_timer :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:1
-4 >> tst_memory_0 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:362224
-4 >> tst_memory_1 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-4 >> tst_memory_2 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-4 >> tst_timer :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:0
-5 >> tst_memory_0 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:362448
-5 >> tst_memory_1 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-5 >> tst_memory_2 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:2228224
-5 >> tst_timer_1 :: 1480942444:4100, 64 bit:4.1.0:x86_64-Linux:nepomuck:7
+1 >> tst_memory_0 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:238168
+1 >> tst_memory_1 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+1 >> tst_memory_2 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+1 >> tst_timer :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:8
+2 >> tst_memory_0 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:278736
+2 >> tst_memory_1 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+2 >> tst_memory_2 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+2 >> tst_timer :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:3
+3 >> tst_memory_0 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:355800
+3 >> tst_memory_1 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+3 >> tst_memory_2 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+3 >> tst_timer :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:3
+4 >> tst_memory_0 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:395864
+4 >> tst_memory_1 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+4 >> tst_memory_2 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+4 >> tst_timer :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:1
+5 >> tst_memory_0 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:396088
+5 >> tst_memory_1 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+5 >> tst_memory_2 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:2252800
+5 >> tst_timer_1 :: 1562161834:4120, 64 bit:4.1.2:x86_64-Linux:nepomuck:18

libpolys/polys/clapsing.cc

@@ -59 +59 @@
   #ifdef HAVE_FLINT
   #if __FLINT_RELEASE >= 20503
-  #if 0
-  if (rField_is_Zp(r))
+  if (rField_is_Zp(r) && (r->cf->ch>500))
   {
     nmod_mpoly_ctx_t ctx;
     if (!convSingRFlintR(ctx,r))
     {
+      // leading coef. 1
       return Flint_GCD_MP(f,pLength(f),g,pLength(g),ctx,r);
     }
   }
   else 
-  #endif
-  #if 0
   if (rField_is_Q(r))
   {
@@ -76 +74 @@
     if (!convSingRFlintR(ctx,r))
     {
+      // leading coef. positive, all coeffs in Z
       poly res=Flint_GCD_MP(f,pLength(f),g,pLength(g),ctx,r);
       res=p_Cleardenom(res,r);
-    }
-  }
-  #endif
+      return res;
+    }
+  }
   #endif
   #endif
@@ -90 +89 @@
     CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g, r ) );
     res=convFactoryPSingP( gcd( F, G ) , r);
-    if ( rField_is_Zp(r)) p_Norm(res,r);
+    if ( rField_is_Zp(r))
+      p_Norm(res,r); // leading coef. 1
+    else if (rField_is_Q(r) && (!n_GreaterZero(pGetCoeff(res),r->cf)))
+      res = p_Neg(res,r); // leading coef. positive, all coeffs in Z
   }
   // and over Q(a) / Fp(a)