Changeset dd3e561 in git for factory/cf_gcd.cc


Ignore:
Timestamp:
Oct 24, 1997, 6:46:20 PM (27 years ago)
Author:
Jens Schmidt <schmidt@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
f2c84a8a2d37c2bf2c56dd13ca31097ff890da91
Parents:
c82e7910ebf6204b5d83978ce3ff54bf94d8b019
Message:
	* cf_gcd.cc (gcd): bug fix.  Handles polynomials with rational
	  coefficients correctly

	* cf_gcd.cc (maxnorm): spurious variable `h' removed

	* cf_gcd.cc (balance): slightly speeded up

	* cf_gcd.cc (chinesePoly): function removed
	(gcd_poly_univar0): slightly speeded up

	* cf_gcd.cc (lcm): bug fix.  Returns zero now if f or g equals
	  zero.

	* cf_gcd.cc (gcd_poly): does not call sparsemod on univariate
	  polynomials an longer

	* cf_gcd.cc (vcontent): assertion added.

	* cf_gcd.cc (content( CF, Variable )): slightly speeded up.
	  Assertion added.


git-svn-id: file:///usr/local/Singular/svn/trunk@844 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/cf_gcd.cc

    rc82e791 rdd3e561  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_gcd.cc,v 1.14 1997-09-12 15:27:25 schmidt Exp $ */
     2/* $Id: cf_gcd.cc,v 1.15 1997-10-24 16:46:20 schmidt Exp $ */
    33
    44#include <config.h>
    … …  
    6161}
    6262
     63//{{{ static CanonicalForm maxnorm ( const CanonicalForm & f )
     64//{{{ docu
     65//
     66// maxnorm() - return the maximum of the absolute values of all
     67//   coefficients of f.
     68//
     69// The absolute value and the maximum are calculated with respect
     70// to operator < on canonical forms which is most meaningful for
     71// rational numbers and integers.
     72//
     73// Used by gcd_poly_univar0().
     74//
     75//}}}
    6376static CanonicalForm
    6477maxnorm ( const CanonicalForm & f )
    6578{
    66     CanonicalForm m = 0, h;
     79    CanonicalForm m = 0;
    6780    CFIterator i;
    6881    for ( i = f; i.hasTerms(); i++ )
    … …  
    7083    return m;
    7184}
    72 
    73 static void
    74 chinesePoly ( const CanonicalForm & f1, const CanonicalForm & q1, const CanonicalForm & f2, const CanonicalForm & q2, CanonicalForm & f, CanonicalForm & q )
    75 {
    76     CFIterator i1 = f1, i2 = f2;
    77     CanonicalForm c;
    78     Variable x = f1.mvar();
    79     f = 0;
    80     while ( i1.hasTerms() && i2.hasTerms() ) {
    81         if ( i1.exp() == i2.exp() ) {
    82             chineseRemainder( i1.coeff(), q1, i2.coeff(), q2, c, q );
    83             f += power( x, i1.exp() ) * c;
    84             i1++; i2++;
    85         }
    86         else if ( i1.exp() > i2.exp() ) {
    87             chineseRemainder( 0, q1, i2.coeff(), q2, c, q );
    88             f += power( x, i2.exp() ) * c;
    89             i2++;
    90         }
    91         else {
    92             chineseRemainder( i1.coeff(), q1, 0, q2, c, q );
    93             f += power( x, i1.exp() ) * c;
    94             i1++;
    95         }
    96     }
    97     while ( i1.hasTerms() ) {
    98         chineseRemainder( i1.coeff(), q1, 0, q2, c, q );
    99         f += power( x, i1.exp() ) * c;
    100         i1++;
    101     }
    102     while ( i2.hasTerms() ) {
    103         chineseRemainder( 0, q1, i2.coeff(), q2, c, q );
    104         f += power( x, i2.exp() ) * c;
    105         i2++;
    106     }
    107 }
    108 
     85//}}}
     86
     87//{{{ static CanonicalForm balance ( const CanonicalForm & f, const CanonicalForm & q )
     88//{{{ docu
     89//
     90// balance() - map f from positive to symmetric representation
     91//   mod q.
     92//
     93// This makes sense for univariate polynomials over Z only.
     94// q should be an integer.
     95//
     96// Used by gcd_poly_univar0().
     97//
     98//}}}
    10999static CanonicalForm
    110100balance ( const CanonicalForm & f, const CanonicalForm & q )
    111101{
    112     CFIterator i;
     102    Variable x = f.mvar();
    113103    CanonicalForm result = 0, qh = q / 2;
    114104    CanonicalForm c;
    115     Variable x = f.mvar();
     105    CFIterator i;
    116106    for ( i = f; i.hasTerms(); i++ ) {
    117         c = i.coeff() % q;
     107        c = mod( i.coeff(), q );
    118108        if ( c > qh )
    119109            result += power( x, i.exp() ) * (c - q);
    … …  
    123113    return result;
    124114}
    125 
     115//}}}
     116
     117//{{{ CanonicalForm igcd ( const CanonicalForm & f, const CanonicalForm & g )
     118//{{{ docu
     119//
     120// igcd() - return integer gcd of f and g.
     121//
     122// Calculates the integer gcd of f and g using the euclidean
     123// algorithm if f and g are integers and we are not calculating
     124// in Q.  Returns one in all other cases.  Normalizes result.
     125//
     126//}}}
    126127CanonicalForm
    127128igcd ( const CanonicalForm & f, const CanonicalForm & g )
    … …  
    142143        return 1;
    143144}
    144 
     145//}}}
     146
     147//{{{ static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
     148//{{{ docu
     149//
     150// icontent() - return gcd of c and all coefficients of f which
     151//   are in a coefficient domain.
     152//
     153// Used by icontent().
     154//
     155//}}}
    145156static CanonicalForm
    146157icontent ( const CanonicalForm & f, const CanonicalForm & c )
    … …  
    155166    }
    156167}
    157 
     168//}}}
     169
     170//{{{ CanonicalForm icontent ( const CanonicalForm & f )
     171//{{{ docu
     172//
     173// icontent() - return gcd over all coefficients of f which are
     174//   in a coefficient domain.
     175//
     176//}}}
    158177CanonicalForm
    159178icontent ( const CanonicalForm & f )
    … …  
    161180    return icontent( f, 0 );
    162181}
    163 
     182//}}}
     183
     184//{{{ CanonicalForm iextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
     185//{{{ docu
     186//
     187// iextgcd() - calculate extended integer gcd.
     188//
     189// Returns gcd(f, g) and a and b sucht that f*a+g*b=gcd(f, g).
     190// The gcd is calculated using an extended euclidean polynomial
     191// remainder sequence.  Normalizes result.
     192//
     193// Note: be sure you are calculating in Z, and not in Q!
     194//
     195//}}}
    164196CanonicalForm
    165197iextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
    … …  
    185217    return p0;
    186218}
    187 
     219//}}}
     220
     221//{{{ CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
     222//{{{ docu
     223//
     224// extgcd() - returns polynomial extended gcd of f and g.
     225//
     226// Returns gcd(f, g) and a and b sucht that f*a+g*b=gcd(f, g).
     227// The gcd is calculated using an extended euclidean polynomial
     228// remainder sequence, so f and g should be polynomials over an
     229// euclidean domain.  Normalizes result.
     230//
     231// Note: be sure that f and g have the same level!
     232//
     233//}}}
    188234CanonicalForm
    189235extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
    … …  
    214260    return p0;
    215261}
     262//}}}
    216263
    217264static CanonicalForm
    … …  
    263310            else {
    264311                if ( Dp.degree() == D.degree() ) {
    265                     chinesePoly( D, q, mapinto( Dp ), p, newD, newq );
     312                    chineseRemainder( D, q, mapinto( Dp ), p, newD, newq );
    266313                    q = newq;
    267314                    D = newD;
    … …  
    291338}
    292339
    293 
    294340static CanonicalForm
    295341gcd_poly1( const CanonicalForm & f, const CanonicalForm & g, bool modularflag )
    … …  
    341387}
    342388
    343 
     389//{{{ static CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g, bool modularflag )
     390//{{{ docu
     391//
     392// gcd_poly() - calculate polynomial gcd.
     393//
     394// This is the dispatcher for polynomial gcd calculation.  We call either
     395// ezgcd(), sparsemod() or gcd_poly1() in dependecy on the current
     396// characteristic and settings of SW_USE_EZGCD and SW_USE_SPARSEMOD, resp.
     397//
     398// modularflag is reached down to gcd_poly1() without change in case of
     399// zero characteristic.
     400//
     401// Used by gcd() and gcd_poly_univar0().
     402//
     403//}}}
    344404static CanonicalForm
    345 gcd_poly( const CanonicalForm & f, const CanonicalForm & g, bool modularflag )
     405gcd_poly ( const CanonicalForm & f, const CanonicalForm & g, bool modularflag )
    346406{
    347407    if ( getCharacteristic() != 0 ) {
    … …  
    353413        return N( ezgcd( M(f), M(g) ) );
    354414    }
    355     else if ( isOn( SW_USE_SPARSEMOD ) ) {
     415    else if ( isOn( SW_USE_SPARSEMOD ) && ! ( f.isUnivariate() && g.isUnivariate() ) ) {
    356416        return sparsemod( f, g );
    357417    }
    … …  
    360420    }
    361421}
    362 
    363 
     422//}}}
     423
     424//{{{ static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
     425//{{{ docu
     426//
     427// cf_content() - return gcd(g, content(f)).
     428//
     429// content(f) is calculated with respect to f's main variable.
     430//
     431// Used by gcd(), content(), content( CF, Variable ).
     432//
     433//}}}
    364434static CanonicalForm
    365435cf_content ( const CanonicalForm & f, const CanonicalForm & g )
    … …  
    380450            return f;
    381451}
     452//}}}
    382453
    383454//{{{ CanonicalForm content ( const CanonicalForm & f )
    … …  
    386457// content() - return content(f) with respect to main variable.
    387458//
     459// Normalizes result.
     460//
    388461//}}}
    389462CanonicalForm
    … …  
    394467//}}}
    395468
     469//{{{ CanonicalForm content ( const CanonicalForm & f, const Variable & x )
     470//{{{ docu
     471//
     472// content() - return content(f) with respect to x.
     473//
     474// x should be a polynomial variable.
     475//
     476//}}}
    396477CanonicalForm
    397478content ( const CanonicalForm & f, const Variable & x )
    398479{
    399     if ( f.mvar() == x )
     480    ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
     481    Variable y = f.mvar();
     482
     483    if ( y == x )
    400484        return cf_content( f, 0 );
    401     else  if ( f.mvar() < x )
     485    else  if ( y < x )
    402486        return f;
    403487    else
    404         return swapvar( content( swapvar( f, f.mvar(), x ), f.mvar() ), f.mvar(), x );
    405 }
    406 
     488        return swapvar( content( swapvar( f, y, x ), y ), y, x );
     489}
     490//}}}
     491
     492//{{{ CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
     493//{{{ docu
     494//
     495// vcontent() - return content of f with repect to variables >= x.
     496//
     497// The content is recursively calculated over all coefficients in
     498// f having level less than x.  x should be a polynomial
     499// variable.
     500//
     501//}}}
    407502CanonicalForm
    408503vcontent ( const CanonicalForm & f, const Variable & x )
    409504{
     505    ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
     506
    410507    if ( f.mvar() <= x )
    411508        return content( f, x );
    … …  
    418515    }
    419516}
     517//}}}
    420518
    421519//{{{ CanonicalForm pp ( const CanonicalForm & f )
    … …  
    423521//
    424522// pp() - return primitive part of f.
     523//
     524// Returns zero if f equals zero, otherwise f / content(f).
    425525//
    426526//}}}
    … …  
    470570                    return g;
    471571            if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) {
     572                CanonicalForm cdF = common_den( f );
     573                CanonicalForm cdG = common_den( g );
    472574                Off( SW_RATIONAL );
    473                 CanonicalForm l = lcm( common_den( f ), common_den( g ) );
     575                CanonicalForm l = lcm( cdF, cdG );
    474576                On( SW_RATIONAL );
    475577                CanonicalForm F = f * l, G = g * l;
    … …  
    496598}
    497599
     600//{{{ CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
     601//{{{ docu
     602//
     603// lcm() - return least common multiple of f and g.
     604//
     605// The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).
     606//
     607// Returns zero if one of f or g equals zero.
     608//
     609//}}}
    498610CanonicalForm
    499611lcm ( const CanonicalForm & f, const CanonicalForm & g )
    500612{
    501     return ( f / gcd( f, g ) ) * g;
    502 }
     613    if ( f.isZero() || g.isZero() )
     614        return f;
     615    else
     616        return ( f / gcd( f, g ) ) * g;
     617}
     618//}}}
Note: See TracChangeset for help on using the changeset viewer.