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}