My Project
|
algorithms for chinese remaindering and rational reconstruction More...
#include "config.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
#include "cf_assert.h"
#include "debug.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_util.h"
Go to the source code of this file.
algorithms for chinese remaindering and rational reconstruction
Used by: cf_gcd.cc, cf_linsys.cc
Header file: cf_algorithm.h
Definition in file cf_chinese.cc.
|
inlinestatic |
Definition at line 276 of file cf_chinese.cc.
void chineseRemainder | ( | const CanonicalForm & | x1, |
const CanonicalForm & | q1, | ||
const CanonicalForm & | x2, | ||
const CanonicalForm & | q2, | ||
CanonicalForm & | xnew, | ||
CanonicalForm & | qnew | ||
) |
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
chineseRemainder - integer chinese remaindering.
Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2) and qnew = q1*q2. q1 and q2 should be positive integers, pairwise prime, x1 and x2 should be polynomials with integer coefficients. If x1 and x2 are polynomials with positive coefficients, the result is guaranteed to have positive coefficients, too.
Note: This algorithm is optimized for the case q1>>q2.
This is a standard algorithm. See, for example, Geddes/Czapor/Labahn - 'Algorithms for Computer Algebra', par. 5.6 and 5.8, or the article of M. Lauer - 'Computing by Homomorphic Images' in B. Buchberger - 'Computer Algebra - Symbolic and Algebraic Computation'.
Note: Be sure you are calculating in Z, and not in Q!
Definition at line 57 of file cf_chinese.cc.
void chineseRemainder | ( | const CFArray & | x, |
const CFArray & | q, | ||
CanonicalForm & | xnew, | ||
CanonicalForm & | qnew | ||
) |
void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
chineseRemainder - integer chinese remaindering.
Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the product of all q[i]. q[i] should be positive integers, pairwise prime. x[i] should be polynomials with integer coefficients. If all coefficients of all x[i] are positive integers, the result is guaranteed to have positive coefficients, too.
This is a standard algorithm, too, except for the fact that we use a divide-and-conquer method instead of a linear approach to calculate the remainder.
Note: Be sure you are calculating in Z, and not in Q!
Definition at line 124 of file cf_chinese.cc.
void chineseRemainderCached | ( | const CanonicalForm & | a, |
const CanonicalForm & | q1, | ||
const CanonicalForm & | b, | ||
const CanonicalForm & | q2, | ||
CanonicalForm & | xnew, | ||
CanonicalForm & | qnew, | ||
CFArray & | inv | ||
) |
Definition at line 308 of file cf_chinese.cc.
void chineseRemainderCached | ( | const CFArray & | a, |
const CFArray & | n, | ||
CanonicalForm & | xnew, | ||
CanonicalForm & | prod, | ||
CFArray & | inv | ||
) |
Definition at line 290 of file cf_chinese.cc.
CanonicalForm Farey | ( | const CanonicalForm & | f, |
const CanonicalForm & | q | ||
) |
Farey rational reconstruction.
If NTL is available it uses the fast algorithm from NTL, i.e. Encarnacion, Collins.
Definition at line 202 of file cf_chinese.cc.
void out_cf | ( | const char * | s1, |
const CanonicalForm & | f, | ||
const char * | s2 | ||
) |
cf_algorithm.cc - simple mathematical algorithms.
Hierarchy: mathematical algorithms on canonical forms
A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.
Compare these functions to the functions in ‘cf_ops.cc’, which are structural algorithms.
Definition at line 99 of file cf_factor.cc.