Changeset 086f3e in git


Ignore:
Timestamp:
Jun 12, 2014, 2:39:07 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
b52d27d2253640853931de85cd929e72b5979ec1
Parents:
cbb7532c858edb13f6b986e888868ff61d03394e
git-author:
Martin Lee <martinlee84@web.de>2014-06-12 14:39:07+02:00
git-committer:
Martin Lee <martinlee84@web.de>2014-06-17 17:12:29+02:00
Message:
chg: more old comments -> doxygen
Location:
factory
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • factory/cf_algorithm.cc

    rcbb753 r086f3e  
    11/* emacs edit mode for this file is -*- C++ -*- */
    22
    3 //{{{ docu
    4 //
    5 // cf_algorithm.cc - simple mathematical algorithms.
    6 //
    7 // Hierarchy: mathematical algorithms on canonical forms
    8 //
    9 // Developers note:
    10 // ----------------
    11 // A "mathematical" algorithm is an algorithm which calculates
    12 // some mathematical function in contrast to a "structural"
    13 // algorithm which gives structural information on polynomials.
    14 //
    15 // Compare these functions to the functions in `cf_ops.cc', which
    16 // are structural algorithms.
    17 //
    18 //}}}
     3/**
     4 *
     5 *
     6 * cf_algorithm.cc - simple mathematical algorithms.
     7 *
     8 * Hierarchy: mathematical algorithms on canonical forms
     9 *
     10 * Developers note:
     11 * ----------------
     12 * A "mathematical" algorithm is an algorithm which calculates
     13 * some mathematical function in contrast to a "structural"
     14 * algorithm which gives structural information on polynomials.
     15 *
     16 * Compare these functions to the functions in `cf_ops.cc', which
     17 * are structural algorithms.
     18 *
     19**/
    1920
    2021
     
    3536void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
    3637
    37 //{{{ CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
    38 //{{{ docu
    39 //
    40 // psr() - return pseudo remainder of `f' and `g' with respect
    41 //   to `x'.
    42 //
    43 // `g' must not equal zero.
    44 //
    45 // For f and g in R[x], R an arbitrary ring, g != 0, there is a
    46 // representation
    47 //
    48 //   LC(g)^s*f = g*q + r
    49 //
    50 // with r = 0 or deg(r) < deg(g) and s = 0 if f = 0 or
    51 // s = max( 0, deg(f)-deg(g)+1 ) otherwise.
    52 // r = psr(f, g) and q = psq(f, g) are called "pseudo remainder"
    53 // and "pseudo quotient", resp.  They are uniquely determined if
    54 // LC(g) is not a zero divisor in R.
    55 //
    56 // See H.-J. Reiffen/G. Scheja/U. Vetter - "Algebra", 2nd ed.,
    57 // par. 15, for a reference.
    58 //
    59 // Type info:
    60 // ----------
    61 // f, g: Current
    62 // x: Polynomial
    63 //
    64 // Polynomials over prime power domains are admissible if
    65 // lc(LC(`g',`x')) is not a zero divisor.  This is a slightly
    66 // stronger precondition than mathematically necessary since
    67 // pseudo remainder and quotient are well-defined if LC(`g',`x')
    68 // is not a zero divisor.
    69 //
    70 // For example, psr(y^2, (13*x+1)*y) is well-defined in
    71 // (Z/13^2[x])[y] since (13*x+1) is not a zero divisor.  But
    72 // calculating it with Factory would fail since 13 is a zero
    73 // divisor in Z/13^2.
    74 //
    75 // Due to this inconsistency with mathematical notion, we decided
    76 // not to declare type `CurrentPP' for `f' and `g'.
    77 //
    78 // Developers note:
    79 // ----------------
    80 // This is not an optimal implementation.  Better would have been
    81 // an implementation in `InternalPoly' avoiding the
    82 // exponentiation of the leading coefficient of `g'.  In contrast
    83 // to `psq()' and `psqr()' it definitely seems worth to implement
    84 // the pseudo remainder on the internal level.  Should be done
    85 // soon.
    86 //
    87 //}}}
     38/** CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
     39 *
     40 *
     41 * psr() - return pseudo remainder of `f' and `g' with respect
     42 *   to `x'.
     43 *
     44 * `g' must not equal zero.
     45 *
     46 * For f and g in R[x], R an arbitrary ring, g != 0, there is a
     47 * representation
     48 *
     49 *   LC(g)^s*f = g*q + r
     50 *
     51 * with r = 0 or deg(r) < deg(g) and s = 0 if f = 0 or
     52 * s = max( 0, deg(f)-deg(g)+1 ) otherwise.
     53 * r = psr(f, g) and q = psq(f, g) are called "pseudo remainder"
     54 * and "pseudo quotient", resp.  They are uniquely determined if
     55 * LC(g) is not a zero divisor in R.
     56 *
     57 * See H.-J. Reiffen/G. Scheja/U. Vetter - "Algebra", 2nd ed.,
     58 * par. 15, for a reference.
     59 *
     60 * Type info:
     61 * ----------
     62 * f, g: Current
     63 * x: Polynomial
     64 *
     65 * Polynomials over prime power domains are admissible if
     66 * lc(LC(`g',`x')) is not a zero divisor.  This is a slightly
     67 * stronger precondition than mathematically necessary since
     68 * pseudo remainder and quotient are well-defined if LC(`g',`x')
     69 * is not a zero divisor.
     70 *
     71 * For example, psr(y^2, (13*x+1)*y) is well-defined in
     72 * (Z/13^2[x])[y] since (13*x+1) is not a zero divisor.  But
     73 * calculating it with Factory would fail since 13 is a zero
     74 * divisor in Z/13^2.
     75 *
     76 * Due to this inconsistency with mathematical notion, we decided
     77 * not to declare type `CurrentPP' for `f' and `g'.
     78 *
     79 * Developers note:
     80 * ----------------
     81 * This is not an optimal implementation.  Better would have been
     82 * an implementation in `InternalPoly' avoiding the
     83 * exponentiation of the leading coefficient of `g'.  In contrast
     84 * to `psq()' and `psqr()' it definitely seems worth to implement
     85 * the pseudo remainder on the internal level.
     86 *
     87 * @sa psq(), psqr()
     88**/
    8889CanonicalForm
    8990#if 0
     
    144145}
    145146#endif
    146 //}}}
    147 
    148 //{{{ CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
    149 //{{{ docu
    150 //
    151 // psq() - return pseudo quotient of `f' and `g' with respect
    152 //   to `x'.
    153 //
    154 // `g' must not equal zero.
    155 //
    156 // See `psr()' for more detailed information.
    157 //
    158 // Type info:
    159 // ----------
    160 // f, g: Current
    161 // x: Polynomial
    162 //
    163 // Developers note:
    164 // ----------------
    165 // This is not an optimal implementation.  Better would have been
    166 // an implementation in `InternalPoly' avoiding the
    167 // exponentiation of the leading coefficient of `g'.  It seemed
    168 // not worth to do so.
    169 //
    170 //}}}
     147
     148/** CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
     149 *
     150 *
     151 * psq() - return pseudo quotient of `f' and `g' with respect
     152 *   to `x'.
     153 *
     154 * `g' must not equal zero.
     155 *
     156 * Type info:
     157 * ----------
     158 * f, g: Current
     159 * x: Polynomial
     160 *
     161 * Developers note:
     162 * ----------------
     163 * This is not an optimal implementation.  Better would have been
     164 * an implementation in `InternalPoly' avoiding the
     165 * exponentiation of the leading coefficient of `g'.  It seemed
     166 * not worth to do so.
     167 *
     168 * @sa psr(), psqr()
     169 *
     170**/
    171171CanonicalForm
    172172psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
     
    192192    }
    193193}
    194 //}}}
    195 
    196 //{{{ void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x )
    197 //{{{ docu
    198 //
    199 // psqr() - calculate pseudo quotient and remainder of `f' and
    200 //   `g' with respect to `x'.
    201 //
    202 // Returns the pseudo quotient of `f' and `g' in `q', the pseudo
    203 // remainder in `r'.  `g' must not equal zero.
    204 //
    205 // See `psr()' for more detailed information.
    206 //
    207 // Type info:
    208 // ----------
    209 // f, g: Current
    210 // q, r: Anything
    211 // x: Polynomial
    212 //
    213 // Developers note:
    214 // ----------------
    215 // This is not an optimal implementation.  Better would have been
    216 // an implementation in `InternalPoly' avoiding the
    217 // exponentiation of the leading coefficient of `g'.  It seemed
    218 // not worth to do so.
    219 //
    220 //}}}
     194
     195/** void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x )
     196 *
     197 *
     198 * psqr() - calculate pseudo quotient and remainder of `f' and
     199 *   `g' with respect to `x'.
     200 *
     201 * Returns the pseudo quotient of `f' and `g' in `q', the pseudo
     202 * remainder in `r'.  `g' must not equal zero.
     203 *
     204 * See `psr()' for more detailed information.
     205 *
     206 * Type info:
     207 * ----------
     208 * f, g: Current
     209 * q, r: Anything
     210 * x: Polynomial
     211 *
     212 * Developers note:
     213 * ----------------
     214 * This is not an optimal implementation.  Better would have been
     215 * an implementation in `InternalPoly' avoiding the
     216 * exponentiation of the leading coefficient of `g'.  It seemed
     217 * not worth to do so.
     218 *
     219 * @sa psr(), psq()
     220 *
     221**/
    221222void
    222223psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable& x )
     
    243244    }
    244245}
    245 //}}}
    246 
    247 //{{{ static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
    248 //{{{ docu
    249 //
    250 // internalBCommonDen() - recursively calculate multivariate
    251 //   common denominator of coefficients of `f'.
    252 //
    253 // Used by: bCommonDen()
    254 //
    255 // Type info:
    256 // ----------
    257 // f: Poly( Q )
    258 // Switches: isOff( SW_RATIONAL )
    259 //
    260 //}}}
     246
     247/** static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
     248 *
     249 *
     250 * internalBCommonDen() - recursively calculate multivariate
     251 *   common denominator of coefficients of `f'.
     252 *
     253 * Used by: bCommonDen()
     254 *
     255 * Type info:
     256 * ----------
     257 * f: Poly( Q )
     258 * Switches: isOff( SW_RATIONAL )
     259 *
     260**/
    261261static CanonicalForm
    262262internalBCommonDen ( const CanonicalForm & f )
     
    271271    }
    272272}
    273 //}}}
    274 
    275 //{{{ CanonicalForm bCommonDen ( const CanonicalForm & f )
    276 //{{{ docu
    277 //
    278 // bCommonDen() - calculate multivariate common denominator of
    279 //   coefficients of `f'.
    280 //
    281 // The common denominator is calculated with respect to all
    282 // coefficients of `f' which are in a base domain.  In other
    283 // words, common_den( `f' ) * `f' is guaranteed to have integer
    284 // coefficients only.  The common denominator of zero is one.
    285 //
    286 // Returns something non-trivial iff the current domain is Q.
    287 //
    288 // Type info:
    289 // ----------
    290 // f: CurrentPP
    291 //
    292 //}}}
     273
     274/** CanonicalForm bCommonDen ( const CanonicalForm & f )
     275 *
     276 *
     277 * bCommonDen() - calculate multivariate common denominator of
     278 *   coefficients of `f'.
     279 *
     280 * The common denominator is calculated with respect to all
     281 * coefficients of `f' which are in a base domain.  In other
     282 * words, common_den( `f' ) * `f' is guaranteed to have integer
     283 * coefficients only.  The common denominator of zero is one.
     284 *
     285 * Returns something non-trivial iff the current domain is Q.
     286 *
     287 * Type info:
     288 * ----------
     289 * f: CurrentPP
     290 *
     291**/
    293292CanonicalForm
    294293bCommonDen ( const CanonicalForm & f )
     
    303302        return CanonicalForm( 1 );
    304303}
    305 //}}}
    306 
    307 //{{{ bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
    308 //{{{ docu
    309 //
    310 // fdivides() - check whether `f' divides `g'.
    311 //
    312 // Returns true iff `f' divides `g'.  Uses some extra heuristic
    313 // to avoid polynomial division.  Without the heuristic, the test
    314 // essentialy looks like `divremt(g, f, q, r) && r.isZero()'.
    315 //
    316 // Type info:
    317 // ----------
    318 // f, g: Current
    319 //
    320 // Elements from prime power domains (or polynomials over such
    321 // domains) are admissible if `f' (or lc(`f'), resp.) is not a
    322 // zero divisor.  This is a slightly stronger precondition than
    323 // mathematically necessary since divisibility is a well-defined
    324 // notion in arbitrary rings.  Hence, we decided not to declare
    325 // the weaker type `CurrentPP'.
    326 //
    327 // Developers note:
    328 // ----------------
    329 // One may consider the the test `fdivides( f.LC(), g.LC() )' in
    330 // the main `if'-test superfluous since `divremt()' in the
    331 // `if'-body repeats the test.  However, `divremt()' does not use
    332 // any heuristic to do so.
    333 //
    334 // It seems not reasonable to call `fdivides()' from `divremt()'
    335 // to check divisibility of leading coefficients.  `fdivides()' is
    336 // on a relatively high level compared to `divremt()'.
    337 //
    338 //}}}
     304
     305/** bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
     306 *
     307 *
     308 * fdivides() - check whether `f' divides `g'.
     309 *
     310 * Returns true iff `f' divides `g'.  Uses some extra heuristic
     311 * to avoid polynomial division.  Without the heuristic, the test
     312 * essentialy looks like `divremt(g, f, q, r) && r.isZero()'.
     313 *
     314 * Type info:
     315 * ----------
     316 * f, g: Current
     317 *
     318 * Elements from prime power domains (or polynomials over such
     319 * domains) are admissible if `f' (or lc(`f'), resp.) is not a
     320 * zero divisor.  This is a slightly stronger precondition than
     321 * mathematically necessary since divisibility is a well-defined
     322 * notion in arbitrary rings.  Hence, we decided not to declare
     323 * the weaker type `CurrentPP'.
     324 *
     325 * Developers note:
     326 * ----------------
     327 * One may consider the the test `fdivides( f.LC(), g.LC() )' in
     328 * the main `if'-test superfluous since `divremt()' in the
     329 * `if'-body repeats the test.  However, `divremt()' does not use
     330 * any heuristic to do so.
     331 *
     332 * It seems not reasonable to call `fdivides()' from `divremt()'
     333 * to check divisibility of leading coefficients.  `fdivides()' is
     334 * on a relatively high level compared to `divremt()'.
     335 *
     336**/
    339337bool
    340338fdivides ( const CanonicalForm & f, const CanonicalForm & g )
     
    385383    }
    386384}
    387 //}}}
    388385
    389386/// same as fdivides if true returns quotient quot of g by f otherwise quot == 0
     
    518515}
    519516
    520 //{{{ CanonicalForm maxNorm ( const CanonicalForm & f )
    521 //{{{ docu
    522 //
    523 // maxNorm() - return maximum norm of `f'.
    524 //
    525 // That is, the base coefficient of `f' with the largest absolute
    526 // value.
    527 //
    528 // Valid for arbitrary polynomials over arbitrary domains, but
    529 // most useful for multivariate polynomials over Z.
    530 //
    531 // Type info:
    532 // ----------
    533 // f: CurrentPP
    534 //
    535 //}}}
     517/** CanonicalForm maxNorm ( const CanonicalForm & f )
     518 *
     519 *
     520 * maxNorm() - return maximum norm of `f'.
     521 *
     522 * That is, the base coefficient of `f' with the largest absolute
     523 * value.
     524 *
     525 * Valid for arbitrary polynomials over arbitrary domains, but
     526 * most useful for multivariate polynomials over Z.
     527 *
     528 * Type info:
     529 * ----------
     530 * f: CurrentPP
     531 *
     532**/
    536533CanonicalForm
    537534maxNorm ( const CanonicalForm & f )
     
    549546    }
    550547}
    551 //}}}
    552 
    553 //{{{ CanonicalForm euclideanNorm ( const CanonicalForm & f )
    554 //{{{ docu
    555 //
    556 // euclideanNorm() - return Euclidean norm of `f'.
    557 //
    558 // Returns the largest integer smaller or equal norm(`f') =
    559 // sqrt(sum( `f'[i]^2 )).
    560 //
    561 // Type info:
    562 // ----------
    563 // f: UVPoly( Z )
    564 //
    565 //}}}
     548
     549/** CanonicalForm euclideanNorm ( const CanonicalForm & f )
     550 *
     551 *
     552 * euclideanNorm() - return Euclidean norm of `f'.
     553 *
     554 * Returns the largest integer smaller or equal norm(`f') =
     555 * sqrt(sum( `f'[i]^2 )).
     556 *
     557 * Type info:
     558 * ----------
     559 * f: UVPoly( Z )
     560 *
     561**/
    566562CanonicalForm
    567563euclideanNorm ( const CanonicalForm & f )
     
    577573    return sqrt( result );
    578574}
    579 //}}}
  • factory/cf_algorithm.h

    rcbb753 r086f3e  
    11/* emacs edit mode for this file is -*- C++ -*- */
     2
     3/**
     4 * @file cf_algorithm.h
     5 * declarations of higher level algorithms.
     6 *
     7 * Header file corresponds to: cf_algorithm.cc, cf_chinese.cc,
     8 *   cf_factor.cc, cf_linsys.cc, cf_resultant.cc
     9 *
     10 * Hierarchy: mathematical algorithms on canonical forms
     11 *
     12 * Developers note:
     13 * ----------------
     14 * This header file collects declarations of most of the
     15 * functions in Factory which implement higher level algorithms
     16 * on canonical forms (factorization, gcd, etc.) and declarations
     17 * of some low level mathematical functions, too (absolute value,
     18 * euclidean norm, etc.).
     19 *
     20**/
    221
    322#ifndef INCL_CF_ALGORITHM_H
    423#define INCL_CF_ALGORITHM_H
    5 
    6 //{{{ docu
    7 //
    8 // cf_algorithm.h - declarations of higher level algorithms.
    9 //
    10 // Header file corresponds to: cf_algorithms.cc, cf_chinese.cc,
    11 //   cf_factor.cc, cf_linsys.cc, cf_resultant.cc
    12 //
    13 // Hierarchy: mathematical algorithms on canonical forms
    14 //
    15 // Developers note:
    16 // ----------------
    17 // This header file collects declarations of most of the
    18 // functions in Factory which implement higher level algorithms
    19 // on canonical forms (factorization, gcd, etc.) and declarations
    20 // of some low level mathematical functions, too (absolute value,
    21 // euclidean norm, etc.).
    22 //
    23 //}}}
    2424
    2525// #include "config.h"
     
    9393//}}}
    9494
    95 //{{{ inline CanonicalForm abs ( const CanonicalForm & f )
    96 //{{{ docu
    97 //
    98 // abs() - return absolute value of `f'.
    99 //
    100 // The absolute value is defined in terms of the function
    101 // `sign()'.  If it reports negative sign for `f' than -`f' is
    102 // returned, otherwise `f'.
    103 //
    104 // This behaviour is most useful for integers and rationals.  But
    105 // it may be used to sign-normalize the leading coefficient of
    106 // arbitrary polynomials, too.
    107 //
    108 // Type info:
    109 // ----------
    110 // f: CurrentPP
    111 //
    112 //}}}
     95/** inline CanonicalForm abs ( const CanonicalForm & f )
     96 *
     97 * abs() - return absolute value of `f'.
     98 *
     99 * The absolute value is defined in terms of the function
     100 * `sign()'.  If it reports negative sign for `f' than -`f' is
     101 * returned, otherwise `f'.
     102 *
     103 * This behaviour is most useful for integers and rationals.  But
     104 * it may be used to sign-normalize the leading coefficient of
     105 * arbitrary polynomials, too.
     106 *
     107 * Type info:
     108 * ----------
     109 * f: CurrentPP
     110 *
     111**/
    113112inline CanonicalForm
    114113abs ( const CanonicalForm & f )
  • factory/cf_chinese.cc

    rcbb753 r086f3e  
    11/* emacs edit mode for this file is -*- C++ -*- */
    22
    3 //{{{ docu
    4 //
    5 // cf_chinese.cc - algorithms for chinese remaindering.
    6 //
    7 // Used by: cf_gcd.cc, cf_linsys.cc
    8 //
    9 // Header file: cf_algorithm.h
    10 //
    11 //}}}
     3/**
     4 * @file cf_chinese.cc
     5 * algorithms for chinese remaindering.
     6 *
     7 * Used by: cf_gcd.cc, cf_linsys.cc
     8 *
     9 * Header file: cf_algorithm.h
     10 *
     11**/
    1212
    1313
     
    2626
    2727
    28 //{{{ void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
    29 //{{{ docu
    30 //
    31 // chineseRemainder - integer chinese remaindering.
    32 //
    33 // Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2)
    34 // and qnew = q1*q2.  q1 and q2 should be positive integers,
    35 // pairwise prime, x1 and x2 should be polynomials with integer
    36 // coefficients.  If x1 and x2 are polynomials with positive
    37 // coefficients, the result is guaranteed to have positive
    38 // coefficients, too.
    39 //
    40 // Note: This algorithm is optimized for the case q1>>q2.
    41 //
    42 // This is a standard algorithm.  See, for example,
    43 // Geddes/Czapor/Labahn - 'Algorithms for Computer Algebra',
    44 // par. 5.6 and 5.8, or the article of M. Lauer - 'Computing by
    45 // Homomorphic Images' in B. Buchberger - 'Computer Algebra -
    46 // Symbolic and Algebraic Computation'.
    47 //
    48 // Note: Be sure you are calculating in Z, and not in Q!
    49 //
    50 //}}}
     28/** void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
     29 *
     30 * chineseRemainder - integer chinese remaindering.
     31 *
     32 * Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2)
     33 * and qnew = q1*q2.  q1 and q2 should be positive integers,
     34 * pairwise prime, x1 and x2 should be polynomials with integer
     35 * coefficients.  If x1 and x2 are polynomials with positive
     36 * coefficients, the result is guaranteed to have positive
     37 * coefficients, too.
     38 *
     39 * Note: This algorithm is optimized for the case q1>>q2.
     40 *
     41 * This is a standard algorithm.  See, for example,
     42 * Geddes/Czapor/Labahn - 'Algorithms for Computer Algebra',
     43 * par. 5.6 and 5.8, or the article of M. Lauer - 'Computing by
     44 * Homomorphic Images' in B. Buchberger - 'Computer Algebra -
     45 * Symbolic and Algebraic Computation'.
     46 *
     47 * Note: Be sure you are calculating in Z, and not in Q!
     48 *
     49**/
    5150void
    5251chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
     
    9897//}}}
    9998
    100 //{{{ void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
    101 //{{{ docu
    102 //
    103 // chineseRemainder - integer chinese remaindering.
    104 //
    105 // Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the
    106 // product of all q[i].  q[i] should be positive integers,
    107 // pairwise prime.  x[i] should be polynomials with integer
    108 // coefficients.  If all coefficients of all x[i] are positive
    109 // integers, the result is guaranteed to have positive
    110 // coefficients, too.
    111 //
    112 // This is a standard algorithm, too, except for the fact that we
    113 // use a divide-and-conquer method instead of a linear approach
    114 // to calculate the remainder.
    115 //
    116 // Note: Be sure you are calculating in Z, and not in Q!
    117 //
    118 //}}}
     99/** void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
     100 *
     101 * chineseRemainder - integer chinese remaindering.
     102 *
     103 * Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the
     104 * product of all q[i].  q[i] should be positive integers,
     105 * pairwise prime.  x[i] should be polynomials with integer
     106 * coefficients.  If all coefficients of all x[i] are positive
     107 * integers, the result is guaranteed to have positive
     108 * coefficients, too.
     109 *
     110 * This is a standard algorithm, too, except for the fact that we
     111 * use a divide-and-conquer method instead of a linear approach
     112 * to calculate the remainder.
     113 *
     114 * Note: Be sure you are calculating in Z, and not in Q!
     115 *
     116**/
    119117void
    120118chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
     
    159157    DEBDECLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
    160158}
    161 //}}}
    162159
    163160#ifndef HAVE_NTL
     
    193190#endif
    194191
     192/**
     193 * Farey rational reconstruction. If NTL is available it uses the fast algorithm
     194 * from NTL, i.e. Encarnacion, Collins.
     195**/
    195196CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q )
    196197{
  • factory/facFqFactorizeUtil.h

    rcbb753 r086f3e  
    121121                           );
    122122
    123 /// check if @F consists of more than just the leading coeff wrt. Variable (1)
     123/// check if @a F consists of more than just the leading coeff wrt. Variable (1)
    124124///
    125125/// @return as described above
     
    131131                               );
    132132
    133 /// like getVars but each variable x occuring in @F is raised to x^degree (F,x)
     133/// like getVars but each variable x occuring in @a F is raised to x^degree (F,x)
    134134CanonicalForm myGetVars (const CanonicalForm& F ///< [in] a polynomial
    135135                        );
Note: See TracChangeset for help on using the changeset viewer.