embedded_sqrt/
lib.rs

1// Copyright (C) 2026 Jorge Andre Castro
2//
3// Ce programme est un logiciel libre : vous pouvez le redistribuer et/ou le modifier
4// selon les termes de la Licence Publique Générale GNU telle que publiée par la
5// Free Software Foundation, soit la version 2 de la licence, soit (à votre convention)
6// n'importe quelle version ultérieure.
7
8//! # embedded-sqrt
9//!
10//! Racine carrée en virgule fixe Q15 pour systèmes embarqués.
11//!
12//! ## Caractéristiques
13//!
14//! - `#![no_std]` — aucune dépendance à la bibliothèque standard
15//! - Arithmétique entière pure (pas de flottants, pas de `libm`)
16//! - Compatible RP2040 (Cortex-M0+) et RP2350 (Cortex-M33)
17//! - Algorithme Newton-Raphson (convergence quadratique, 6 itérations)
18//!
19//! ## Format Q15
20//!
21//! En Q15, un `i32` représente un nombre réel dans `[0.0, 1.0[` :
22//! ```text
23//! valeur_réelle = valeur_i32 / 32768.0
24//! ```
25//! Exemples :
26//! - `0`     → 0.0
27//! - `8192`  → 0.25
28//! - `16384` → 0.5
29//! - `23170` → 0.707 (≈ 1/√2)
30//! - `32767` → ≈ 1.0
31//!
32//! ## Exemple
33//!
34//! ```rust
35//! use embedded_sqrt::sqrt;
36//!
37//! // sqrt(0.25) = 0.5
38//! assert_eq!(sqrt(8192), 16384);
39//!
40//! // sqrt(0.0) = 0.0
41//! assert_eq!(sqrt(0), 0);
42//! ```
43
44#![no_std]
45
46/// Calcule la racine carrée d'un nombre en virgule fixe Q15.
47///
48/// # Arguments
49///
50/// * `a` — valeur en Q15 dans `[0, 32767]`
51///   (`valeur_réelle = a / 32768.0`)
52///
53/// # Retour
54///
55/// `sqrt(a)` en Q15. Retourne `0` si `a <= 0`.
56///
57/// # Précision
58///
59/// Erreur maximale < 150 ULP (unités au dernier rang) sur toute la plage,
60/// soit < 0.005 en valeur réelle.
61///
62/// # Algorithme
63///
64/// Newton-Raphson en arithmétique entière Q15 :
65/// ```text
66/// x_{n+1} = (x_n + a / x_n) / 2
67/// ```
68/// L'entrée est normalisée dans `[0.5, 2.0[` avant l'itération,
69/// puis dénormalisée via `sqrt(a · 4^n) = 2^n · sqrt(a)`.
70///
71/// # Exemples
72///
73/// ```rust
74/// use embedded_sqrt::sqrt;
75///
76/// // sqrt(0.25) = 0.5  →  8192 → 16384
77/// assert!((sqrt(8192) - 16384).abs() < 100);
78///
79/// // sqrt(≈1.0) = ≈1.0  →  32767 → 32767
80/// assert!((sqrt(32767) - 32767).abs() < 150);
81///
82/// // valeurs négatives → 0
83/// assert_eq!(sqrt(-1), 0);
84/// ```
85pub fn sqrt(a: i32) -> i32 {
86    if a <= 0 { return 0; }
87
88    // --- Normalisation ---
89    // On ramène val dans [16384, 65536[ = [0.5, 2.0[ en Q15.
90    // Propriété utilisée : sqrt(a · 4^n) = 2^n · sqrt(a)
91    // On mémorise n dans `shift` pour dénormaliser le résultat.
92    let mut val = a as i64;
93    let mut shift = 0i32;
94    while val < 16384 {
95        val <<= 2;
96        shift += 1;
97    }
98    while val >= 65536 {
99        val >>= 2;
100        shift -= 1;
101    }
102
103    // --- Estimation initiale ---
104    // Deux points de départ couvrant [0.5, 1.0[ et [1.0, 2.0[.
105    // Erreur initiale < 20 %, suffisante pour converger en 6 itérations.
106    let mut x: i64 = if val < 32768 {
107        27525 // ≈ 0.84 en Q15, centre géométrique de [√0.5, 1.0[
108    } else {
109        39000 // ≈ 1.19 en Q15, centre géométrique de [1.0, √2[
110    };
111
112    // --- Itérations Newton-Raphson ---
113    // x_{n+1} = (x_n + val / x_n) / 2
114    //
115    // Division Q15 : (val / x) en Q15 = (val << 15) / x
116    // La convergence est quadratique : les bits corrects doublent à chaque étape.
117    // 6 itérations donnent > 15 bits de précision.
118    for _ in 0..6 {
119        let div = (val << 15) / x;
120        x = (x + div) >> 1;
121    }
122
123    // --- Dénormalisation ---
124    // On annule le shift appliqué à l'entrée.
125    if shift >= 0 {
126        (x >> shift) as i32
127    } else {
128        (x << (-shift)) as i32
129    }
130}
131
132#[cfg(test)]
133mod tests {
134    use super::*;
135
136    #[test]
137    fn test_sqrt_perfect_square() {
138        // sqrt(0.25) = 0.5 → sqrt(8192) = 16384 en Q15
139        let res = sqrt(8192);
140        assert!((res - 16384).abs() < 100, "Reçu: {}", res);
141    }
142
143    #[test]
144    fn test_sqrt_one() {
145        // sqrt(≈1.0) = ≈1.0 → sqrt(32767) = 32767 en Q15
146        let res = sqrt(32767);
147        assert!((res - 32767).abs() < 150, "Reçu: {}", res);
148    }
149
150    #[test]
151    fn test_sqrt_various_values() {
152        // sqrt(0.09) = 0.3 → sqrt(2949) = 9830 en Q15
153        let res = sqrt(2949);
154        assert!((res - 9830).abs() < 100, "Reçu: {}", res);
155    }
156
157    #[test]
158    fn test_sqrt_zero_and_negative() {
159        assert_eq!(sqrt(0), 0);
160        assert_eq!(sqrt(-1), 0);
161    }
162}
embedded_sqrt/lib.rs

embedded_sqrt/
lib.rs
