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#![forbid(unsafe_code)]
46
47/// Calcule la racine carrée d'un nombre en virgule fixe Q15.
48///
49/// # Arguments
50///
51/// * `a` — valeur en Q15 dans `[0, 32767]`
52///   (`valeur_réelle = a / 32768.0`)
53///
54/// # Retour
55///
56/// `sqrt(a)` en Q15. Retourne `0` si `a <= 0`.
57///
58/// # Précision
59///
60/// Erreur maximale < 150 ULP (unités au dernier rang) sur toute la plage,
61/// soit < 0.005 en valeur réelle.
62///
63/// # Algorithme
64///
65/// Newton-Raphson en arithmétique entière Q15 :
66/// ```text
67/// x_{n+1} = (x_n + a / x_n) / 2
68/// ```
69/// L'entrée est normalisée dans `[0.5, 2.0[` avant l'itération,
70/// puis dénormalisée via `sqrt(a · 4^n) = 2^n · sqrt(a)`.
71///
72/// # Exemples
73///
74/// ```rust
75/// use embedded_sqrt::sqrt;
76///
77/// // sqrt(0.25) = 0.5  →  8192 → 16384
78/// assert!((sqrt(8192) - 16384).abs() < 100);
79///
80/// // sqrt(≈1.0) = ≈1.0  →  32767 → 32767
81/// assert!((sqrt(32767) - 32767).abs() < 150);
82///
83/// // valeurs négatives → 0
84/// assert_eq!(sqrt(-1), 0);
85/// ```
86pub fn sqrt(a: i32) -> i32 {
87    if a <= 0 { return 0; }
88
89    //  Normalisation 
90    // On ramène val dans [16384, 65536[ = [0.5, 2.0[ en Q15.
91    // Propriété utilisée : sqrt(a · 4^n) = 2^n · sqrt(a)
92    // On mémorise n dans `shift` pour dénormaliser le résultat.
93    let mut val = a as i64;
94    let mut shift = 0i32;
95    while val < 16384 {
96        val <<= 2;
97        shift += 1;
98    }
99    while val >= 65536 {
100        val >>= 2;
101        shift -= 1;
102    }
103
104    //  Estimation initiale 
105    // Deux points de départ couvrant [0.5, 1.0[ et [1.0, 2.0[.
106    // Erreur initiale < 20 %, suffisante pour converger en 6 itérations.
107    let mut x: i64 = if val < 32768 {
108        27525 // ≈ 0.84 en Q15, centre géométrique de [√0.5, 1.0[
109    } else {
110        39000 // ≈ 1.19 en Q15, centre géométrique de [1.0, √2[
111    };
112
113    //  Itérations Newton-Raphson 
114    // x_{n+1} = (x_n + val / x_n) / 2
115    //
116    // Division Q15 : (val / x) en Q15 = (val << 15) / x
117    // La convergence est quadratique : les bits corrects doublent à chaque étape.
118    // 6 itérations donnent > 15 bits de précision.
119    for _ in 0..6 {
120        let div = (val << 15) / x;
121        x = (x + div) >> 1;
122    }
123
124    //  Dénormalisation 
125    // On annule le shift appliqué à l'entrée.
126    if shift >= 0 {
127        (x >> shift) as i32
128    } else {
129        (x << (-shift)) as i32
130    }
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    #[test]
138    fn test_sqrt_perfect_square() {
139        // sqrt(0.25) = 0.5 → sqrt(8192) = 16384 en Q15
140        let res = sqrt(8192);
141        assert!((res - 16384).abs() < 100, "Reçu: {}", res);
142    }
143
144    #[test]
145    fn test_sqrt_one() {
146        // sqrt(≈1.0) = ≈1.0 → sqrt(32767) = 32767 en Q15
147        let res = sqrt(32767);
148        assert!((res - 32767).abs() < 150, "Reçu: {}", res);
149    }
150
151    #[test]
152    fn test_sqrt_various_values() {
153        // sqrt(0.09) = 0.3 → sqrt(2949) = 9830 en Q15
154        let res = sqrt(2949);
155        assert!((res - 9830).abs() < 100, "Reçu: {}", res);
156    }
157
158    #[test]
159    fn test_sqrt_zero_and_negative() {
160        assert_eq!(sqrt(0), 0);
161        assert_eq!(sqrt(-1), 0);
162    }
163}
embedded_sqrt/lib.rs

embedded_sqrt/
lib.rs
