malachite_float/float/conversion/from_bits.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::Float;
10use crate::InnerFloat::Finite;
11use alloc::vec;
12use core::cmp::Ordering::{self, *};
13use malachite_base::num::arithmetic::traits::{DivisibleByPowerOf2, NegModPowerOf2, PowerOf2};
14use malachite_base::num::basic::integers::PrimitiveInt;
15use malachite_base::num::logic::traits::SignificantBits;
16use malachite_base::rounding_modes::RoundingMode::{self, *};
17use malachite_nz::natural::{LIMB_HIGH_BIT, Natural, bit_to_limb_count_ceiling};
18use malachite_nz::platform::Limb;
19
20impl Float {
21 /// Returns an approximation of a real number, given the number's bits. To avoid troublesome
22 /// edge cases, the number should not be a dyadic rational (and the iterator of bits should
23 /// therefore be infinite, and not eventually 0 or 1). Given this assumption, the rounding mode
24 /// `Exact` should never be passed.
25 ///
26 /// The approximation has precision `prec` and is rounded according to the provided rounding
27 /// mode.
28 ///
29 /// This function reads `prec + z` bits, or `prec + z + 1` bits if `rm` is `Nearest`, where `z`
30 /// is the number of leading false bits in `bits`.
31 ///
32 /// If the first bit is set, this function produces a value in the interval $[1/2,1)$; each
33 /// leading false bit halves that interval, so $z$ of them place the value in
34 /// $[2^{-z-1},2^{-z})$. The exponent is not range-checked, so a bit sequence beginning with
35 /// enough false bits to reach `Float::MIN_EXPONENT` would underflow.
36 ///
37 /// $$
38 /// f((x_k),p,m) = C+\varepsilon,
39 /// $$
40 /// where
41 /// $$
42 /// C=\sum_{k=0}^\infty x_k 2^{-(k+1)}.
43 /// $$
44 /// - If $m$ is not `Nearest`, then $|\varepsilon| < 2^{\lfloor\log_2 C\rfloor-p+1}$.
45 /// - If $m$ is `Nearest`, then $|\varepsilon| < 2^{\lfloor\log_2 C\rfloor-p}$.
46 ///
47 /// The output has precision `prec`.
48 ///
49 /// # Worst-case complexity
50 /// $T(n) = O(n)$
51 ///
52 /// $M(n) = O(n)$
53 ///
54 /// where $T$ is time, $M$ is additional memory, and $n$ is `prec`.
55 ///
56 /// # Panics
57 /// Panics if `prec` is zero or `rm` is `Exact`.
58 ///
59 /// # Examples
60 /// ```
61 /// use malachite_base::rounding_modes::RoundingMode::*;
62 /// use malachite_float::Float;
63 /// use std::cmp::Ordering::*;
64 ///
65 /// // Produces 10100100010000100000...
66 /// struct Bits {
67 /// b: bool,
68 /// k: usize,
69 /// j: usize,
70 /// }
71 ///
72 /// impl Iterator for Bits {
73 /// type Item = bool;
74 ///
75 /// fn next(&mut self) -> Option<bool> {
76 /// Some(if self.b {
77 /// self.b = false;
78 /// self.j = self.k;
79 /// true
80 /// } else {
81 /// self.j -= 1;
82 /// if self.j == 0 {
83 /// self.k += 1;
84 /// self.b = true;
85 /// }
86 /// false
87 /// })
88 /// }
89 /// }
90 ///
91 /// impl Bits {
92 /// fn new() -> Bits {
93 /// Bits {
94 /// b: true,
95 /// k: 1,
96 /// j: 1,
97 /// }
98 /// }
99 /// }
100 ///
101 /// let (c, o) = Float::non_dyadic_from_bits_prec_round(Bits::new(), 100, Floor);
102 /// assert_eq!(c.to_string(), "0.64163256065515386629384277022540");
103 /// assert_eq!(o, Less);
104 ///
105 /// let (c, o) = Float::non_dyadic_from_bits_prec_round(Bits::new(), 100, Ceiling);
106 /// assert_eq!(c.to_string(), "0.64163256065515386629384277022619");
107 /// assert_eq!(o, Greater);
108 /// ```
109 pub fn non_dyadic_from_bits_prec_round<I: Iterator<Item = bool>>(
110 mut bits: I,
111 prec: u64,
112 rm: RoundingMode,
113 ) -> (Self, Ordering) {
114 assert_ne!(prec, 0);
115 assert_ne!(rm, Exact);
116 let len = bit_to_limb_count_ceiling(prec);
117 let mut limbs = vec![0; len];
118 let mut limbs_it = limbs.iter_mut().rev();
119 let mut x = limbs_it.next().unwrap();
120 let mut mask = LIMB_HIGH_BIT;
121 let mut seen_one = false;
122 let mut exponent: i32 = 0;
123 let mut remaining = prec;
124 for b in &mut bits {
125 if !seen_one {
126 if b {
127 seen_one = true;
128 } else {
129 exponent = exponent.checked_sub(1).unwrap();
130 continue;
131 }
132 }
133 if b {
134 *x |= mask;
135 }
136 remaining -= 1;
137 if remaining == 0 {
138 break;
139 }
140 if mask == 1 {
141 x = limbs_it.next().unwrap();
142 mask = LIMB_HIGH_BIT;
143 } else {
144 mask >>= 1;
145 }
146 }
147 let mut significand = Natural::from_owned_limbs_asc(limbs);
148 let increment = rm == Up || rm == Ceiling || (rm == Nearest && bits.next() == Some(true));
149 if increment {
150 significand +=
151 Natural::from(Limb::power_of_2(prec.neg_mod_power_of_2(Limb::LOG_WIDTH)));
152 if !significand
153 .significant_bits()
154 .divisible_by_power_of_2(Limb::LOG_WIDTH)
155 {
156 significand >>= 1u32;
157 exponent += 1;
158 }
159 }
160 (
161 Self(Finite {
162 sign: true,
163 exponent,
164 precision: prec,
165 significand,
166 }),
167 if increment { Greater } else { Less },
168 )
169 }
170
171 /// Returns an approximation of a real number, given the number's bits. To avoid troublesome
172 /// edge cases, the number should not be a dyadic rational (and the iterator of bits should
173 /// therefore be infinite, and not eventually 0 or 1).
174 ///
175 /// The approximation has precision `prec` and is rounded according to the `Nearest` rounding
176 /// mode.
177 ///
178 /// This function reads `prec + z + 1` bits, where `z` is the number of leading false bits in
179 /// `bits`.
180 ///
181 /// If the first bit is set, this function produces a value in the interval $[1/2,1)$; each
182 /// leading false bit halves that interval, so $z$ of them place the value in
183 /// $[2^{-z-1},2^{-z})$. The exponent is not range-checked, so a bit sequence beginning with
184 /// enough false bits to reach `Float::MIN_EXPONENT` would underflow.
185 ///
186 /// $$
187 /// f((x_k),p,m) = C+\varepsilon,
188 /// $$
189 /// where
190 /// $$
191 /// C=\sum_{k=0}^\infty x_k 2^{-(k+1)}
192 /// $$
193 /// and $|\varepsilon| < 2^{\lfloor\log_2 C\rfloor-p}$.
194 ///
195 /// The output has precision `prec`.
196 ///
197 /// # Worst-case complexity
198 /// $T(n) = O(n)$
199 ///
200 /// $M(n) = O(n)$
201 ///
202 /// where $T$ is time, $M$ is additional memory, and $n$ is `prec`.
203 ///
204 /// # Panics
205 /// Panics if `prec` is zero.
206 ///
207 /// # Examples
208 /// ```
209 /// use malachite_float::Float;
210 /// use std::cmp::Ordering::*;
211 ///
212 /// // Produces 10100100010000100000...
213 /// struct Bits {
214 /// b: bool,
215 /// k: usize,
216 /// j: usize,
217 /// }
218 ///
219 /// impl Iterator for Bits {
220 /// type Item = bool;
221 ///
222 /// fn next(&mut self) -> Option<bool> {
223 /// Some(if self.b {
224 /// self.b = false;
225 /// self.j = self.k;
226 /// true
227 /// } else {
228 /// self.j -= 1;
229 /// if self.j == 0 {
230 /// self.k += 1;
231 /// self.b = true;
232 /// }
233 /// false
234 /// })
235 /// }
236 /// }
237 ///
238 /// impl Bits {
239 /// fn new() -> Bits {
240 /// Bits {
241 /// b: true,
242 /// k: 1,
243 /// j: 1,
244 /// }
245 /// }
246 /// }
247 ///
248 /// let (c, o) = Float::non_dyadic_from_bits_prec(Bits::new(), 1);
249 /// assert_eq!(c.to_string(), "0.50");
250 /// assert_eq!(o, Less);
251 ///
252 /// let (c, o) = Float::non_dyadic_from_bits_prec(Bits::new(), 10);
253 /// assert_eq!(c.to_string(), "0.64160");
254 /// assert_eq!(o, Less);
255 ///
256 /// let (c, o) = Float::non_dyadic_from_bits_prec(Bits::new(), 100);
257 /// assert_eq!(c.to_string(), "0.64163256065515386629384277022540");
258 /// assert_eq!(o, Less);
259 /// ```
260 #[inline]
261 pub fn non_dyadic_from_bits_prec<I: Iterator<Item = bool>>(
262 bits: I,
263 prec: u64,
264 ) -> (Self, Ordering) {
265 Self::non_dyadic_from_bits_prec_round(bits, prec, Nearest)
266 }
267}