PIPS
Functions
normalize.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
+ Include dependency graph for normalize.c:

Go to the source code of this file.

Functions

bool contrainte_normalize (Pcontrainte c, bool is_egalite)
 package contrainte - NORMALISATION D'UN CONTRAINTE More...
 
bool egalite_normalize (Pcontrainte eg)
 bool egalite_normalize(Pcontrainte eg): reduction d'une equation diophantienne par le pgcd de ses coefficients; l'equation est infaisable si le terme constant n'est pas divisible par ce pgcd More...
 
bool inegalite_normalize (Pcontrainte ineg)
 bool inegalite_normalize(Pcontrainte ineg): normalisation d'une inegalite a variables entieres; voir contrainte_normalize; retourne presque toujours true car une inegalite n'ayant qu'un terme constant est toujours faisable a moins qu'il ne reste qu'un terme constant strictement positif. More...
 

Function Documentation

◆ contrainte_normalize()

bool contrainte_normalize ( Pcontrainte  c,
bool  is_egalite 
)

package contrainte - NORMALISATION D'UN CONTRAINTE

normalize.c

INTLIBRARY bool contrainte_normalize(Pcontrainte c, bool is_egalite): reduction par le pgcd de ses coefficients d'une egalite (is_egalite==true) ou d'une inegalite (is_egalite==false)

Dans le cas des egalites, la faisabilite est testee et retournee

Modifications:

  • double changement du signe du terme constant pour le traitement des inegalites (Francois Irigoin, 30 octobre 1991)
  • ajout d'un test pour les egalites du type 0 == k et les inegalites 0 <= -k quand k est une constante numerique entiere strictement positive (Francois Irigoin, 15 novembre 1995)

is_c_norm: si is_egalite=true, equation faisable

pgcd des termes non constant de c

modulo(abs(b0),a)

si le coefficient du terme constant est inferieur a ABS(a), on va obtenir un couple (TCST,coeff) avec un coefficient qui vaut 0, ceci est contraire a nos conventions

mise a jour du resultat de la division C if ( b0 < 0 && nb0 > 0) vect_add_elem(&(c->vecteur),0,-1); On n'en a plus besoin parce que vect_div utilise la division a reste toujours positif dont on a besoin

is_inegalite

Parameters
is_egalites_egalite

Definition at line 56 of file normalize.c.

59 {
60  /* is_c_norm: si is_egalite=true, equation faisable */
61  bool is_c_norm = true;
62  /* pgcd des termes non constant de c */
63  Value a;
64  /* modulo(abs(b0),a) */
65  Value nb0 = VALUE_ZERO;
66 
67  if(c!=NULL && (c->vecteur != NULL))
68  {
69  a = vect_pgcd_except(c->vecteur,TCST);
70  if (value_notzero_p(a)) {
71  Pvecteur v;
72 
73  nb0 = value_abs(vect_coeff(TCST,c->vecteur));
74  nb0 = value_mod(nb0,a);
75 
76  if (is_egalite) {
77  if (value_zero_p(nb0)) {
78  (void) vect_div(c->vecteur,value_abs(a));
79 
80  /* si le coefficient du terme constant est inferieur
81  * a ABS(a), on va obtenir un couple (TCST,coeff) avec
82  * un coefficient qui vaut 0, ceci est contraire a nos
83  * conventions
84  */
85  c->vecteur = vect_clean(c->vecteur);
86  }
87  else
88  is_c_norm= false;
89  }
90 
91  else {
92  vect_chg_coeff(&(c->vecteur), TCST,
93  value_uminus(vect_coeff(TCST, c->vecteur)));
94  (void) vect_div(c->vecteur,value_abs(a));
95  c->vecteur= vect_clean(c->vecteur);
96  vect_chg_coeff(&(c->vecteur), TCST,
97  value_uminus(vect_coeff(TCST, c->vecteur)));
98  /* mise a jour du resultat de la division C
99  * if ( b0 < 0 && nb0 > 0)
100  * vect_add_elem(&(c->vecteur),0,-1);
101  * On n'en a plus besoin parce que vect_div utilise la
102  * division a reste toujours positif dont on a besoin
103  */
104  }
105  v=c->vecteur;
106  if(is_c_norm
107  && !VECTEUR_NUL_P(v)
108  && (vect_size(v) == 1)
109  && term_cst(v)) {
110  if(is_egalite) {
111  assert(value_notzero_p(vecteur_val(v)));
112  is_c_norm = false;
113  }
114  else { /* is_inegalite */
115  is_c_norm = value_negz_p(vecteur_val(v)) ;
116  }
117  }
118  }
119  }
120 
121  return is_c_norm;
122 }
VALUE_ZERO
#define VALUE_ZERO
Definition: arithmetique-local.h:302
value_notzero_p
#define value_notzero_p(val)
Definition: arithmetique-local.h:391
value_uminus
#define value_uminus(val)
unary operators on values
Definition: arithmetique-local.h:377
value_negz_p
#define value_negz_p(val)
Definition: arithmetique-local.h:387
value_zero_p
#define value_zero_p(val)
Definition: arithmetique-local.h:388
Value
int Value
Definition: arithmetique-local.h:296
value_abs
#define value_abs(val)
Definition: arithmetique-local.h:379
value_mod
#define value_mod(v1, v2)
Definition: arithmetique-local.h:344
vect_pgcd_except
Value vect_pgcd_except(Pvecteur v, Variable var)
Value vect_pgcd_except(Pvecteur v, Variable var): calcul du pgcd de tous les coefficients non nul d'u...
Definition: reductions.c:130
vect_size
int vect_size(Pvecteur v)
package vecteur - reductions
Definition: reductions.c:47
assert
#define assert(ex)
Definition: newgen_assert.h:41
vect_clean
Pvecteur vect_clean(Pvecteur v)
Pvecteur vect_clean(Pvecteur v): elimination de tous les couples dont le coefficient vaut 0 dans le v...
Definition: scalaires.c:80
vect_div
Pvecteur vect_div(Pvecteur v, Value x)
Pvecteur vect_div(Pvecteur v, Value x): division du vecteur v par le scalaire x, si x est different d...
Definition: scalaires.c:52
Scontrainte::vecteur
Pvecteur vecteur
Definition: contrainte-local.h:89
Svecteur
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
Definition: vecteur-local.h:89
TCST
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
Definition: vecteur-local.h:131
vecteur_val
#define vecteur_val(v)
Definition: vecteur-local.h:127
VECTEUR_NUL_P
#define VECTEUR_NUL_P(v)
Definition: vecteur-local.h:111
term_cst
#define term_cst(varval)
Definition: vecteur-local.h:132
vect_coeff
Value vect_coeff(Variable var, Pvecteur vect)
Variable vect_coeff(Variable var, Pvecteur vect): coefficient de coordonnee var du vecteur vect —> So...
Definition: unaires.c:228
vect_chg_coeff
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val)
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val): mise de la coordonnee var du vecteur *pp...
Definition: unaires.c:143

References assert, TCST, term_cst, value_abs, value_mod, value_negz_p, value_notzero_p, value_uminus, VALUE_ZERO, value_zero_p, vect_chg_coeff(), vect_clean(), vect_coeff(), vect_div(), vect_pgcd_except(), vect_size(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_val.

Referenced by egalite_normalize(), inegalite_normalize(), sc_bounded_normalization(), sc_elim_double_constraints(), and sc_gcd_normalize().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ egalite_normalize()

bool egalite_normalize ( Pcontrainte  eg)

bool egalite_normalize(Pcontrainte eg): reduction d'une equation diophantienne par le pgcd de ses coefficients; l'equation est infaisable si le terme constant n'est pas divisible par ce pgcd

Soit eg == sum ai xi = b i Soit k = pgcd ai i eg := eg/k

return b % k == 0 || all ai == 0 && b != 0;

Parameters
egg

Definition at line 136 of file normalize.c.

138 {
139  return(contrainte_normalize(eg, true));
140 }
contrainte_normalize
bool contrainte_normalize(Pcontrainte c, bool is_egalite)
package contrainte - NORMALISATION D'UN CONTRAINTE
Definition: normalize.c:56

References contrainte_normalize().

Referenced by better_elim_var_with_eg(), gcd_and_constant_dependence_test(), new_elim_var_with_eg(), sc_add_normalize_eq(), sc_bounded_normalization(), sc_minmax_of_variable2(), sc_normalize(), sc_strong_normalize2(), sc_strong_normalize_and_check_feasibility(), and sc_strong_normalize_and_check_feasibility2().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ inegalite_normalize()

bool inegalite_normalize ( Pcontrainte  ineg)

bool inegalite_normalize(Pcontrainte ineg): normalisation d'une inegalite a variables entieres; voir contrainte_normalize; retourne presque toujours true car une inegalite n'ayant qu'un terme constant est toujours faisable a moins qu'il ne reste qu'un terme constant strictement positif.

Soit eg == sum ai xi <= b i Soit k = pgcd ai i eg := eg/k

return true unless all ai are 0 and b < 0

Parameters
inegneg

Definition at line 156 of file normalize.c.

158 {
159  return(contrainte_normalize(ineg ,false));
160 }

References contrainte_normalize().

Referenced by sc_add_normalize_ineq(), sc_bounded_normalization(), sc_normalize(), and sc_strong_normalize_and_check_feasibility().

+ Here is the call graph for this function:
+ Here is the caller graph for this function: