#ifndef IMATHS
#define IMATHS

/*

  Ce module réalise des fonctions sur des nombres entiers

  (c) 1997 Steven Pigeon & Les Logiciels Bergama Enr.

*/


/////////////////////////////////////////////////////////////////////////////////////

// Fonctions diverses 


unsigned int CompactLog2(unsigned int i);
    // Calcule Plafond(Log2(i)), mais en moins de code

unsigned int Log2(unsigned int i);
    // Calcule Plafond(Log2(i)), en plus rapide

unsigned int Log10(unsigned int i);
    // Calcule Plafond(Log10(i))


unsigned int FloorSqrt(unsigned int x);
    // Calcule Floor(Sqrt(i))

unsigned int Sqrt(unsigned int i);
    // Calcule Round(Sqrt(i))

unsigned int iabs(int i);
    // Calcule la valeur absolue de i

int iSign(int i);
    // Calcule le signe de i


/////////////////////////////////////////////////////////////////////////////////////

// Fonctions diverses de bas niveau


int Ror(int i,int p);
int Rol(int i,int p);
    // Rotation à droite, à gauche

int BitReverse(int i, int l);
    // Flip les bits, alignés à gauche (comme les indexes pour Fourier)

void DivMod(int a, int b, int & q, int & r);
void UDivMod(unsigned int a, unsigned int b, unsigned int & q, unsigned int & r);
    // calculent div et mod en meme temps (pairage forcé)


/////////////////////////////////////////////////////////////////////////////////////

// Fonctions du genre "théorie des nombres"

const unsigned int FastDivTest = 223092870; // 2*3*5*7*11*13*17*19*23
const float GoldenRatio        = 1.6180339887f; // (1+Sqrt(5)) / 2
const float InverseGoldenRatio = 0.6180339887f;

unsigned int pgfc(unsigned int a, unsigned int b); 
    // Calcule le plus grand facteur commun de a et b

void SimplifyFraction(int & a, int & b); 
    // Reduit la fraction a/b à sa forme canonique

unsigned int ExpoDiscrete(unsigned int a, unsigned int p);  
    // Calcule l'exponentiation discrete a^p.

unsigned int ModExpoDiscrete(unsigned int a, unsigned int p, unsigned int m); 
    // Calcule l'exponentiation discrete a^p mod m

void Factorise( unsigned int i, unsigned int facteurs[], int & factptr); 
    // Factorise i, retourne les facteurs dans facteurs[32], et leur nombre 
    // dans factptr. à noter: 1 n'est jamais parmi les facteurs.

void FacteursPropres(unsigned int i, unsigned int **facteursPropres, int & factptr);
    // Factorise i et génère les diviseurs propres de i, y compris 1 et i.
    // Le vecteur retourné est alloué. Les facteurs sont dans un ordre quelconque,
    // sauf pour 1 qui est toujours en premier et i qui est toujours en dernier.

int Premier(unsigned int i); 
    // retourne vrai (1) si i est premier

int RelativementPremier(unsigned int a, unsigned int b);
    // retourne vrai si a et b sont relativement premiers.

unsigned int RelativementPremierSqrt(unsigned a);
    // retourne un entier relativement premier à a, tel que b mod a =~= Sqrt(a)

unsigned int RelativementPremierPhi(unsigned a);
    // retourne un entier relativement premier à a, tel que b mod a =~= a * Phi^-1


unsigned int GenerateurStochastique(unsigned int q);
    // retourne un générateur (élément primitif) du corps Zq (pas toujours le même!)
    // et -1 s'il n'en trouve pas (assez rapidement)

unsigned int PlusPetitGenerateur(unsigned int q);
    // retourne le plus petit générateur de q, -1 s'il n'y en a pas.

unsigned int NiemeRacineUniteStochastique(unsigned int q, unsigned int m);
   // retourne la n-ième racine de l'unité, ou 0xffffffffu si q-1 mod n !=0 

unsigned int PlusPetiteNiemeRacineUnite(unsigned int q, unsigned int m);
   // retourne la plus petite m-ième racine de l'unité mod q

/////////////////////////////////////////////////////////////////////////////////////

#endif

