Changeset a9a6dcb in git
 Timestamp:
 Apr 13, 2012, 11:19:24 AM (11 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
 Children:
 f7a4e9271997208f4ee40a14fd1e1b5c6c0c1ffc
 Parents:
 e24341824b73ccd926669238b426c9c0ee24664b
 gitauthor:
 Martin Lee <martinlee84@web.de>20120413 11:19:24+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20120507 14:14:08+02:00
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cf_gcd_smallp.cc
re243418 ra9a6dcb 219 219 } 220 220 221 int222 substituteCheck (const CanonicalForm& F, const CanonicalForm& G)223 {224 if (F.inCoeffDomain()  G.inCoeffDomain())225 return 0;226 Variable x= Variable (1);227 if (degree (F, x) <= 1  degree (G, x) <= 1)228 return 0;229 CanonicalForm f= swapvar (F, F.mvar(), x); //TODO swapping is pretty expensive230 CanonicalForm g= swapvar (G, G.mvar(), x);231 int sizef= 0;232 int sizeg= 0;233 for (CFIterator i= f; i.hasTerms(); i++, sizef++)234 {235 if (i.exp() == 1)236 return 0;237 }238 for (CFIterator i= g; i.hasTerms(); i++, sizeg++)239 {240 if (i.exp() == 1)241 return 0;242 }243 int * expf= new int [sizef];244 int * expg= new int [sizeg];245 int j= 0;246 for (CFIterator i= f; i.hasTerms(); i++, j++)247 {248 expf [j]= i.exp();249 }250 j= 0;251 for (CFIterator i= g; i.hasTerms(); i++, j++)252 {253 expg [j]= i.exp();254 }255 256 int indf= sizef  1;257 int indg= sizeg  1;258 if (expf[indf] == 0)259 indf;260 if (expg[indg] == 0)261 indg;262 263 if (expg[indg] != expf [indf]  (expg[indg] == 1 && expf[indf] == 1))264 {265 delete [] expg;266 delete [] expf;267 return 0;268 }269 // expf[indg] == expf[indf] after here270 int result= expg[indg];271 for (int i= indf  1; i >= 0; i)272 {273 if (expf [i]%result != 0)274 {275 delete [] expg;276 delete [] expf;277 return 0;278 }279 }280 281 for (int i= indg  1; i >= 0; i)282 {283 if (expg [i]%result != 0)284 {285 delete [] expg;286 delete [] expf;287 return 0;288 }289 }290 291 delete [] expg;292 delete [] expf;293 return result;294 }295 296 // substiution297 void298 subst (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& A,299 CanonicalForm& B, const int d300 )301 {302 if (d == 1)303 {304 A= F;305 B= G;306 return;307 }308 309 CanonicalForm C= 0;310 CanonicalForm D= 0;311 Variable x= Variable (1);312 CanonicalForm f= swapvar (F, x, F.mvar());313 CanonicalForm g= swapvar (G, x, G.mvar());314 for (CFIterator i= f; i.hasTerms(); i++)315 C += i.coeff()*power (f.mvar(), i.exp()/ d);316 for (CFIterator i= g; i.hasTerms(); i++)317 D += i.coeff()*power (g.mvar(), i.exp()/ d);318 A= swapvar (C, x, F.mvar());319 B= swapvar (D, x, G.mvar());320 }321 322 CanonicalForm323 reverseSubst (const CanonicalForm& F, const int d)324 {325 if (d == 1)326 return F;327 328 Variable x= Variable (1);329 if (degree (F, x) <= 0)330 return F;331 CanonicalForm f= swapvar (F, x, F.mvar());332 CanonicalForm result= 0;333 for (CFIterator i= f; i.hasTerms(); i++)334 result += i.coeff()*power (f.mvar(), d*i.exp());335 return swapvar (result, x, F.mvar());336 }337 338 221 static inline CanonicalForm 339 222 uni_content (const CanonicalForm & F); … … 574 457 return N (gcd(A,B)); 575 458 576 int substitute= substituteCheck (A, B);577 578 if (substitute > 1)579 subst (A, B, A, B, substitute);580 581 459 CanonicalForm cA, cB; // content of A and B 582 460 CanonicalForm ppA, ppB; // primitive part of A and B … … 614 492 { 615 493 if (ppA.level() == ppB.level()) 616 { 617 if (substitute > 1) 618 return N (reverseSubst (gcd (ppA, ppB)*gcdcAcB, substitute)); 619 else 620 return N (gcd (ppA, ppB)*gcdcAcB); 621 } 494 return N (gcd (ppA, ppB)*gcdcAcB); 622 495 else 623 { 624 if (substitute > 1) 625 return N (reverseSubst (gcdcAcB, substitute)); 626 else 627 return N (gcdcAcB); 628 } 496 return N (gcdcAcB); 629 497 } 630 498 … … 643 511 { 644 512 if (ppA.level() == ppB.level()) 645 { 646 if (substitute > 1) 647 return N (reverseSubst (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB, 648 substitute)); 649 else 650 return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB); 651 } 513 return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB); 652 514 else 653 { 654 if (substitute > 1) 655 return N (reverseSubst (gcdcAcB, substitute)); 656 else 657 return N (gcdcAcB); 658 } 515 return N (gcdcAcB); 659 516 } 660 517 } … … 682 539 683 540 if (d == 0) 684 { 685 if (substitute > 1) 686 return N (reverseSubst (gcdcAcB, substitute)); 687 else 688 return N(gcdcAcB); 689 } 541 return N(gcdcAcB); 542 690 543 int d0= totaldegree (ppB, Variable(2), Variable (ppB.level())); 691 544 if (d0 < d) 692 545 d= d0; 693 546 if (d == 0) 694 { 695 if (substitute > 1) 696 return N (reverseSubst (gcdcAcB, substitute)); 697 else 698 return N(gcdcAcB); 699 } 547 return N(gcdcAcB); 700 548 701 549 CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH; … … 793 641 794 642 if (d0 == 0) 795 { 796 if (substitute > 1) 797 return N (reverseSubst (gcdcAcB, substitute)); 798 else 799 return N(gcdcAcB); 800 } 643 return N(gcdcAcB); 801 644 if (d0 > d) 802 645 { … … 847 690 if (compressConvexDense) 848 691 ppH= decompress (ppH, MM, V); 849 if (substitute > 1)850 {851 ppH= reverseSubst (ppH, substitute);852 gcdcAcB= reverseSubst (gcdcAcB, substitute);853 }854 692 return N(gcdcAcB*ppH); 855 693 } … … 859 697 if (compressConvexDense) 860 698 ppH= decompress (ppH, MM, V); 861 if (substitute > 1)862 {863 ppH= reverseSubst (ppH, substitute);864 gcdcAcB= reverseSubst (gcdcAcB, substitute);865 }866 699 return N(gcdcAcB*ppH); 867 700 } … … 946 779 return N (gcd (A, B)); 947 780 948 int substitute= substituteCheck (A, B);949 950 if (substitute > 1)951 subst (A, B, A, B, substitute);952 953 781 CanonicalForm cA, cB; // content of A and B 954 782 CanonicalForm ppA, ppB; // primitive part of A and B … … 986 814 { 987 815 if (ppA.level() == ppB.level()) 988 { 989 if (substitute > 1) 990 return N (reverseSubst (gcd (ppA, ppB)*gcdcAcB, substitute)); 991 else 992 return N (gcd (ppA, ppB)*gcdcAcB); 993 } 816 return N (gcd (ppA, ppB)*gcdcAcB); 994 817 else 995 { 996 if (substitute > 1) 997 return N (reverseSubst (gcdcAcB, substitute)); 998 else 999 return N (gcdcAcB); 1000 } 818 return N (gcdcAcB); 1001 819 } 1002 820 … … 1015 833 { 1016 834 if (ppA.level() == ppB.level()) 1017 { 1018 if (substitute > 1) 1019 return N (reverseSubst (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB, 1020 substitute)); 1021 else 1022 return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB); 1023 } 835 return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB); 1024 836 else 1025 { 1026 if (substitute > 1) 1027 return N (reverseSubst (gcdcAcB, substitute)); 1028 else 1029 return N (gcdcAcB); 1030 } 837 return N (gcdcAcB); 1031 838 } 1032 839 } … … 1053 860 int d= totaldegree (ppA, Variable(2), Variable (ppA.level())); 1054 861 if (d == 0) 1055 { 1056 if (substitute > 1) 1057 return N (reverseSubst (gcdcAcB, substitute)); 1058 else 1059 return N(gcdcAcB); 1060 } 862 return N(gcdcAcB); 1061 863 int d0= totaldegree (ppB, Variable(2), Variable (ppB.level())); 1062 864 if (d0 < d) 1063 865 d= d0; 1064 866 if (d == 0) 1065 { 1066 if (substitute > 1) 1067 return N (reverseSubst (gcdcAcB, substitute)); 1068 else 1069 return N(gcdcAcB); 1070 } 867 return N(gcdcAcB); 1071 868 1072 869 CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH; … … 1141 938 { 1142 939 if (inextension) 1143 {1144 940 setCharacteristic (p, k, gf_name_buf); 1145 { 1146 if (substitute > 1) 1147 return N (reverseSubst (gcdcAcB, substitute)); 1148 else 1149 return N(gcdcAcB); 1150 } 1151 } 1152 else 1153 { 1154 if (substitute > 1) 1155 return N (reverseSubst (gcdcAcB, substitute)); 1156 else 1157 return N(gcdcAcB); 1158 } 941 return N(gcdcAcB); 1159 942 } 1160 943 if (d0 > d) … … 1200 983 if (compressConvexDense) 1201 984 ppH= decompress (ppH, MM, V); 1202 if (substitute > 1)1203 {1204 ppH= reverseSubst (ppH, substitute);1205 gcdcAcB= reverseSubst (gcdcAcB, substitute);1206 }1207 985 setCharacteristic (p, k, gf_name_buf); 1208 986 return N(gcdcAcB*ppH); … … 1215 993 if (compressConvexDense) 1216 994 ppH= decompress (ppH, MM, V); 1217 if (substitute > 1)1218 {1219 ppH= reverseSubst (ppH, substitute);1220 gcdcAcB= reverseSubst (gcdcAcB, substitute);1221 }1222 995 return N(gcdcAcB*ppH); 1223 996 } … … 1310 1083 return N (gcd (A, B)); 1311 1084 1312 int substitute= substituteCheck (A, B);1313 1314 if (substitute > 1)1315 subst (A, B, A, B, substitute);1316 1317 1085 CanonicalForm cA, cB; // content of A and B 1318 1086 CanonicalForm ppA, ppB; // primitive part of A and B … … 1350 1118 { 1351 1119 if (ppA.level() == ppB.level()) 1352 { 1353 if (substitute > 1) 1354 return N (reverseSubst (gcd (ppA, ppB)*gcdcAcB, substitute)); 1355 else 1356 return N (gcd (ppA, ppB)*gcdcAcB); 1357 } 1120 return N (gcd (ppA, ppB)*gcdcAcB); 1358 1121 else 1359 { 1360 if (substitute > 1) 1361 return N (reverseSubst (gcdcAcB, substitute)); 1362 else 1363 return N (gcdcAcB); 1364 } 1122 return N (gcdcAcB); 1365 1123 } 1366 1124 … … 1379 1137 { 1380 1138 if (ppA.level() == ppB.level()) 1381 { 1382 if (substitute > 1) 1383 return N (reverseSubst (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB, 1384 substitute)); 1385 else 1386 return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB); 1387 } 1139 return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB); 1388 1140 else 1389 { 1390 if (substitute > 1) 1391 return N (reverseSubst (gcdcAcB, substitute)); 1392 else 1393 return N (gcdcAcB); 1394 } 1141 return N (gcdcAcB); 1395 1142 } 1396 1143 } … … 1418 1165 1419 1166 if (d == 0) 1420 { 1421 if (substitute > 1) 1422 return N (reverseSubst (gcdcAcB, substitute)); 1423 else 1424 return N(gcdcAcB); 1425 } 1167 return N(gcdcAcB); 1168 1426 1169 d0= totaldegree (ppB, Variable (2), Variable (ppB.level())); 1427 1170 … … 1430 1173 1431 1174 if (d == 0) 1432 { 1433 if (substitute > 1) 1434 return N (reverseSubst (gcdcAcB, substitute)); 1435 else 1436 return N(gcdcAcB); 1437 } 1175 return N(gcdcAcB); 1438 1176 1439 1177 CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH; … … 1570 1308 1571 1309 if (d0 == 0) 1572 { 1573 if (substitute > 1) 1574 return N (reverseSubst (gcdcAcB, substitute)); 1575 else 1576 return N(gcdcAcB); 1577 } 1310 return N(gcdcAcB); 1578 1311 if (d0 > d) 1579 1312 { … … 1617 1350 if (compressConvexDense) 1618 1351 ppH= decompress (ppH, MM, V); 1619 if (substitute > 1)1620 {1621 ppH= reverseSubst (ppH, substitute);1622 gcdcAcB= reverseSubst (gcdcAcB, substitute);1623 }1624 1352 return N(gcdcAcB*ppH); 1625 1353 } … … 3049 2777 return N (gcd (A, B)); 3050 2778 3051 int substitute= substituteCheck (A, B);3052 3053 if (substitute > 1)3054 subst (A, B, A, B, substitute);3055 3056 2779 CanonicalForm cA, cB; // content of A and B 3057 2780 CanonicalForm ppA, ppB; // primitive part of A and B … … 3095 2818 3096 2819 if (d == 0) 3097 { 3098 if (substitute > 1) 3099 return N(reverseSubst (gcdcAcB, substitute)); 3100 else 3101 return N(gcdcAcB); 3102 } 2820 return N(gcdcAcB); 3103 2821 d0= totaldegree (ppB, Variable (2), Variable (ppB.level())); 3104 2822 … … 3107 2825 3108 2826 if (d == 0) 3109 { 3110 if (substitute > 1) 3111 return N(reverseSubst (gcdcAcB, substitute)); 3112 else 3113 return N(gcdcAcB); 3114 } 2827 return N(gcdcAcB); 3115 2828 3116 2829 CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton; … … 3212 2925 3213 2926 if (d0 == 0) 3214 { 3215 if (substitute > 1) 3216 return N(reverseSubst (gcdcAcB, substitute)); 3217 else 3218 return N(gcdcAcB); 3219 } 2927 return N(gcdcAcB); 3220 2928 if (d0 > d) 3221 2929 { … … 3260 2968 ppH /= Lc(ppH); 3261 2969 DEBOUTLN (cerr, "ppH after mapDown= " << ppH); 3262 if (substitute > 1)3263 {3264 ppH= reverseSubst (ppH, substitute);3265 gcdcAcB= reverseSubst (gcdcAcB, substitute);3266 }3267 2970 return N(gcdcAcB*ppH); 3268 2971 } 3269 2972 } 3270 2973 else if (fdivides (ppH, ppA) && fdivides (ppH, ppB)) 3271 {3272 if (substitute > 1)3273 {3274 ppH= reverseSubst (ppH, substitute);3275 gcdcAcB= reverseSubst (gcdcAcB, substitute);3276 }3277 2974 return N(gcdcAcB*ppH); 3278 }3279 2975 } 3280 2976 G_m= H; … … 3398 3094 3399 3095 if (d0 == 0) 3400 { 3401 if (substitute > 1) 3402 return N(reverseSubst (gcdcAcB, substitute)); 3403 else 3404 return N(gcdcAcB); 3405 } 3096 return N(gcdcAcB); 3406 3097 if (d0 > d) 3407 3098 { … … 3450 3141 ppH /= Lc(ppH); 3451 3142 DEBOUTLN (cerr, "ppH after mapDown= " << ppH); 3452 if (substitute > 1)3453 {3454 ppH= reverseSubst (ppH, substitute);3455 gcdcAcB= reverseSubst (gcdcAcB, substitute);3456 }3457 3143 return N(gcdcAcB*ppH); 3458 3144 } … … 3460 3146 else if (fdivides (ppH, ppA) && fdivides (ppH, ppB)) 3461 3147 { 3462 if (substitute > 1)3463 {3464 ppH= reverseSubst (ppH, substitute);3465 gcdcAcB= reverseSubst (gcdcAcB, substitute);3466 }3467 3148 return N(gcdcAcB*ppH); 3468 3149 } … … 3507 3188 return N (gcd (A, B)); 3508 3189 3509 int substitute= substituteCheck (A, B);3510 3511 if (substitute > 1)3512 subst (A, B, A, B, substitute);3513 3514 3190 CanonicalForm cA, cB; // content of A and B 3515 3191 CanonicalForm ppA, ppB; // primitive part of A and B … … 3553 3229 3554 3230 if (d == 0) 3555 { 3556 if (substitute > 1) 3557 return N(reverseSubst (gcdcAcB, substitute)); 3558 else 3559 return N(gcdcAcB); 3560 } 3231 return N(gcdcAcB); 3232 3561 3233 d0= totaldegree (ppB, Variable (2), Variable (ppB.level())); 3562 3234 … … 3565 3237 3566 3238 if (d == 0) 3567 { 3568 if (substitute > 1) 3569 return N(reverseSubst (gcdcAcB, substitute)); 3570 else 3571 return N(gcdcAcB); 3572 } 3239 return N(gcdcAcB); 3573 3240 3574 3241 CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton; … … 3713 3380 3714 3381 if (d0 == 0) 3715 { 3716 if (substitute > 1) 3717 return N(reverseSubst (gcdcAcB, substitute)); 3718 else 3719 return N(gcdcAcB); 3720 } 3382 return N(gcdcAcB); 3721 3383 if (d0 > d) 3722 3384 { … … 3756 3418 3757 3419 if (fdivides (ppH, ppA) && fdivides (ppH, ppB)) 3758 {3759 if (substitute > 1)3760 {3761 ppH= reverseSubst (ppH, substitute);3762 gcdcAcB= reverseSubst (gcdcAcB, substitute);3763 }3764 3420 return N(gcdcAcB*ppH); 3765 }3766 3421 } 3767 3422 G_m= H; … … 3937 3592 3938 3593 if (d0 == 0) 3939 { 3940 if (substitute > 1) 3941 return N(reverseSubst (gcdcAcB, substitute)); 3942 else 3943 return N(gcdcAcB); 3944 } 3594 return N(gcdcAcB); 3945 3595 if (d0 > d) 3946 3596 { … … 3981 3631 DEBOUTLN (cerr, "ppH= " << ppH); 3982 3632 if (fdivides (ppH, ppA) && fdivides (ppH, ppB)) 3983 {3984 if (substitute > 1)3985 {3986 ppH= reverseSubst (ppH, substitute);3987 gcdcAcB= reverseSubst (gcdcAcB, substitute);3988 }3989 3633 return N(gcdcAcB*ppH); 3990 }3991 3634 } 3992 3635
Note: See TracChangeset
for help on using the changeset viewer.