Loading...
Searching...
No Matches
int_intdiv.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
/**
*
* @file int_intdiv.cc
*
* 'InternalInteger' division algorithms.
*
**/
#include "config.h"
#include "canonicalform.h"
#include "imm.h"
#include "int_cf.h"
#include "int_int.h"
#include "int_rat.h"
#include "factory/cf_gmp.h"
#include "gmpext.h"
#include "templates/ftmpl_functions.h"
/**
* @sa CanonicalForm::operator /(), InternalInteger::dividecoeff()
**/
InternalCF *
InternalInteger::dividesame ( InternalCF * c )
{
ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
"type error: InternalInteger expected" );
if ( c == this ) {
if ( deleteObject() ) delete this;
return int2imm( 1 );
}
if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
mpz_t n, d;
mpz_init_set( n, thempi );
mpz_init_set( d, MPI( c ) );
if ( deleteObject() ) delete this;
InternalRational * result = new InternalRational( n, d );
return result->normalize_myself();
}
if ( getRefCount() > 1 ) {
decRefCount();
mpz_t mpiResult;
mpz_init( mpiResult );
if ( mpz_sgn( MPI( c ) ) > 0 )
mpz_fdiv_q( mpiResult, thempi, MPI( c ) );
else
mpz_cdiv_q( mpiResult, thempi, MPI( c ) );
return normalizeMPI( mpiResult );
} else {
if ( mpz_sgn( MPI( c ) ) > 0 )
mpz_fdiv_q( thempi, thempi, MPI( c ) );
else
mpz_cdiv_q( thempi, thempi, MPI( c ) );
return normalizeMyself();
}
}
/**
* @sa CanonicalForm::operator /(), InternalInteger::dividesame()
**/
InternalCF *
InternalInteger::dividecoeff ( InternalCF * c, bool invert )
{
ASSERT( ::is_imm( c ) == INTMARK,
"type error: immediate integer expected" );
ASSERT( invert || imm2int( c ) != 0,
"math error: divide by zero" );
long intC = imm2int( c );
if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
mpz_t n, d;
if ( invert ) {
mpz_init_set_si( n, intC );
mpz_init_set( d, thempi );
} else {
mpz_init_set( n, thempi );
mpz_init_set_si( d, intC );
}
if ( deleteObject() ) delete this;
InternalRational * result = new InternalRational( n, d );
return result->normalize_myself();
}
if ( invert ) {
int mpiSign = mpz_sgn( thempi );
if ( deleteObject() ) delete this;
if ( intC >= 0 )
return int2imm( 0 );
else
return int2imm( -mpiSign );
} else if ( getRefCount() > 1 ) {
decRefCount();
mpz_t mpiResult;
mpz_init( mpiResult );
if ( intC > 0 )
mpz_fdiv_q_ui( mpiResult, thempi, intC );
else {
mpz_fdiv_q_ui( mpiResult, thempi, -intC );
mpz_neg( mpiResult, mpiResult );
}
return normalizeMPI( mpiResult );
} else {
if ( intC > 0 )
mpz_fdiv_q_ui( thempi, thempi, intC );
else {
mpz_fdiv_q_ui( thempi, thempi, -intC );
mpz_neg( thempi, thempi );
}
return normalizeMyself();
}
}
/**
* @sa CanonicalForm::div(), InternalInteger::divcoeff()
**/
InternalCF *
InternalInteger::divsame ( InternalCF * c )
{
ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
"type error: InternalInteger expected" );
if ( c == this ) {
if ( deleteObject() ) delete this;
return int2imm( 1 );
}
if ( getRefCount() > 1 ) {
deleteObject();
mpz_t mpiResult;
mpz_init( mpiResult );
mpz_divexact( mpiResult, thempi, MPI( c ) );
return normalizeMPI( mpiResult );
} else {
mpz_divexact( thempi, thempi, MPI( c ) );
return normalizeMyself();
}
}
/**
* @sa CanonicalForm::div(), InternalInteger::divsame()
**/
InternalCF *
InternalInteger::divcoeff ( InternalCF * c, bool invert )
{
ASSERT( ::is_imm( c ) == INTMARK,
"type error: immediate integer expected" );
ASSERT( invert || imm2int( c ) != 0,
"math error: divide by zero" );
ASSERT( ! invert || imm2int( c ) == 0,
"math error: c does not divide CO" );
if ( invert ) {
if ( deleteObject() ) delete this;
// this may happen iff `c' == 0
return int2imm( 0 );
} else if ( getRefCount() > 1 ) {
deleteObject();
mpz_t mpiC;
mpz_t mpiResult;
mpz_init_set_si( mpiC, imm2int( c ) );
mpz_init( mpiResult );
mpz_divexact( mpiResult, thempi, mpiC );
mpz_clear( mpiC );
return normalizeMPI( mpiResult );
} else {
mpz_t mpiC;
mpz_init_set_si( mpiC, imm2int( c ) );
mpz_divexact( thempi, thempi, mpiC );
mpz_clear( mpiC );
return normalizeMyself();
}
}
/**
* @sa CanonicalForm::operator %(), InternalInteger::modulocoeff()
**/
InternalCF *
InternalInteger::modulosame ( InternalCF * c )
{
ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
"type error: InternalInteger expected" );
if ( (c == this) || cf_glob_switches.isOn( SW_RATIONAL ) ) {
if ( deleteObject() ) delete this;
return int2imm( 0 );
}
if ( getRefCount() > 1 ) {
decRefCount();
mpz_t mpiResult;
mpz_init( mpiResult );
mpz_mod( mpiResult, thempi, MPI( c ) );
return uiNormalizeMPI( mpiResult );
} else {
mpz_mod( thempi, thempi, MPI( c ) );
return uiNormalizeMyself();
}
}
/**
* @sa CanonicalForm::operator %(), InternalInteger::modulosame()
**/
InternalCF *
InternalInteger::modulocoeff ( InternalCF * c, bool invert )
{
ASSERT( ::is_imm( c ) == INTMARK,
"type error: immediate integer expected" );
ASSERT( invert || imm2int( c ) != 0,
"math error: divide by zero" );
if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
if ( deleteObject() ) delete this;
return int2imm( 0 );
}
long intC = imm2int( c );
if ( invert ) {
if ( intC >= 0 ) {
if ( deleteObject() ) delete this;
return c;
} else {
// no checks for refCount == 1 are done. It is not worth ...
mpz_t mpiResult;
mpz_init_set( mpiResult, thempi );
mpz_abs( mpiResult, mpiResult );
mpz_sub_ui( mpiResult, mpiResult, -intC );
if ( deleteObject() ) delete this;
return uiNormalizeMPI( mpiResult );
}
} else {
mpz_t dummy;
mpz_init( dummy );
InternalCF * result = int2imm( mpz_mod_ui( dummy, thempi, tabs( intC ) ) );
mpz_clear( dummy );
if ( deleteObject() ) delete this;
return result;
}
}
/**
* @sa see CanonicalForm::mod(), InternalInteger::modcoeff()
**/
InternalCF *
InternalInteger::modsame ( InternalCF * c )
{
return modulosame( c );
}
/**
* @sa see CanonicalForm::mod(), InternalInteger::modsame()
**/
InternalCF *
InternalInteger::modcoeff ( InternalCF * c, bool invert )
{
return modulocoeff( c, invert );
}
/**
* @sa CanonicalForm::divrem(), InternalInteger::divremcoeff()
**/
void
InternalInteger::divremsame ( InternalCF * c, InternalCF * & quot, InternalCF * & rem )
{
ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
"type error: InternalInteger expected" );
if ( c == this ) {
quot = int2imm( 1 );
rem = int2imm( 0 );
return;
}
if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
mpz_t n, d;
mpz_init_set( n, thempi );
mpz_init_set( d, MPI( c ) );
InternalRational * result = new InternalRational( n, d );
quot = result->normalize_myself();
rem = int2imm( 0 );
return;
}
mpz_t q;
mpz_t r;
mpz_init( q ); mpz_init( r );
if ( mpz_sgn( MPI( c ) ) > 0 )
mpz_fdiv_qr( q, r, thempi, MPI( c ) );
else
mpz_cdiv_qr( q, r, thempi, MPI( c ) );
quot = normalizeMPI( q );
rem = uiNormalizeMPI( r );
}
/**
* @sa CanonicalForm::divrem(), InternalInteger::divremsame()
**/
void
InternalInteger::divremcoeff ( InternalCF * c, InternalCF * & quot, InternalCF * & rem, bool invert )
{
ASSERT( ::is_imm( c ) == INTMARK,
"type error: immediate integer expected" );
ASSERT( invert || imm2int( c ) != 0,
"math error: divide by zero" );
long intC = imm2int( c );
if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
mpz_t n, d;
if ( invert ) {
mpz_init_set_si( n, intC );
mpz_init_set( d, thempi );
} else {
mpz_init_set( n, thempi );
mpz_init_set_si( d, intC );
}
InternalRational * result = new InternalRational( n, d );
quot = result->normalize_myself();
rem = int2imm( 0 );
return;
}
if ( invert ) {
if ( intC >= 0 ) {
rem = c;
quot = int2imm( 0 );
} else {
mpz_t mpiResult;
mpz_init_set( mpiResult, thempi );
mpz_abs( mpiResult, mpiResult );
mpz_sub_ui( mpiResult, mpiResult, -intC );
rem = uiNormalizeMPI( mpiResult );
quot = int2imm( -mpz_sgn( thempi ) );
}
} else {
mpz_t q;
mpz_t dummy;
mpz_init( q ); mpz_init( dummy );
if ( intC > 0 ) {
rem = int2imm( mpz_fdiv_qr_ui( q, dummy, thempi, intC ) );
quot = normalizeMPI( q );
} else {
rem = int2imm( mpz_fdiv_qr_ui( q, dummy, thempi, -intC ) );
mpz_neg( q, q );
quot = normalizeMPI( q );
}
mpz_clear( dummy );
}
}
/**
* @sa CanonicalForm::divremt(), InternalInteger::divremcoefft()
**/
bool
InternalInteger::divremsamet ( InternalCF * c, InternalCF * & quot, InternalCF * & rem )
{
divremsame( c, quot, rem );
return true;
}
/**
* @sa CanonicalForm::divremt(), InternalInteger::divremsamet()
**/
bool
InternalInteger::divremcoefft ( InternalCF * c, InternalCF * & quot, InternalCF * & rem, bool invert )
{
divremcoeff( c, quot, rem, invert );
return true;
}
canonicalform.h
Header for factory's main class CanonicalForm.
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
IntegerDomain
#define IntegerDomain
Definition cf_defs.h:21
cf_gmp.h
cf_glob_switches
INST_VAR CFSwitches cf_glob_switches
Definition cf_switches.cc:54
tabs
int tabs
Definition checklibs.c:11
InternalCF
virtual class for internal CanonicalForm's
Definition int_cf.h:47
InternalCF::InternalCF
InternalCF()
Definition int_cf.h:55
InternalCF::getRefCount
int getRefCount()
Definition int_cf.h:51
InternalCF::levelcoeff
virtual int levelcoeff() const
Definition int_cf.h:68
InternalCF::decRefCount
int decRefCount()
Definition int_cf.h:53
InternalCF::invert
virtual InternalCF * invert()
Definition int_cf.cc:172
InternalCF::deleteObject
int deleteObject()
Definition int_cf.h:61
InternalInteger::dividecoeff
InternalCF * dividecoeff(InternalCF *, bool)
Definition int_intdiv.cc:69
InternalInteger::normalizeMyself
InternalCF * normalizeMyself()
normalizeMyself(), uiNormalizeMyself() - normalize CO.
Definition int_int.h:172
InternalInteger::modsame
InternalCF * modsame(InternalCF *)
Definition int_intdiv.cc:253
InternalInteger::thempi
mpz_t thempi
Definition int_int.h:58
InternalInteger::divremcoeff
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition int_intdiv.cc:308
InternalInteger::InternalRational
friend class InternalRational
Definition int_int.h:149
InternalInteger::modcoeff
InternalCF * modcoeff(InternalCF *, bool)
Definition int_intdiv.cc:262
InternalInteger::modulocoeff
InternalCF * modulocoeff(InternalCF *, bool)
Definition int_intdiv.cc:212
InternalInteger::modulosame
InternalCF * modulosame(InternalCF *)
Definition int_intdiv.cc:186
InternalInteger::divcoeff
InternalCF * divcoeff(InternalCF *, bool)
Definition int_intdiv.cc:151
InternalInteger::divremsame
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
Definition int_intdiv.cc:271
InternalInteger::normalizeMPI
static InternalCF * normalizeMPI(mpz_ptr)
uiNormalizeMyself()' is the same as normalizeMyself()' except that CO is expected to be non-negative.
Definition int_int.h:216
InternalInteger::divremsamet
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
Definition int_intdiv.cc:364
InternalInteger::is_imm
bool is_imm() const
Definition int_int.cc:41
InternalInteger::dividesame
InternalCF * dividesame(InternalCF *)
Definition int_intdiv.cc:28
InternalInteger::divsame
InternalCF * divsame(InternalCF *)
Definition int_intdiv.cc:125
InternalInteger::MPI
static mpz_ptr MPI(const InternalCF *const c)
uiNormalizeMPI()' is the same as normalizeMPI()' except that aMpi' is expected to be non-begative.
Definition int_int.h:252
InternalInteger::uiNormalizeMPI
static InternalCF * uiNormalizeMPI(mpz_ptr)
InternalInteger::uiNormalizeMyself
InternalCF * uiNormalizeMyself()
InternalInteger::divremcoefft
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition int_intdiv.cc:374
result
return result
Definition facAbsBiFact.cc:76
ftmpl_functions.h
some useful template functions.
gmpext.h
utility functions for gmp
imm.h
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
imm2int
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
INTMARK
const long INTMARK
Definition imm.h:37
int2imm
static InternalCF * int2imm(long i)
Definition imm.h:75
int_cf.h
Factory's internal CanonicalForm's.
int_int.h
Factory's internal integers.
int_rat.h
Factory's internal rationals.
rem
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition minpoly.cc:572