Changeset afd067 in git


Ignore:
Timestamp:
Aug 22, 2005, 7:24:02 PM (19 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
Children:
dbb5b323a019a8f9237ef8f8617f358c43046074
Parents:
42de8e63b3e9b4283abf78c542e5012da1723bdf
Message:
*hannes: gcd/ezgcd revisited
         (fac_ezgcd.cc: OPTIMALVAR, cf_reval.cc: MORE_ZEROES)


git-svn-id: file:///usr/local/Singular/svn/trunk@8542 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
factory
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • factory/cf_factor.cc

    r42de8e6 rafd067  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_factor.cc,v 1.25 2005-07-08 14:36:31 Singular Exp $ */
     2/* $Id: cf_factor.cc,v 1.26 2005-08-22 17:24:01 Singular Exp $ */
    33
    44//{{{ docu
    … …  
    2727#include "fac_sqrfree.h"
    2828#include "cf_algorithm.h"
     29#include "cf_map.h"
    2930
    3031#include "int_int.h"
    … …  
    333334    }
    334335    else
     336    {
    335337      F = ZFactorizeMultivariate( fz, issqrfree );
     338    }
    336339
    337340    if ( on_rational )

  • factory/cf_random.cc

    r42de8e6 rafd067  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_random.cc,v 1.6 1997-12-08 18:24:25 schmidt Exp $ */
     2/* $Id: cf_random.cc,v 1.7 2005-08-22 17:24:01 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    7676IntRandom::IntRandom()
    7777{
    78     max = 100;
     78    max = 50;
    7979}
    8080
    … …  
    8888CanonicalForm IntRandom::generate() const
    8989{
    90     return factoryrandom( max );
     90    return factoryrandom( 2*max )-max;
    9191}
    9292

  • factory/cf_reval.cc

    r42de8e6 rafd067  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_reval.cc,v 1.3 2001-01-19 18:11:50 Singular Exp $ */
     2/* $Id: cf_reval.cc,v 1.4 2005-08-22 17:24:01 Singular Exp $ */
     3
     4#define MORE_ZEROES
    35
    46#include <config.h>
    … …  
    1719        gen = e.gen->clone();
    1820    values = e.values;
     21    cnt = e.cnt;
    1922}
    2023
    … …  
    3235          delete gen;
    3336        values = e.values;
     37        cnt = e.cnt;
    3438        if ( e.gen == 0 )
    3539            gen = 0;
    … …  
    4751        values[i] = gen->generate();
    4852}
     53
     54void
     55REvaluation::nextpoint_0()
     56{
     57    int n = values.max();
     58#ifdef MORE_ZEROES
     59   // for ( int i = values.min(); i <= n; i++ )
     60//      values[i] = gen->generate();
     61  if (cnt<=n /* values.max() */ )
     62  {
     63    cnt++;
     64    int t;
     65    if (values.min()<n)
     66    {
     67      do
     68      {
     69        t=factoryrandom(n);
     70      }
     71      while (t<values.min());
     72    }
     73    else t=n;
     74    values[t]=gen->generate();
     75  }
     76  else
     77#endif
     78  {
     79    for ( int i = values.min(); i <= n; i++ )
     80        values[i] = gen->generate();
     81  }
     82}

  • factory/cf_reval.h

    r42de8e6 rafd067  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_reval.h,v 1.3 1997-06-19 12:23:56 schmidt Exp $ */
     2/* $Id: cf_reval.h,v 1.4 2005-08-22 17:24:01 Singular Exp $ */
    33
    44#ifndef INCL_CF_REVAL_H
    … …  
    1717private:
    1818    CFRandom * gen;
     19    int cnt;
    1920public:
    2021    REvaluation() : Evaluation(), gen(0) {}
    21     REvaluation( int min, int max, const CFRandom & sample ) : Evaluation( min, max ), gen( sample.clone() ) {}
     22    REvaluation( int min, int max, const CFRandom & sample ) : Evaluation( min, max ), gen( sample.clone() ) { cnt=1;}
    2223    REvaluation( const REvaluation & e );
    2324    ~REvaluation();
    2425    REvaluation& operator= ( const REvaluation & e );
    2526    void nextpoint();
     27    void nextpoint_0();
    2628};
    2729

  • factory/fac_ezgcd.cc

    r42de8e6 rafd067  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_ezgcd.cc,v 1.20 2005-08-19 10:59:19 pohl Exp $ */
     2/* $Id: fac_ezgcd.cc,v 1.21 2005-08-22 17:24:01 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    1919#define OPTIMALVAR 1
    2020
     21static void findeval( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db, REvaluation & b, int delta, int degF, int degG );
     22
     23static CanonicalForm ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b, bool internal );
     24
     25static CanonicalForm ezgcd_specialcase ( const CanonicalForm & F, const CanonicalForm & G, REvaluation & b, const modpk & bound );
     26
     27static modpk findBound ( const CanonicalForm & F, const CanonicalForm & G, const CanonicalForm & lcF, const CanonicalForm & lcG, int degF, int degG );
     28
     29static modpk enlargeBound ( const CanonicalForm & F, const CanonicalForm & Lb, const CanonicalForm & Db, const modpk & pk );
     30
    2131#ifdef OPTIMALVAR
    22 static Variable getOptimalVar( const CanonicalForm & FF, const CanonicalForm & GG );
    23 #endif
    24 
    25 static void findeval( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db, REvaluation & b, int delta, int degF, int degG );
    26 
    27 static CanonicalForm ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b, bool internal );
    28 
    29 static CanonicalForm ezgcd_specialcase ( const CanonicalForm & F, const CanonicalForm & G, REvaluation & b, const modpk & bound );
    30 
    31 static modpk findBound ( const CanonicalForm & F, const CanonicalForm & G, const CanonicalForm & lcF, const CanonicalForm & lcG, int degF, int degG );
    32 
    33 static modpk enlargeBound ( const CanonicalForm & F, const CanonicalForm & Lb, const CanonicalForm & Db, const modpk & pk );
    34 
    35 #ifdef OPTIMALVAR
     32static Variable ezgcd_getOptimalVar( const CanonicalForm & FF, const CanonicalForm & GG );
     33
     34
    3635CanonicalForm ezgcd( const CanonicalForm & FF, const CanonicalForm & GG )
    3736{
    3837  CanonicalForm F,G;
    3938  REvaluation b;
    40   Variable Z=getOptimalVar(FF,GG);
     39  Variable Z=ezgcd_getOptimalVar(FF,GG);
    4140//Test:  return Z;
    42   if(Z==Variable(1)){return ezgcd( FF, GG, b, false );}
     41  if(Z==Variable(1))
     42     return ezgcd( FF, GG, b, false );
    4343  F=swapvar(FF,Z,Variable(1));
    4444  G=swapvar(GG,Z,Variable(1));
    … …  
    8989    bound = findBound( F, G, lcF, lcG, degF, degG );
    9090    if ( ! internal )
    91         b = REvaluation( 2, t, IntRandom( 50 ) );
     91        b = REvaluation( 2, t, IntRandom( 25 ) );
    9292    while ( ! gcdfound ) {
    9393        /// ---> A2
    … …  
    103103        /// ---> A3
    104104        if ( delta == 0 )
    105         {
     105        {
    106106          DEBDECLEVEL( cerr, "ezgcd" );
    107107          return d;
    108         }
     108        }
    109109        /// ---> A4
    110110        //deltaold = delta;
    … …  
    112112            bt = b;
    113113            findeval( F, G, Fbt, Gbt, Dbt, bt, delta + 1, degF, degG );
    114             int dd=degree( Dbt );
     114            int dd=degree( Dbt );
    115115            if ( dd /*degree( Dbt )*/ == 0 )
    116             {
     116            {
    117117                DEBDECLEVEL( cerr, "ezgcd" );
    118118                return d;
    119             }
     119            }
    120120            if ( dd /*degree( Dbt )*/ == delta )
    121121                break;
    … …  
    132132            DEBDECLEVEL( cerr, "ezgcd" );
    133133            return d*F;
    134         }
     134        }
    135135        if ( degG < degF && delta == degG && divides( G, F ) )
    136136        {
    137137            DEBDECLEVEL( cerr, "ezgcd" );
    138138            return d*G;
    139         }
     139        }
    140140        if ( delta != degF && delta != degG ) {
    141141            /// ---> A6
    … …  
    143143            //if ( gcd( (DD[1] = Fb / Db), Db ) == 1 ) {
    144144            DD[1] = Fb / Db;
    145             xxx= gcd( DD[1], Db );
     145            xxx= gcd( DD[1], Db );
    146146            DEBOUTLN( cerr, "gcd((Fb/Db),Db) = " << xxx );
    147147            DEBOUTLN( cerr, "Fb/Db = " << DD[1] );
    148148            DEBOUTLN( cerr, "Db = " << Db );
    149             if (xxx.inCoeffDomain()) {
     149            if (xxx.inCoeffDomain()) {
    150150                B = F;
    151151                DD[2] = Db;
    … …  
    155155            }
    156156            //else  if ( gcd( (DD[1] = Gb / Db), Db ) == 1 ) {
    157             else
    158             { 
     157            else
     158            {
    159159              DD[1] = Gb / Db;
    160               xxx=gcd( DD[1], Db );
     160              xxx=gcd( DD[1], Db );
    161161              DEBOUTLN( cerr, "gcd((Gb/Db),Db) = " << xxx );
    162162              DEBOUTLN( cerr, "Gb/Db = " << DD[1] );
    163163              DEBOUTLN( cerr, "Db = " << Db );
    164               if (xxx.inCoeffDomain())
     164              if (xxx.inCoeffDomain())
    165165              {
    166166                B = G;
    … …  
    180180#endif
    181181              }
    182             }
     182            }
    183183            /// ---> A7
    184184            DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
    … …  
    192192            gcdfound = Hensel( B, DD, lcDD, b, bound, x );
    193193            DEBOUTLN( cerr, "(hensel finished) DD   = " << DD );
    194            
    195             if (gcdfound)
    196             {
     194
     195            if (gcdfound)
     196            {
    197197              CanonicalForm cand=DD[2] / content(DD[2],Variable(1));
    198               if (B==F)
    199               {
     198              if (B==F)
     199              {
    200200                DEBOUTLN( cerr, "(test) G: "<<G<<" % gcd:"<<cand<<" -> " << G%cand );
    201201                gcdfound= divides(cand,G);
    202202              }
    203               else
    204               {
     203              else
     204              {
    205205                DEBOUTLN( cerr, "(test) F: "<<F<<" % gcd:"<<cand<<" -> " << F%cand);
    206206                gcdfound= divides(cand,F);
    207               }
    208             }
     207              }
     208            }
    209209            /// ---> A8 (gcdfound)
    210210        }
    … …  
    236236        //     '(16*B^8-208*B^6*C+927*B^4*C^2-1512*B^2*C^3+432*C^4)' \
    237237        //     '(4*B^7*C^2-50*B^5*C^3+208*B^3*C^4-288*B*C^5)'
    238         b.nextpoint();
    239         return ezgcd( F, G, b, true );
     238        b.nextpoint_0();
     239        return ezgcd( F, G, b, true );
    240240    }
    241241#if 1
    … …  
    314314    bool ok;
    315315    if ( delta != 0 )
    316         b.nextpoint();
     316        b.nextpoint_0();
    317317    DEBOUTLN( cerr, "ezgcd: (findeval) F = " << F  <<", G="<< G);
    318318    DEBOUTLN( cerr, "ezgcd: (findeval) degF = " << degF << ", degG="<<degG );
    … …  
    325325            ok = degree( Gb ) == degG;
    326326        }
    327        
     327
    328328        if ( ok )
    329         {   
     329        {
    330330            Db = gcd( Fb, Gb );
    331331            if ( delta > 0 )
    … …  
    333333        }
    334334        if ( ! ok )
    335             b.nextpoint();
     335        {
     336            b.nextpoint_0();
     337        }
    336338    } while ( ! ok );
    337339}
    … …  
    380382
    381383#ifdef OPTIMALVAR
    382 static Variable getOptimalVar( const CanonicalForm & FF, const CanonicalForm & GG )
    383 {
    384   int ii,tt,d,dd,s,so;
    385   CanonicalForm F,G,Fbz,Gbz,Dbz;
     384static Variable ezgcd_getOptimalVar( const CanonicalForm & FF, const CanonicalForm & GG )
     385{
     386  int ii,tt,d,s,dd,so;
     387  CanonicalForm F,G;
    386388  Variable opt=Variable(1);
    387   if((FF.level()<3)||(GG.level()<3)){return opt;}
    388   REvaluation bz=REvaluation(2,tmax(FF.level(),GG.level()),IntRandom(50));
    389   Fbz=bz(FF);
    390   Gbz=bz(GG);
    391   Dbz=gcd(Fbz,Gbz);
    392   dd=degree(Dbz);
    393   so=size(Dbz);
    394389  tt=FF.level();
    395   if(GG.level()<tt){tt=GG.level();}
     390  if(GG.level()<tt)
     391    tt=GG.level();
     392  if(tt<3 /*(FF.level()<3)||(GG.level()<3)*/)
     393    return opt;
     394  REvaluation bz=REvaluation(2,tmax(FF.level(),GG.level()),IntRandom(1));
     395  CanonicalForm Fbz=bz(FF);
     396  CanonicalForm Gbz=bz(GG);
     397  CanonicalForm Dbz0=gcd(Fbz,Gbz);
     398  dd=degree(Dbz0);
     399  so=-1;
    396400  for(ii=2;ii<=tt;ii++)
    397401  {
     402    //bz.nextpoint();
    398403    F=swapvar(FF,Variable(ii),Variable(1));
    399404    G=swapvar(GG,Variable(ii),Variable(1));
    400405    Fbz=bz(F);
    401406    Gbz=bz(G);
    402     Dbz=gcd(Fbz,Gbz);
     407    CanonicalForm Dbz=gcd(Fbz,Gbz);
    403408    d=degree(Dbz);
    404409    if(d==dd)
    405410    {
    406411      s=size(Dbz);
    407       if(s>so){so=s;opt=Variable(ii);}
    408     }
    409     if(d>dd){dd=d;so=size(Dbz);opt=Variable(ii);}
     412      if (so==-1)
     413      {
     414        so=size(Dbz0);
     415      }
     416      if(s>so)
     417      {
     418        so=s;
     419        opt=Variable(ii);
     420        Dbz0=Dbz;
     421      }
     422    }
     423    else if(d>dd)
     424    {
     425      dd=d;
     426      so=-1;
     427      opt=Variable(ii);
     428      Dbz0=Dbz;
     429    }
    410430  }
    411431  return opt;

  • factory/fac_multivar.cc

    r42de8e6 rafd067  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_multivar.cc,v 1.11 2005-06-28 14:39:52 Singular Exp $ */
     2/* $Id: fac_multivar.cc,v 1.12 2005-08-22 17:24:02 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    203203    CFArray G, lcG, D;
    204204    int i, j, k, m, r, maxdeg, h;
    205     REvaluation A( 2, t, IntRandom( 100 ) );
     205    REvaluation A( 2, t, IntRandom( 50 ) );
    206206    CanonicalForm U0;
    207207    CanonicalForm ft, ut, gt, d;
Note: See TracChangeset for help on using the changeset viewer.