Le Problème de Bâle (Hello, World !)

28 juillet 2023

Hello, World ! Ceci est mon premier article, et il sert exclusivement à tester les fonctionnalités de ce site.

Voici quelques extraits de code dans différents langages qui calculent le Problème de Bâle :

Pour commencer, $L A T E X$

n = 1 \sum \infty \frac{1}{n ^{2}} = \frac{π ^{2}}{6} = 1.6449340668482264

Python

def pi_squared_over_6(N: int) -> float:
    return sum(x**(-2) for x in range(1,N))

Rust

fn pi_squared_over_6(N: u64) -> f64 {
    (1..N).map(|x| 1.0 / ((x*x) as f64)).sum()
}

Haskell

piSquaredOver6 :: Integer -> Double
-- pas de N majuscule en Haskell :(
piSquaredOver6 n = sum $ map (\x -> 1 / fromIntegral (x * x)) [1..n]

C

double pi_squared_over_6(unsigned int N) {
    double sum = 0.0;
    for (int i = 1; i < N; i++) {
        sum += 1.0 / (i*i);
    }
    return sum;
}

Quelle est votre solution préférée ?

Performances

Voyons comment elles se comparent en performance sur un M1 Pro, pour $N = 1 0^{9}$ .

Langage	Temps (ms, $μ \pm σ$ )
Rust (parallélisé)	$112.6 \pm 3.5$
Rust (–release)	$937.9 \pm 0.4$
C (-O3)	$995.3 \pm 0.8$
Haskell (-O3)	$13454 \pm 205$
Python (3.10)	$67720 \pm 0$

Amélioration du code Python

Le code Python a pris un temps absurde à s’exécuter, alors améliorons-le en tirant parti de numpy, qui appelle du code C vectorisé.

import numpy as np

def pi_squared_over_6(N: int) -> float:
    x = np.ones(N)
    r = np.arange(1,N)
    sq = np.square(r)
    div = np.divide(x, sq)
    return float(np.sum(div))

Un peu mieux, mais en vérifiant btm, la consommation excessive de mémoire suggère que la plupart du travail consiste à déplacer des milliards de flottants, plutôt qu’à effectuer les calculs. Essayons de découper cela en morceaux :

def pi_squared_over_6(N: int) -> float:
    CHUNKS = 25000
    SIZE = N // CHUNKS
    s = 0.0
    x = np.ones(N // CHUNKS - 1)
    for i in range(CHUNKS):
        N_tmp = i * SIZE
        r = np.arange(N_tmp + 1, N_tmp + SIZE)
        sq = np.square(r)
        div = np.divide(x, sq)
        s += np.sum(div)
        # libération de la mémoire
        del sq
        del div
        del r
        
    return s

Bien mieux ! Maintenant, il s’exécute en moins de 2 secondes !