Changeset a9a6dcb in git


Ignore:
Timestamp:
Apr 13, 2012, 11:19:24 AM (11 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
Children:
f7a4e9271997208f4ee40a14fd1e1b5c6c0c1ffc
Parents:
e24341824b73ccd926669238b426c9c0ee24664b
git-author:
Martin Lee <martinlee84@web.de>2012-04-13 11:19:24+02:00
git-committer:
Martin Lee <martinlee84@web.de>2012-05-07 14:14:08+02:00
Message:
chg: reduce overhead in gcd
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/cf_gcd_smallp.cc

    re243418 ra9a6dcb  
    219219}
    220220
    221 int
    222 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 expensive
    230   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 here
    270   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 // substiution
    297 void
    298 subst (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& A,
    299        CanonicalForm& B, const int d
    300       )
    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 CanonicalForm
    323 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 
    338221static inline CanonicalForm
    339222uni_content (const CanonicalForm & F);
    … …  
    574457    return N (gcd(A,B));
    575458
    576   int substitute= substituteCheck (A, B);
    577 
    578   if (substitute > 1)
    579     subst (A, B, A, B, substitute);
    580 
    581459  CanonicalForm cA, cB;    // content of A and B
    582460  CanonicalForm ppA, ppB;    // primitive part of A and B
    … …  
    614492    {
    615493      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);
    622495      else
    623       {
    624         if (substitute > 1)
    625           return N (reverseSubst (gcdcAcB, substitute));
    626         else
    627           return N (gcdcAcB);
    628       }
     496        return N (gcdcAcB);
    629497    }
    630498
    … …  
    643511    {
    644512      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);
    652514      else
    653       {
    654         if (substitute > 1)
    655           return N (reverseSubst (gcdcAcB, substitute));
    656         else
    657           return N (gcdcAcB);
    658       }
     515        return N (gcdcAcB);
    659516    }
    660517  }
    … …  
    682539
    683540  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
    690543  int d0= totaldegree (ppB, Variable(2), Variable (ppB.level()));
    691544  if (d0 < d)
    692545    d= d0;
    693546  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);
    700548
    701549  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH;
    … …  
    793641
    794642    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);
    801644    if (d0 >  d)
    802645    {
    … …  
    847690          if (compressConvexDense)
    848691            ppH= decompress (ppH, MM, V);
    849           if (substitute > 1)
    850           {
    851             ppH= reverseSubst (ppH, substitute);
    852             gcdcAcB= reverseSubst (gcdcAcB, substitute);
    853           }
    854692          return N(gcdcAcB*ppH);
    855693        }
    … …  
    859697        if (compressConvexDense)
    860698          ppH= decompress (ppH, MM, V);
    861         if (substitute > 1)
    862         {
    863           ppH= reverseSubst (ppH, substitute);
    864           gcdcAcB= reverseSubst (gcdcAcB, substitute);
    865         }
    866699        return N(gcdcAcB*ppH);
    867700      }
    … …  
    946779    return N (gcd (A, B));
    947780
    948   int substitute= substituteCheck (A, B);
    949 
    950   if (substitute > 1)
    951     subst (A, B, A, B, substitute);
    952 
    953781  CanonicalForm cA, cB;    // content of A and B
    954782  CanonicalForm ppA, ppB;    // primitive part of A and B
    … …  
    986814    {
    987815      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);
    994817      else
    995       {
    996         if (substitute > 1)
    997           return N (reverseSubst (gcdcAcB, substitute));
    998         else
    999           return N (gcdcAcB);
    1000       }
     818        return N (gcdcAcB);
    1001819    }
    1002820
    … …  
    1015833    {
    1016834      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);
    1024836      else
    1025       {
    1026         if (substitute > 1)
    1027           return N (reverseSubst (gcdcAcB, substitute));
    1028         else
    1029           return N (gcdcAcB);
    1030       }
     837        return N (gcdcAcB);
    1031838    }
    1032839  }
    … …  
    1053860  int d= totaldegree (ppA, Variable(2), Variable (ppA.level()));
    1054861  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);
    1061863  int d0= totaldegree (ppB, Variable(2), Variable (ppB.level()));
    1062864  if (d0 < d)
    1063865    d= d0;
    1064866  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);
    1071868
    1072869  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH;
    … …  
    1141938    {
    1142939      if (inextension)
    1143       {
    1144940        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);
    1159942    }
    1160943    if (d0 >  d)
    … …  
    1200983          if (compressConvexDense)
    1201984            ppH= decompress (ppH, MM, V);
    1202           if (substitute > 1)
    1203           {
    1204             ppH= reverseSubst (ppH, substitute);
    1205             gcdcAcB= reverseSubst (gcdcAcB, substitute);
    1206           }
    1207985          setCharacteristic (p, k, gf_name_buf);
    1208986          return N(gcdcAcB*ppH);
    … …  
    1215993          if (compressConvexDense)
    1216994            ppH= decompress (ppH, MM, V);
    1217           if (substitute > 1)
    1218           {
    1219             ppH= reverseSubst (ppH, substitute);
    1220             gcdcAcB= reverseSubst (gcdcAcB, substitute);
    1221           }
    1222995          return N(gcdcAcB*ppH);
    1223996        }
    … …  
    13101083    return N (gcd (A, B));
    13111084
    1312   int substitute= substituteCheck (A, B);
    1313 
    1314   if (substitute > 1)
    1315     subst (A, B, A, B, substitute);
    1316 
    13171085  CanonicalForm cA, cB;    // content of A and B
    13181086  CanonicalForm ppA, ppB;    // primitive part of A and B
    … …  
    13501118    {
    13511119      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);
    13581121      else
    1359       {
    1360         if (substitute > 1)
    1361           return N (reverseSubst (gcdcAcB, substitute));
    1362         else
    1363           return N (gcdcAcB);
    1364       }
     1122        return N (gcdcAcB);
    13651123    }
    13661124
    … …  
    13791137    {
    13801138      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);
    13881140      else
    1389       {
    1390         if (substitute > 1)
    1391           return N (reverseSubst (gcdcAcB, substitute));
    1392         else
    1393           return N (gcdcAcB);
    1394       }
     1141        return N (gcdcAcB);
    13951142    }
    13961143  }
    … …  
    14181165
    14191166  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
    14261169  d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
    14271170
    … …  
    14301173
    14311174  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);
    14381176
    14391177  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH;
    … …  
    15701308
    15711309    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);
    15781311    if (d0 >  d)
    15791312    {
    … …  
    16171350        if (compressConvexDense)
    16181351          ppH= decompress (ppH, MM, V);
    1619         if (substitute > 1)
    1620         {
    1621           ppH= reverseSubst (ppH, substitute);
    1622           gcdcAcB= reverseSubst (gcdcAcB, substitute);
    1623         }
    16241352        return N(gcdcAcB*ppH);
    16251353      }
    … …  
    30492777    return N (gcd (A, B));
    30502778
    3051   int substitute= substituteCheck (A, B);
    3052 
    3053   if (substitute > 1)
    3054     subst (A, B, A, B, substitute);
    3055 
    30562779  CanonicalForm cA, cB;    // content of A and B
    30572780  CanonicalForm ppA, ppB;    // primitive part of A and B
    … …  
    30952818
    30962819  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);
    31032821  d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
    31042822
    … …  
    31072825
    31082826  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);
    31152828
    31162829  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton;
    … …  
    32122925
    32132926    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);
    32202928    if (d0 >  d)
    32212929    {
    … …  
    32602968          ppH /= Lc(ppH);
    32612969          DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
    3262           if (substitute > 1)
    3263           {
    3264             ppH= reverseSubst (ppH, substitute);
    3265             gcdcAcB= reverseSubst (gcdcAcB, substitute);
    3266           }
    32672970          return N(gcdcAcB*ppH);
    32682971        }
    32692972      }
    32702973      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         }
    32772974        return N(gcdcAcB*ppH);
    3278       }
    32792975    }
    32802976    G_m= H;
    … …  
    33983094
    33993095        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);
    34063097        if (d0 >  d)
    34073098        {
    … …  
    34503141              ppH /= Lc(ppH);
    34513142              DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
    3452               if (substitute > 1)
    3453               {
    3454                 ppH= reverseSubst (ppH, substitute);
    3455                 gcdcAcB= reverseSubst (gcdcAcB, substitute);
    3456               }
    34573143              return N(gcdcAcB*ppH);
    34583144            }
    … …  
    34603146          else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
    34613147          {
    3462             if (substitute > 1)
    3463             {
    3464               ppH= reverseSubst (ppH, substitute);
    3465               gcdcAcB= reverseSubst (gcdcAcB, substitute);
    3466             }
    34673148            return N(gcdcAcB*ppH);
    34683149          }
    … …  
    35073188    return N (gcd (A, B));
    35083189
    3509   int substitute= substituteCheck (A, B);
    3510 
    3511   if (substitute > 1)
    3512     subst (A, B, A, B, substitute);
    3513 
    35143190  CanonicalForm cA, cB;    // content of A and B
    35153191  CanonicalForm ppA, ppB;    // primitive part of A and B
    … …  
    35533229
    35543230  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
    35613233  d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
    35623234
    … …  
    35653237
    35663238  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);
    35733240
    35743241  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton;
    … …  
    37133380
    37143381    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);
    37213383    if (d0 >  d)
    37223384    {
    … …  
    37563418
    37573419      if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
    3758       {
    3759         if (substitute > 1)
    3760         {
    3761           ppH= reverseSubst (ppH, substitute);
    3762           gcdcAcB= reverseSubst (gcdcAcB, substitute);
    3763         }
    37643420        return N(gcdcAcB*ppH);
    3765       }
    37663421    }
    37673422    G_m= H;
    … …  
    39373592
    39383593        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);
    39453595        if (d0 >  d)
    39463596        {
    … …  
    39813631          DEBOUTLN (cerr, "ppH= " << ppH);
    39823632          if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
    3983           {
    3984             if (substitute > 1)
    3985             {
    3986               ppH= reverseSubst (ppH, substitute);
    3987               gcdcAcB= reverseSubst (gcdcAcB, substitute);
    3988             }
    39893633            return N(gcdcAcB*ppH);
    3990           }
    39913634        }
    39923635
Note: See TracChangeset for help on using the changeset viewer.