Un binôme sans factorielles


def binomial(n, p):
    if p < 0 or p > n:
        return 0
    p = min(p, n - p)              # symetrie : moins d'iterations
    r = 1
    for i in range(p):
        r = r * (n - i) // (i + 1)  # division EXACTE a chaque tour
    return r

Le principe. On utilise $(p n) = \prod_{i = 0}^{p - 1} \frac{n - i}{i + 1}$ , en effectuant la division à chaque tour. Elle tombe toujours juste : après $i$ tours, r vaut $(i n)$ , qui est entier — c'est ce qui autorise le //.

Les tailles en jeu. Pour $(50 100)$ :

$(50 100) \approx 1, 009 \times 1 0^{29} (30 chiffres), 100! \approx 9, 33 \times 1 0^{157} (158 chiffres) .$

La voie factorielle construit donc un nombre de $158$ chiffres pour en obtenir un de $30$ , avant de tout simplifier. Notre boucle ne dépasse jamais $p$ fois le résultat final.

Ce que cela change. En Python, les entiers sont de taille arbitraire : les deux méthodes donnent le même résultat exact, seule la vitesse souffre. Dans un langage à entiers $64$ bits, la version factorielle déborderait dès $21!$ et rendrait un résultat faux sans le moindre avertissement, là où celle-ci reste juste jusqu'à $(31 62) \approx 4, 7 \times 1 0^{17}$ .

La ligne $p = min (p, n - p)$ exploite $(p n) = (n - p n)$ : pour $(99 100)$ , elle ramène $99$ tours à un seul.

Énoncé

Corrigé

Exercices semblables