PIPS
|
Go to the source code of this file.
Macros | |
#define | GCD_MAX_A 15 |
#define | GCD_MAX_B 15 |
Functions | |
Value | pgcd_slow (Value a, Value b) |
package arithmetique More... | |
Value | pgcd_fast (Value a, Value b) |
int pgcd_fast(int a, int b): calcul iteratif du pgcd de deux entiers; le pgcd retourne est toujours positif; il n'est pas defini si a et b sont nuls (abort); More... | |
Value | pgcd_interne (Value a, Value b) |
int pgcd_interne(int a, int b): calcul iteratif du pgcd de deux entiers strictement positifs tels que a > b; le pgcd retourne est toujours positif; More... | |
Value | gcd_subtract (Value a, Value b) |
int gcd_subtract(int a, int b): find the gcd (pgcd) of two integers More... | |
Value | vecteur_bezout (Value u[], Value v[], int l) |
int vecteur_bezout(int u[], int v[], int l): calcul du vecteur v qui verifie le theoreme de bezout pour le vecteur u; les vecteurs u et v sont de dimension l More... | |
Value | bezout (Value a, Value b, Value *x, Value *y) |
int bezout(int a, int b, int *x, int *y): calcule x et y, les deux nombres qui verifient le theoreme de Bezout pour a et b; le pgcd de a et b est retourne par valeur More... | |
Value | bezout_grl (Value a, Value b, Value *x, Value *y) |
int bezout_grl(int a, int b, int *x, int *y): calcule x et y, les deux entiers quelconcs qui verifient le theoreme de Bezout pour a et b; le pgcd de a et b est retourne par valeur More... | |
#define GCD_MAX_A 15 |
#define GCD_MAX_B 15 |
int bezout(int a, int b, int *x, int *y): calcule x et y, les deux nombres qui verifient le theoreme de Bezout pour a et b; le pgcd de a et b est retourne par valeur
a * x + b * y = gcd(a,b) return gcd(a,b)
Definition at line 265 of file pgcd.c.
References value_div, value_ge, value_minus, value_mod, value_mult, value_notzero_p, VALUE_ONE, VALUE_ZERO, value_zero_p, and x.
Referenced by vecteur_bezout().
int bezout_grl(int a, int b, int *x, int *y): calcule x et y, les deux entiers quelconcs qui verifient le theoreme de Bezout pour a et b; le pgcd de a et b est retourne par valeur
a * x + b * y = gcd(a,b) return gcd(a,b) gcd () >=0 le pre et le post conditions de pgcd sont comme la fonction gcd_subtract(). les situations speciaux sont donnes ci_dessous: si (a==0 et b==0) x=y=0; gcd()=0, si (a==0)(ou b==0) x=1(ou -1) y=0 (ou x=0 y=1(ou -1)) et gcd()=a(ou -a) (ou gcd()=b(ou -b))
les signes de a et b
Definition at line 324 of file pgcd.c.
References value_div, value_ge, value_minus, value_mod, VALUE_MONE, value_mult, value_neg_p, value_notzero_p, VALUE_ONE, value_uminus, VALUE_ZERO, value_zero_p, and x.
Referenced by base_G_h1_unnull().
int gcd_subtract(int a, int b): find the gcd (pgcd) of two integers
There is no precondition on the input. Negative input is handled in the same way as positive ones. If one input is zero the output is equal to the other input - thus an input of two zeros is the only way an output of zero is created. Postcondition: gcd(a,b) > 0 ; gcd(a,b)==0 iff a==0 and b==0 whereas it should be undefined (F. Irigoin) Exception: gcd(0,0) aborts Implementation: by subtractions
Note: the signs of a and b do not matter because they can be exactly divided by the gcd
b == 0
Definition at line 189 of file pgcd.c.
References assert, value_abs, value_ge, value_minus, value_notzero_p, and value_zero_p.
int pgcd_fast(int a, int b): calcul iteratif du pgcd de deux entiers; le pgcd retourne est toujours positif; il n'est pas defini si a et b sont nuls (abort);
si cette routine n'est JAMAIS appelee avec des arguments nuls, il faudrait supprimer les deux tests d'egalite a 0; ca devrait etre le cas avec les vecteurs creux
Definition at line 82 of file pgcd.c.
References assert, pgcd_interne(), value_abs, value_gt, value_notzero_p, and value_zero_p.
int pgcd_interne(int a, int b): calcul iteratif du pgcd de deux entiers strictement positifs tels que a > b; le pgcd retourne est toujours positif;
Definition d'une look-up table pour les valeurs de a appartenant a 0..GCD_MAX_A et pour les valeurs de b appartenant a 1..GCD_MAX_B
Serait-il utile d'ajouter une test b==1 pour supprimer une colonne?
la commutativite du pgcd n'est pas utilisee pour reduire la taille de la table
b == 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a == 0
a == 1
a == 2
a == 3
a == 4
a == 5
a == 6
a == 7
a == 8
a == 9
a == 10
a == 11
a == 12
a == 13
a == 14
a == 15
on pourrait aussi utiliser une table des nombres premiers pour diminuer le nombre de boucles
on utilise la valeur particuliere -1 pour iterer
compute modulo(a,b) en utilisant la routine C puisque a et b sont strictement positifs (vaudrait-il mieux utiliser la soustraction?)
Definition at line 106 of file pgcd.c.
References assert, GCD_MAX_A, GCD_MAX_B, int_to_value, value_gt, value_le, value_mod, VALUE_MONE, value_neg_p, value_pos_p, VALUE_TO_INT, and value_zero_p.
Referenced by pgcd_fast().
package arithmetique
INTLIBRARY Value pgcd_slow(Value a, Value b) computation of the gcd of a and b. the result is always positive. standard algorithm in log(max(a,b)). pgcd_slow(0,0)==1 (maybe should we abort?). I changed from a recursive for a simple iterative version, FC 07/96.
a==0, b==0
a==0, b!=0
a!=0, b==0
a==b
swap
on entry in this loop, a > b > 0 is insured
Definition at line 44 of file pgcd.c.
References value_abs, value_absolute, value_eq, value_gt, value_mod, value_notzero_p, VALUE_ONE, and value_zero_p.
Referenced by matrice_determinant(), matrice_diagonale_inversion(), matrice_triangulaire_inversion(), matrix_determinant(), and substitute_var_with_vec().
int vecteur_bezout(int u[], int v[], int l): calcul du vecteur v qui verifie le theoreme de bezout pour le vecteur u; les vecteurs u et v sont de dimension l
-> -> -> < u . v > = gcd(u ) i
printf("gcd = %d \n",gcd);
sum u * v = gcd(u ) k<l k k k<l k
a1 = gcd (u ) k<l-1 k
printf("gcd = %d\n",gcd);
Definition at line 220 of file pgcd.c.
References assert, bezout(), VALUE_ONE, value_product, and x.