Skip to main content

publet_algorithms/
fixed.rs

1//! Fixed-point arithmetic scaled by 10^6.
2//!
3//! Built for callers that need the same computation over the same input to
4//! yield bit-identical results across every implementation and every run --
5//! [`crate::propagate`] is the motivating case. Floating point cannot
6//! provide that: results depend on rounding mode, on instruction selection,
7//! on whether an intermediate stayed in a wider register.
8//!
9//! The type deliberately implements no conversion from `f32` or `f64`. A
10//! single `as f64` anywhere in a weight computation would reintroduce the
11//! problem silently, and the absence of a conversion means the mistake does
12//! not compile.
13//!
14//! # Examples
15//!
16//! ```
17//! use publet_algorithms::Fixed6;
18//!
19//! let whole = Fixed6::ONE;
20//! let third = whole.mul_div(Fixed6::from_integer(1), Fixed6::from_integer(3));
21//! // Truncating division: one third is 0.333333, never 0.3333334.
22//! assert_eq!(third.to_string(), "0.333333");
23//! ```
24
25// Clippy's `integer_division` lint advises using floats to avoid precision
26// loss. That advice is correct in general and wrong here: bit-identical
27// results across implementations is the point, which floating point cannot
28// give, so truncating integer division is the specified behaviour rather
29// than an approximation of something better.
30#![allow(clippy::integer_division)]
31
32use std::fmt;
33use std::iter::Sum;
34use std::ops::{Add, Sub};
35
36/// The scaling factor: six decimal places.
37pub const SCALE: i128 = 1_000_000;
38
39/// A number scaled by 10^6, with truncating division.
40///
41/// Backed by `i128` so that a multiplication of two scaled values cannot
42/// overflow before the division that rescales it.
43#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default, Hash)]
44pub struct Fixed6(i128);
45
46impl Fixed6 {
47    /// Zero.
48    pub const ZERO: Self = Self(0);
49    /// One.
50    pub const ONE: Self = Self(SCALE);
51
52    /// Construct from a raw scaled value.
53    ///
54    /// # Example
55    ///
56    /// ```
57    /// use publet_algorithms::Fixed6;
58    ///
59    /// // 1_500_000 scaled by 10^6 is 1.5.
60    /// assert_eq!(Fixed6::from_scaled(1_500_000).to_string(), "1.500000");
61    /// ```
62    #[must_use]
63    pub const fn from_scaled(raw: i128) -> Self {
64        Self(raw)
65    }
66
67    /// Construct from a whole number.
68    ///
69    /// # Example
70    ///
71    /// ```
72    /// use publet_algorithms::Fixed6;
73    ///
74    /// assert_eq!(Fixed6::from_integer(3).to_string(), "3.000000");
75    /// assert_eq!(Fixed6::from_integer(-2).to_scaled(), -2_000_000);
76    /// ```
77    #[must_use]
78    pub const fn from_integer(n: i64) -> Self {
79        Self(n as i128 * SCALE)
80    }
81
82    /// The underlying scaled value.
83    ///
84    /// # Example
85    ///
86    /// ```
87    /// use publet_algorithms::{Fixed6, SCALE};
88    ///
89    /// assert_eq!(Fixed6::ONE.to_scaled(), SCALE);
90    /// ```
91    #[must_use]
92    pub const fn to_scaled(self) -> i128 {
93        self.0
94    }
95
96    /// `self * numerator / denominator`, truncating toward zero.
97    ///
98    /// The multiplication happens before the division and in `i128`, so
99    /// precision is not lost to an intermediate rounding that a different
100    /// implementation might place elsewhere.
101    ///
102    /// Returns [`Self::ZERO`] when `denominator` is zero, which is the
103    /// arithmetic identity this layer wants: a key that confers no weight
104    /// at all confers none to anyone.
105    ///
106    /// # Example
107    ///
108    /// ```
109    /// use publet_algorithms::Fixed6;
110    ///
111    /// let two = Fixed6::from_integer(2);
112    /// let three = Fixed6::from_integer(3);
113    /// // 2 * 1 / 3, truncated: 0.666666, not 0.666667.
114    /// assert_eq!(two.mul_div(Fixed6::ONE, three).to_string(), "0.666666");
115    ///
116    /// // A zero denominator gives zero rather than panicking.
117    /// assert_eq!(two.mul_div(Fixed6::ONE, Fixed6::ZERO), Fixed6::ZERO);
118    /// ```
119    #[must_use]
120    pub fn mul_div(self, numerator: Self, denominator: Self) -> Self {
121        if denominator.0 == 0 {
122            return Self::ZERO;
123        }
124        // (a*S * b*S) / (c*S) = (a*b/c)*S, already at the right scale.
125        Self(self.0.saturating_mul(numerator.0) / denominator.0)
126    }
127
128    /// `self * other`, truncating toward zero.
129    ///
130    /// # Example
131    ///
132    /// ```
133    /// use publet_algorithms::Fixed6;
134    ///
135    /// let half = Fixed6::from_scaled(500_000);
136    /// assert_eq!(half.times(half).to_string(), "0.250000");
137    /// ```
138    #[must_use]
139    pub fn times(self, other: Self) -> Self {
140        Self(self.0.saturating_mul(other.0) / SCALE)
141    }
142
143    /// `self / other`, truncating toward zero.
144    ///
145    /// Returns [`Self::ZERO`] when `other` is zero.
146    ///
147    /// # Example
148    ///
149    /// ```
150    /// use publet_algorithms::Fixed6;
151    ///
152    /// assert_eq!(Fixed6::ONE.ratio(Fixed6::from_integer(3)).to_string(), "0.333333");
153    /// assert_eq!(Fixed6::ONE.ratio(Fixed6::ZERO), Fixed6::ZERO);
154    /// ```
155    #[must_use]
156    pub fn ratio(self, other: Self) -> Self {
157        if other.0 == 0 {
158            return Self::ZERO;
159        }
160        Self(self.0.saturating_mul(SCALE) / other.0)
161    }
162
163    /// The smaller of two values.
164    ///
165    /// # Example
166    ///
167    /// ```
168    /// use publet_algorithms::Fixed6;
169    ///
170    /// assert_eq!(Fixed6::ONE.min(Fixed6::ZERO), Fixed6::ZERO);
171    /// ```
172    #[must_use]
173    pub fn min(self, other: Self) -> Self {
174        if self.0 <= other.0 { self } else { other }
175    }
176
177    /// Whether this value is zero.
178    ///
179    /// # Example
180    ///
181    /// ```
182    /// use publet_algorithms::Fixed6;
183    ///
184    /// assert!(Fixed6::ZERO.is_zero());
185    /// // Truncation can reach zero: a millionth of a millionth.
186    /// let tiny = Fixed6::from_scaled(1);
187    /// assert!(tiny.times(tiny).is_zero());
188    /// ```
189    #[must_use]
190    pub const fn is_zero(self) -> bool {
191        self.0 == 0
192    }
193
194    /// Halve repeatedly, for exponential decay.
195    ///
196    /// Computes `self * 2^(-numerator/denominator)` by applying whole
197    /// halvings and then a linear interpolation of the remainder. Exact
198    /// exponentiation would need a transcendental function, which cannot be
199    /// made bit-identical across platforms; this approximation is fully
200    /// specified by integer operations and therefore can.
201    ///
202    /// # Example
203    ///
204    /// ```
205    /// use publet_algorithms::Fixed6;
206    ///
207    /// // One half-life: exactly half.
208    /// assert_eq!(Fixed6::ONE.halve_fractional(30, 30).to_string(), "0.500000");
209    /// // Half a half-life: interpolated between 1 and 0.5 (2^-0.5 is about 0.707).
210    /// assert_eq!(Fixed6::ONE.halve_fractional(15, 30).to_string(), "0.750000");
211    /// ```
212    #[must_use]
213    pub fn halve_fractional(self, numerator: u64, denominator: u64) -> Self {
214        if denominator == 0 || self.0 == 0 {
215            return self;
216        }
217        let whole = numerator / denominator;
218        let mut value = self.0;
219        // Beyond 127 halvings the result is zero in this representation.
220        for _ in 0..whole.min(127) {
221            value /= 2;
222        }
223        if whole >= 127 {
224            return Self(0);
225        }
226        let remainder = numerator % denominator;
227        if remainder == 0 {
228            return Self(value);
229        }
230        // Linear interpolation between value and value/2 over the fraction.
231        let frac = i128::from(remainder);
232        let den = i128::from(denominator);
233        Self(value - (value * frac) / (den * 2))
234    }
235}
236
237impl Add for Fixed6 {
238    type Output = Self;
239    fn add(self, other: Self) -> Self {
240        Self(self.0.saturating_add(other.0))
241    }
242}
243
244impl Sub for Fixed6 {
245    type Output = Self;
246    fn sub(self, other: Self) -> Self {
247        Self(self.0.saturating_sub(other.0))
248    }
249}
250
251impl Sum for Fixed6 {
252    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
253        iter.fold(Self::ZERO, Add::add)
254    }
255}
256
257impl fmt::Display for Fixed6 {
258    /// Render with exactly six decimal places, so that output is stable.
259    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
260        let negative = self.0 < 0;
261        let magnitude = self.0.unsigned_abs();
262        let whole = magnitude / SCALE.unsigned_abs();
263        let frac = magnitude % SCALE.unsigned_abs();
264        if negative {
265            write!(f, "-")?;
266        }
267        write!(f, "{whole}.{frac:06}")
268    }
269}
270
271#[cfg(test)]
272mod tests {
273    use super::*;
274
275    // covers: Fixed6::from_integer, Fixed6::from_scaled, Fixed6::mul_div
276    #[test]
277    fn mul_div_keeps_the_scale() {
278        let two = Fixed6::from_integer(2);
279        let three = Fixed6::from_integer(3);
280        // 2 * 2 / 3
281        assert_eq!(two.mul_div(two, three).to_string(), "1.333333");
282        // Multiplying before dividing preserves precision a naive
283        // (self/den)*num would lose.
284        let small = Fixed6::from_scaled(3);
285        assert_eq!(
286            small.mul_div(Fixed6::from_integer(1000), Fixed6::from_integer(3)),
287            Fixed6::from_scaled(1000)
288        );
289    }
290
291    // covers: Fixed6::from_integer, Fixed6::ratio
292    #[test]
293    fn truncates_toward_zero_rather_than_rounding() {
294        let one = Fixed6::ONE;
295        let three = Fixed6::from_integer(3);
296        assert_eq!(one.ratio(three).to_string(), "0.333333");
297        let two = Fixed6::from_integer(2);
298        // 2/3 truncates to 0.666666, not 0.666667.
299        assert_eq!(two.ratio(three).to_string(), "0.666666");
300    }
301
302    // covers: Fixed6::mul_div, Fixed6::ratio
303    #[test]
304    fn division_by_zero_yields_zero() {
305        assert_eq!(Fixed6::ONE.ratio(Fixed6::ZERO), Fixed6::ZERO);
306        assert_eq!(Fixed6::ONE.mul_div(Fixed6::ONE, Fixed6::ZERO), Fixed6::ZERO);
307    }
308
309    // covers: Fixed6::from_scaled
310    #[test]
311    fn display_is_stable_to_six_places() {
312        assert_eq!(Fixed6::ZERO.to_string(), "0.000000");
313        assert_eq!(Fixed6::ONE.to_string(), "1.000000");
314        assert_eq!(Fixed6::from_scaled(1).to_string(), "0.000001");
315        assert_eq!(Fixed6::from_scaled(-1).to_string(), "-0.000001");
316    }
317
318    // covers: Fixed6::halve_fractional
319    #[test]
320    fn halving_is_exact_on_whole_periods() {
321        let one = Fixed6::ONE;
322        assert_eq!(one.halve_fractional(0, 10), one);
323        assert_eq!(one.halve_fractional(10, 10).to_string(), "0.500000");
324        assert_eq!(one.halve_fractional(20, 10).to_string(), "0.250000");
325        assert_eq!(one.halve_fractional(1000, 10), Fixed6::ZERO);
326    }
327
328    // covers: Fixed6::from_scaled
329    #[test]
330    fn addition_saturates_rather_than_wrapping() {
331        let big = Fixed6::from_scaled(i128::MAX);
332        assert_eq!(big + big, Fixed6::from_scaled(i128::MAX));
333    }
334}