Changeset 9719434 in git for factory


Ignore:
Timestamp:
Mar 12, 1998, 11:26:14 AM (26 years ago)
Author:
Jens Schmidt <schmidt@…>
Branches:
(u'spielwiese', 'd1b01e9d51ade4b46b745d3bada5c5f3696be3a8')
Children:
041dbdc0753163b5283d5d03266a061267c59427
Parents:
91c4fc82713e72893b097592af3f701d13a4f992
Message:
	* cf_algorithm.cc (divides): slightly speeded up.

	* cf_algorithm.cc (cden, common_den): renamed to
	  `internalBCommonDen()' and `bCommonDen()', resp.  Declarations
	  adapted. All references changed.

	* cf_algorithm.cc (maxNorm, euclideanNorm): new functions.
	  Declarations added.

	* cf_algorithm.cc (internalBCommonDen): uses `blcm()' instead of
	  `lcm()'


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

Legend:

Unmodified
Added
Removed

  • factory/cf_algorithm.cc

    r91c4fc8 r9719434  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_algorithm.cc,v 1.5 1997-10-09 14:48:19 schmidt Exp $ */
     2/* $Id: cf_algorithm.cc,v 1.6 1998-03-12 10:26:14 schmidt Exp $ */
    33
    44//{{{ docu
    … …  
    1414//
    1515// Used by: cf_gcd.cc, cf_resultant.cc, fac_distrib.cc,
    16 //   fac_ezgcd.cc, sm_sparsemod.cc
     16//   fac_ezgcd.cc, fac_util.cc, sm_sparsemod.cc
    1717//
    1818//}}}
    … …  
    2424#include "cf_defs.h"
    2525#include "canonicalform.h"
     26#include "cf_algorithm.h"
    2627#include "variable.h"
    2728#include "cf_iter.h"
    … …  
    3031//{{{ docu
    3132//
    32 // psr() - calculate pseudo remainder of f and g with respect to x.
    33 //
    34 // x should be a polynomial variable.
     33// psr() - calculate pseudo remainder of `f' and `g' with respect
     34//   to `x'.
     35//
     36// `x' should be a polynomial variable, `g' must not equal zero.
    3537//
    3638// For f and g in R[x], R an integral domain, g != 0, there is a
    … …  
    5153psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
    5254{
    53     ASSERT( x.level() > 0, "cannot calculate pseudo remainder/quotient with respect to algebraic variables" );
     55    ASSERT( x.level() > 0, "illegal variable" );
    5456    ASSERT( g != 0, "division by zero" );
    5557
    … …  
    6668//{{{ docu
    6769//
    68 // psq() - calculate pseudo quotient of f and g with respect to x.
    69 //
    70 // x should be a polynomial variable.  See psr() for more
    71 // detailed information.
     70// psq() - calculate pseudo quotient of `f' and `g' with respect
     71//   to `x'.
     72//
     73// `x' should be a polynomial variable, `g' must not equal zero.
     74// See `psr()' for more detailed information.
    7275//
    7376//}}}
    … …  
    7578psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
    7679{
    77     ASSERT( x.level() > 0, "cannot calculate pseudo remainder/quotient with respect to algebraic variables" );
     80    ASSERT( x.level() > 0, "illegal variable" );
    7881    ASSERT( g != 0, "division by zero" );
    7982
    … …  
    9093//{{{ docu
    9194//
    92 // psqr() - calculate pseudo quotient and remainder of f and g with respect to x.
    93 //
    94 // x should be a polynomial variable.  See psr() for more
    95 // detailed information.
     95// psqr() - calculate pseudo quotient and remainder of `f' and
     96//   `g' with respect to `x'.
     97//
     98// `x' should be a polynomial variable, `g' must not equal zero.
     99// See `psr()' for more detailed information.
    96100//
    97101//}}}
    … …  
    99103psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable& x )
    100104{
    101     ASSERT( x.level() > 0, "cannot calculate pseudo remainder/quotient with respect to algebraic variables" );
     105    ASSERT( x.level() > 0, "illegal variable" );
    102106    ASSERT( g != 0, "division by zero" );
    103107
    … …  
    112116//}}}
    113117
    114 //{{{ static CanonicalForm cden ( const CanonicalForm & f )
    115 //{{{ docu
    116 //
    117 // cden() - recursively calculate multivariate common denominator
    118 //   of coefficients of f.
    119 //
    120 // Used by: common_den()
     118//{{{ static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
     119//{{{ docu
     120//
     121// internalBCommonDen() - recursively calculate multivariate
     122//   common denominator of coefficients of `f'.
     123//
     124// Used by: bCommonDen()
    121125//
    122126//}}}
    123127static CanonicalForm
    124 cden ( const CanonicalForm & f )
     128internalBCommonDen ( const CanonicalForm & f )
    125129{
    126130    if ( f.inBaseDomain() )
    127131        return f.den();
    128132    else {
    129         CFIterator i;
    130         CanonicalForm cd = 1;
    131         for ( i = f; i.hasTerms(); i++ )
    132             cd = lcm( cd, cden( i.coeff() ) );
    133         return cd;
    134     }
    135 }
    136 //}}}
    137 
    138 //{{{ CanonicalForm common_den ( const CanonicalForm & f )
    139 //{{{ docu
    140 //
    141 // common_den() - calculate multivariate common denominator of
    142 //   coefficients of f.
     133        CanonicalForm result = 1;
     134        for ( CFIterator i = f; i.hasTerms(); i++ )
     135            result = blcm( result, internalBCommonDen( i.coeff() ) );
     136        return result;
     137    }
     138}
     139//}}}
     140
     141//{{{ CanonicalForm bCommonDen ( const CanonicalForm & f )
     142//{{{ docu
     143//
     144// bCommonDen() - calculate multivariate common denominator of
     145//   coefficients of `f'.
    143146//
    144147// The common denominator is calculated with respect to all
    145 // coefficients of f which are in a base domain.  In other words,
    146 // common_den( f ) * f is guaranteed to have integer
    147 // coefficients only.
    148 //
    149 // Returns one for domains other than Q.
    150 //
    151 //}}}
    152 CanonicalForm
    153 common_den ( const CanonicalForm & f )
     148// coefficients of `f' which are in a base domain.  In other
     149// words, common_den( `f' ) * `f' is guaranteed to have integer
     150// coefficients only.  The common denominator of zero equals is
     151// one.
     152//
     153// Returns something non-trivial iff the current domain is Q.
     154//
     155//}}}
     156CanonicalForm
     157bCommonDen ( const CanonicalForm & f )
    154158{
    155159    if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) {
    156         // switch to Z so lcm() will work correctly
     160        // otherwise `bgcd()' returns one
    157161        Off( SW_RATIONAL );
    158         CanonicalForm cd = cden( f );
     162        CanonicalForm result = internalBCommonDen( f );
    159163        On( SW_RATIONAL );
    160         return cd;
    161     }
    162     else
    163         return 1;
     164        return result;
     165    } else
     166        return CanonicalForm( 1 );
    164167}
    165168//}}}
    … …  
    168171//{{{ docu
    169172//
    170 // divides() - check whether f divides g.
     173// divides() - check whether `f' divides `g'.
    171174//
    172175// Uses some extra checks to avoid polynomial division.
    … …  
    180183            CanonicalForm q, r;
    181184            bool ok = divremt( g, f, q, r );
    182             return ok && r == 0;
     185            return ok && r.isZero();
    183186        }
    184187        else
    … …  
    187190        CanonicalForm q, r;
    188191        bool ok = divremt( g, f, q, r );
    189         return ok && r == 0;
    190     }
    191 }
    192 //}}}
     192        return ok && r.isZero();
     193    }
     194}
     195//}}}
     196
     197//{{{ CanonicalForm maxNorm ( const CanonicalForm & f )
     198//{{{ docu
     199//
     200// maxNorm() - get maximum norm of `f'.
     201//
     202// That is, the base coefficient of `f' with the largest absolute
     203// value.
     204//
     205// Valid for arbitrary polynomials over arbitrary domains, but
     206// most useful for multivariate polynomials over Z.
     207//
     208//}}}
     209CanonicalForm
     210maxNorm ( const CanonicalForm & f )
     211{
     212    if ( f.inBaseDomain() )
     213        return abs( f );
     214    else {
     215        CanonicalForm result = 0;
     216        for ( CFIterator i = f; i.hasTerms(); i++ ) {
     217            CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
     218            if ( coeffMaxNorm > result )
     219                result = coeffMaxNorm;
     220        }
     221        return result;
     222    }
     223}
     224//}}}
     225
     226//{{{ CanonicalForm euclideanNorm ( const CanonicalForm & f )
     227//{{{ docu
     228//
     229// euclideanNorm() - get euclidean norm of `f'.
     230//
     231// That is, returns the largest integer smaller or equal
     232// norm(`f') = sqrt(sum( `f'[i]^2 )).  `f' should be an
     233// univariate polynomial over Z.
     234//
     235//}}}
     236CanonicalForm
     237euclideanNorm ( const CanonicalForm & f )
     238{
     239    ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
     240            "illegal polynomial" );
     241
     242    CanonicalForm result = 0;
     243    for ( CFIterator i = f; i.hasTerms(); i++ ) {
     244        CanonicalForm coeff = i.coeff();
     245        result += coeff*coeff;
     246    }
     247    return sqrt( result );
     248}
     249//}}}
Note: See TracChangeset for help on using the changeset viewer.