---
title: "Structures"
date: "2023-10-19"
---

# Les fractions

* Représentation d'un nombre sous la forme de la division de deux entiers
\begin{equation*}
q=\frac{n}{d},
\end{equation*}
avec $q\in\mathds{Q}$, $n\in\mathds{Z}$ le numérateur et $d\in\mathds{Z}^+$ le dénominateur (**attention** $d\neq 0$).
* Ces nombres peuvent s'additionner
\begin{align*}
&q_1=\frac{n_1}{d_1},\quad q_2=\frac{n_2}{d_2},\\
&q_3=q_1+q_2=\frac{n_1d_2+n_2d_1}{d_1d_2}.
\end{align*}
se soustraire, multiplier, diviser.

# Représentation informatique

## Fractions

* Numérateur: `int32_t num`;
* Dénominateur: `int32_t denom`.

## Addition

```C
int32_t num1 = 1, denom1 = 2;
int32_t num2 = 1, denom2 = 3;
int32_t num3 = num1 * denom2 + num2 * denom1;
int32_t denom3 = denom1 * denom2;
```

## Pas super pratique....

# Types composés: `struct`{.C} (1/5)

## On peut faire mieux

* Plusieurs variables qu'on aimerait regrouper dans un seul type: `struct`{.C}.

```C
struct fraction { // déclaration du type
    int32_t num, denom;
};

struct fraction frac; // déclaration de frac
// c'est un type tout comme int, float, bool, etc.
```

# Types composés: `struct`{.C} (2/5)

\footnotesize

## Simplifications

- `typedef`{.C} permet de définir un nouveau type.

    ```C
    typedef unsigned int uint;
    typedef struct fraction fraction_t;
    typedef struct fraction {
        int32_t num, denom;
    } fraction_t;
    ```
- L'initialisation peut aussi se faire avec

    ```C
    fraction_t frac = {1, -2};      // num = 1, denom = -2
    fraction_t frac = {.denom = 1, .num = -2}; // idem
    fraction_t frac = {.denom = 1}; // argl! .num non initialisé 
    fraction_t frac2 = frac;        // copie
    ```

# Types composés: `struct`{.C} (3/5)

\footnotesize

## Pointeurs

- Comme pour tout type, on peut avoir des pointeurs vers un `struct`{.C}.
- Les champs sont accessible avec le sélecteur `->`{.C}

    ```C
    fraction_t *frac; // on crée un pointeur
    frac->num = 1;    // seg fault...
    frac->denom = -1; // mémoire pas allouée.
    ```

![La représentation mémoire de `fraction_t`.](figs/pointer_struct.svg){width=50%}

# Types composés: `struct`{.C} (4/5)

\footnotesize

## Initialisation

- Avec le passage par **référence** on peut modifier un struct *en place*.
- Les champs sont accessible avec le sélecteur `->`{.C}

    ```C
    void fraction_init(fraction_t *f, 
                      int32_t num, int32_t denom) 
    {
        // f a déjà été allouée
        f->num   = num;
        f->denom = denom;
    }
    int main() {
        fraction_t frac; // on alloue une fraction
        fraction_init(&frac, 2, -1); // on l'initialise
    }
    ```

# Types composés: `struct`{.C} (5/5)

\footnotesize

## Initialisation version copie

* On peut allouer une fraction, l'initialiser et le retourner.
* La valeur retournée peut être copiée dans une nouvelle structure.

    ```C
    fraction_t fraction_create(int32_t num, int32_t denom) {
        fraction_t f;
        f.num = num; f.denom = denom;
        return f;
    }
    int main() {
        // on crée une fraction et on l'initialise
        // en copiant la fraction créé par fraction_create
        // deux allocation et une copie
        fraction_t frac = fraction_create(2, -1); 
    }
    ```

# Modification en place vs retour

\footnotesize

## Quelle est la différence entre `fraction_init` et `fraction_create`?

```C
void fraction_init(fraction_t *f, int32_t num, int32_t denom);
fraction_t fraction_create(int32_t num, int32_t denom);
```

. . .

* `fraction_init`{.C} modifie une fraction **déjà** allouée quelque part.
* `fraction_create`{.C} alloue une nouvelle fraction et la retourne.

. . .

## Quelle impact sur les performances?

. . .

* `init`: une allocation et modification des données.
* `create`: deux allocation, une modification et une copie.
* Important pour des structures contenance *beaucoup* de données.

# Précision

## Différence avec les nombres à virgule?

. . .

* Les fractions ont une représentation **exacte**,

. . .

* Valeur min/max sont `INT32_MIN` / `INT32_MAX`,

. . .

* Limites sur les valeurs des `num`, `denom` possibles sont les `int32_t` qui peuvent être vite atteintes même pour des "petits" nombres.
\begin{align*}
&\underbrace{\frac{1002583}{1002584}}_{\sim 0.9999990025773402}+\underbrace{\frac{1005359}{1005358}}_{\sim 1.0000009946705553}\\
&=\frac{1002583\cdot 1005358+1002584\cdot 1005359}{1002584\cdot 1005358}\\
&=\underbrace{\frac{2015911687370}{1007955845072}}_{\sim 1.9999999972478952}
\end{align*}
* En réalité on a un dépassement de capacité:
\begin{align*}
\frac{1572025546}{-1361469488}\sim -1.1546535268368792.
\end{align*}