Représentation des nombres

Ecriture (petit-boutiste)

Complexité : \( C_n = \mathcal{O}(log(n)) \)

let rec ecriture n b = match n with
    | 0 -> []
    | _ -> let q, r = (n / b, n mod b) in r::(ecriture q b)

HR : Par récurence sur \( n \) : "ecriture n b termine et renvoie l'écriture de n en base b"

#include <math.h>

int* ecriture(int n, int b){
    // Ecriture de n en base b 
    if (n == 0){
        return NULL;
    }
    else{
        int* res = malloc((log_base(n, b) + 1) * sizeof(int));
        int i = 0;
        while (n != 0){
            int r = n % b;
            n = n / b;
            res[i] = r;
            i += 1;
        }
        return res;
    }
}

Variant : \( n \)

Invariant : En notant \( N_0 \) la valeur initiale de \( n \). Les indices de 0 à i-1 contiennent les i premiers chiffres de poids faible de \( N_0 \) et \(n = N_0 / b^i \)

Hörner (petit-boutiste)

Complexité : \( C_n = \mathcal{O}(n) \) où n désigne la taille de l

let horner l b = match l with
    | [] -> 0
    | h::t -> h + b * (horner t b)

HR : Par récurence sur \( n \), taille de la liste : "horner l b termine et renvoie l'écriture de l en base décimale"

int horner(int* ecr, int taille_ecr, int b){
    int res = 0;
    for (int i = taille_ecr - 1; i >= 0; i -= 1){
        res = ecr[i] + b * res;
    }
    return res;
}

Variant : \( i \)

Invariant : Pour tout \(i \), \(res = \sum_{k = i + 1}^{taille\_ecr - 1} ecr_k \cdot b^{k-i-1} \)