qfall_math/integer/z/arithmetic/
logarithm.rs

1// Copyright © 2023 Marvin Beckmann
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! Implementations to call the logarithm on a [`Z`] integer.
10
11use crate::{error::MathError, integer::Z, rational::Q};
12use flint_sys::fmpz::{fmpz_clog, fmpz_dlog, fmpz_flog};
13
14impl Z {
15    /// Computes the logarithm of a natural number (i.e. an integer greater than `0`)
16    /// with a base greater than `1` rounded up.
17    ///
18    /// **Warning**: It assumes that the return value fits in an [`i64`].
19    ///
20    /// Parameters:
21    /// - `base`: the base of the logarithm
22    ///
23    /// Returns $\lceil log_base(self) \rceil$ as a [`Z`] instance or a [`MathError`],
24    /// if at least one of the conditions
25    /// `base > 1` and `self > 0` isn't met.
26    ///
27    /// # Examples
28    /// ```
29    /// use qfall_math::integer::Z;
30    ///
31    /// let value = Z::from(15);
32    /// let log = value.log_ceil(4).unwrap();
33    ///
34    /// assert_eq!(Z::from(2), log);
35    /// ```
36    ///
37    /// # Errors and Failures
38    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput) if the `base` is smaller than `2`.
39    /// - Returns a [`MathError`] of type
40    ///   [`NonPositive`](MathError::NonPositive) if `self` is not
41    ///   greater than `0`.
42    pub fn log_ceil(&self, base: impl Into<Z>) -> Result<Z, MathError> {
43        let base: Z = base.into();
44        if base <= Z::ONE {
45            Err(MathError::InvalidIntegerInput(format!(
46                "The base must be greater than 1, but the provided is {base}"
47            )))
48        } else if self <= &Z::ZERO {
49            Err(MathError::NonPositive(self.to_string()))
50        } else {
51            Ok(Z::from(unsafe { fmpz_clog(&self.value, &base.value) }))
52        }
53    }
54
55    /// Computes the logarithm of a natural number (i.e. an integer greater than `0`)
56    /// with a base greater than `1` rounded down.
57    ///
58    /// **Warning**: It assumes that the return value fits in an [`i64`].
59    ///
60    /// Parameters:
61    /// - `base`: the base of the logarithm
62    ///
63    /// Returns $\lfloor log_base(self) \rfloor$ as a [`Z`] instance or a [`MathError`],
64    /// if at least one of the conditions
65    /// `base > 1` and `self > 0` isn't met.
66    ///
67    /// # Examples
68    /// ```
69    /// use qfall_math::integer::Z;
70    ///
71    /// let value = Z::from(15);
72    /// let log = value.log_floor(4).unwrap();
73    ///
74    /// assert_eq!(Z::from(1), log);
75    /// ```
76    ///
77    /// # Errors and Failures
78    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput) if the `base` is smaller than `2`.
79    /// - Returns a [`MathError`] of type
80    ///   [`NonPositive`](MathError::NonPositive) if `self` is not
81    ///   greater than `0`.
82    pub fn log_floor(&self, base: impl Into<Z>) -> Result<Z, MathError> {
83        let base: Z = base.into();
84        if base <= Z::ONE {
85            Err(MathError::InvalidIntegerInput(format!(
86                "The base must be greater than 1, but the provided is {base}"
87            )))
88        } else if self <= &Z::ZERO {
89            Err(MathError::NonPositive(self.to_string()))
90        } else {
91            Ok(Z::from(unsafe { fmpz_flog(&self.value, &base.value) }))
92        }
93    }
94
95    /// Computes the natural logarithm of a natural number
96    /// (i.e. an integer greater than `0`)
97    /// approximated as an [`f64`] and returned as a [`Q`].
98    ///
99    /// **Warning**: It assumes that the return value does not overflow an [`f64`].
100    ///
101    /// Returns the double precision approximation of the natural logarithm of `self`
102    /// or a [`MathError`], if `self` is smaller than `1`.
103    ///
104    /// # Examples
105    /// ```
106    /// use qfall_math::integer::Z;
107    /// use qfall_math::rational::Q;
108    ///
109    /// let value = Z::from(1);
110    /// let log = value.ln().unwrap();
111    ///
112    /// assert_eq!(Q::ZERO, log);
113    /// ```
114    ///
115    /// # Errors and Failures
116    /// - Returns a [`MathError`] of type
117    ///   [`NonPositive`](MathError::NonPositive) if `self` is not
118    ///   greater than `0`.
119    pub fn ln(&self) -> Result<Q, MathError> {
120        if self <= &Z::ZERO {
121            Err(MathError::NonPositive(self.to_string()))
122        } else {
123            Ok(Q::from(unsafe { fmpz_dlog(&self.value) }))
124        }
125    }
126
127    /// Computes the logarithm of a natural number (i.e. an integer greater than `0`)
128    /// with an integer base greater than `1` approximated as an [`f64`]
129    /// and returned as a [`Q`].
130    ///
131    /// **Warning**: It assumes that the return value does not overflow an [`f64`].
132    ///
133    /// Parameters:
134    /// - `base`: the base of the logarithm
135    ///
136    /// Returns `log_base(self)` as a [`Q`] instance or a [`MathError`],
137    /// if at least one of the conditions `base > 1` and `self > 0` isn't met.
138    ///
139    /// # Examples
140    /// ```
141    /// use qfall_math::integer::Z;
142    /// use qfall_math::rational::Q;
143    ///
144    /// let value = Z::from(2);
145    /// let log = value.log(2).unwrap();
146    ///
147    /// assert_eq!(Q::ONE, log);
148    /// ```
149    ///
150    /// # Errors and Failures
151    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
152    ///   if the `base` is smaller than `2`.
153    /// - Returns a [`MathError`] of type
154    ///   [`NonPositive`](MathError::NonPositive)
155    ///   if `self` is not
156    ///   greater than `0`.
157    pub fn log(&self, base: impl Into<Z>) -> Result<Q, MathError> {
158        let base: Z = base.into();
159        if base <= Z::ONE {
160            return Err(MathError::InvalidIntegerInput(format!(
161                "The base must be greater than 1, but the provided is {base}"
162            )));
163        }
164
165        let ln_value = self.ln()?;
166        let ln_base = base.ln()?;
167        let log_b = ln_value / ln_base;
168
169        Ok(log_b)
170    }
171}
172
173#[cfg(test)]
174#[allow(clippy::needless_borrows_for_generic_args)]
175mod test_log_ceil {
176    use crate::integer::Z;
177
178    /// Ensure that an error is returned if the base is too small
179    #[test]
180    fn base_too_small() {
181        let value = Z::from(17);
182
183        assert!(value.log_ceil(&Z::ZERO).is_err());
184        assert!(value.log_ceil(&Z::ONE).is_err());
185        assert!(value.log_ceil(&Z::MINUS_ONE).is_err());
186        assert!(value.log_ceil(&Z::from(i64::MIN)).is_err());
187    }
188
189    /// Ensure that an error is returned if `self` is too small
190    #[test]
191    fn value_too_small() {
192        let base = Z::from(2);
193
194        assert!(Z::ZERO.log_ceil(&base).is_err());
195        assert!(Z::MINUS_ONE.log_ceil(&base).is_err());
196        assert!(Z::from(i64::MIN).log_ceil(&base).is_err());
197    }
198
199    /// Ensure that the value is rounded up
200    #[test]
201    fn rounded_up() {
202        let base = Z::from(2);
203
204        assert_eq!(Z::ZERO, Z::from(1).log_ceil(&base).unwrap());
205        assert_eq!(Z::ONE, Z::from(2).log_ceil(&base).unwrap());
206        assert_eq!(Z::from(2), Z::from(3).log_ceil(&base).unwrap());
207        assert_eq!(Z::from(2), Z::from(4).log_ceil(&base).unwrap());
208        assert_eq!(Z::from(64), Z::from(u64::MAX).log_ceil(&base).unwrap());
209        assert_eq!(Z::from(32), Z::from(u64::MAX).log_ceil(Z::from(4)).unwrap());
210    }
211
212    /// Ensures that `log_ceil` is available for all important types
213    /// that can be casted to a [`Z`] instance like u8, u16, i32, i64, ...
214    #[test]
215    fn availability() {
216        let value = Z::from(5);
217
218        let _ = value.log_ceil(2_u8).unwrap();
219        let _ = value.log_ceil(2_u16).unwrap();
220        let _ = value.log_ceil(2_u32).unwrap();
221        let _ = value.log_ceil(2_u64).unwrap();
222        let _ = value.log_ceil(2_i8).unwrap();
223        let _ = value.log_ceil(2_i16).unwrap();
224        let _ = value.log_ceil(2_i32).unwrap();
225        let _ = value.log_ceil(2_i64).unwrap();
226        let _ = value.log_ceil(&value).unwrap();
227    }
228}
229
230#[cfg(test)]
231mod test_log_floor {
232    use crate::integer::Z;
233
234    /// Ensure that an error is returned if the base is too small
235    #[test]
236    fn base_too_small() {
237        let value = Z::from(17);
238
239        assert!(value.log_floor(&Z::ZERO).is_err());
240        assert!(value.log_floor(&Z::ONE).is_err());
241        assert!(value.log_floor(&Z::MINUS_ONE).is_err());
242        assert!(value.log_floor(Z::from(i64::MIN)).is_err());
243    }
244
245    /// Ensure that an error is returned if `self` is too small
246    #[test]
247    fn value_too_small() {
248        let base = Z::from(2);
249
250        assert!(Z::ZERO.log_floor(&base).is_err());
251        assert!(Z::MINUS_ONE.log_floor(&base).is_err());
252        assert!(Z::from(i64::MIN).log_floor(&base).is_err());
253    }
254
255    /// Ensure that the value is rounded down
256    #[test]
257    fn rounded_down() {
258        let base = Z::from(2);
259
260        assert_eq!(Z::ZERO, Z::from(1).log_floor(&base).unwrap());
261        assert_eq!(Z::ONE, Z::from(2).log_floor(&base).unwrap());
262        assert_eq!(Z::ONE, Z::from(3).log_floor(&base).unwrap());
263        assert_eq!(Z::from(2), Z::from(4).log_floor(&base).unwrap());
264        assert_eq!(Z::from(63), Z::from(u64::MAX).log_floor(&base).unwrap());
265        assert_eq!(
266            Z::from(31),
267            Z::from(u64::MAX).log_floor(Z::from(4)).unwrap()
268        );
269    }
270
271    /// Ensures that `log_floor` is available for types
272    /// that can be casted to a [`Z`] instance like u8, u16, i32, i64, ...
273    #[test]
274    fn availability() {
275        let value = Z::from(5);
276
277        let _ = value.log_floor(2_u8).unwrap();
278        let _ = value.log_floor(2_u16).unwrap();
279        let _ = value.log_floor(2_u32).unwrap();
280        let _ = value.log_floor(2_u64).unwrap();
281        let _ = value.log_floor(2_i8).unwrap();
282        let _ = value.log_floor(2_i16).unwrap();
283        let _ = value.log_floor(2_i32).unwrap();
284        let _ = value.log_floor(2_i64).unwrap();
285        let _ = value.log_floor(&value).unwrap();
286    }
287}
288
289#[cfg(test)]
290mod test_natural_ln {
291    use crate::{integer::Z, rational::Q};
292    use std::f64::consts::{LN_2, LN_10};
293
294    /// Ensure that an error is returned if `self` is too small
295    #[test]
296    fn value_too_small() {
297        assert!(Z::ZERO.ln().is_err());
298        assert!(Z::MINUS_ONE.ln().is_err());
299        assert!(Z::from(i64::MIN).ln().is_err());
300    }
301
302    /// Ensure that the output of the function corresponds to the known
303    /// approximated value in [`f64`]
304    #[test]
305    fn static_known_values() {
306        assert_eq!(Q::ZERO, Z::ONE.ln().unwrap());
307        assert_eq!(Q::from(LN_2), Z::from(2).ln().unwrap());
308        assert_eq!(Q::from(LN_10), Z::from(10).ln().unwrap());
309    }
310}
311
312#[cfg(test)]
313mod test_log {
314    use crate::{integer::Z, rational::Q, traits::Distance};
315
316    /// Ensure that an error is returned if the base is too small
317    #[test]
318    fn base_too_small() {
319        let value = Z::from(17);
320
321        assert!(value.log(&Z::ZERO).is_err());
322        assert!(value.log(&Z::ONE).is_err());
323        assert!(value.log(&Z::MINUS_ONE).is_err());
324        assert!(value.log(Z::from(i64::MIN)).is_err());
325    }
326
327    /// Ensure that an error is returned if `self` is too small
328    #[test]
329    fn value_too_small() {
330        let base = Z::from(2);
331
332        assert!(Z::ZERO.log(&base).is_err());
333        assert!(Z::MINUS_ONE.log(&base).is_err());
334        assert!(Z::from(i64::MIN).log(&base).is_err());
335    }
336
337    /// Checks whether the logarithm computation works correctly for small values
338    #[test]
339    fn small_values() {
340        let z_0 = Z::from(1);
341        let z_1 = Z::from(2);
342        let z_2 = Z::from(6);
343        let z_3 = Z::from(9);
344        let cmp_0 = Q::from(6_f64.log2());
345        let cmp_1 = Q::from(2);
346        let max_distance = Q::from((1, 1_000_000_000));
347
348        let res_0 = z_0.log(2).unwrap();
349        let res_1 = z_1.log(2).unwrap();
350        let res_2 = z_2.log(2).unwrap();
351        let res_3 = z_3.log(3).unwrap();
352
353        assert_eq!(Q::ZERO, res_0);
354        assert_eq!(Q::ONE, res_1);
355        assert!(cmp_0.distance(res_2) < max_distance);
356        assert!(cmp_1.distance(res_3) < max_distance);
357    }
358
359    /// Checks whether the logarithm computation works correctly for large values
360    #[test]
361    fn large_values() {
362        let z_0 = Z::from(i64::MAX as u64 + 1);
363        let z_1 = Z::from(i64::MAX);
364        let z_2 = Z::from(i32::MAX);
365        let cmp_0 = Q::from(63);
366        let cmp_1 = Q::from((i64::MAX as f64).log2());
367        let max_distance = Q::from((1, 1_000_000_000));
368
369        let res_0 = z_0.log(2).unwrap();
370        let res_1 = z_1.log(2).unwrap();
371        let res_2 = z_2.log(i32::MAX).unwrap();
372
373        assert!(cmp_0.distance(res_0) < max_distance);
374        assert!(cmp_1.distance(res_1) < max_distance);
375        assert_eq!(Q::ONE, res_2);
376    }
377
378    /// Ensures that the logarithm function is available for all important types
379    /// that can be casted to a [`Z`] instance like u8, u16, i32, i64, ...
380    #[test]
381    fn availability() {
382        let value = Z::from(5);
383
384        let _ = value.log(2_u8).unwrap();
385        let _ = value.log(2_u16).unwrap();
386        let _ = value.log(2_u32).unwrap();
387        let _ = value.log(2_u64).unwrap();
388        let _ = value.log(2_i8).unwrap();
389        let _ = value.log(2_i16).unwrap();
390        let _ = value.log(2_i32).unwrap();
391        let _ = value.log(2_i64).unwrap();
392        let _ = value.log(&value).unwrap();
393    }
394}
qfall_math/integer/z/arithmetic/logarithm.rs

qfall_math/integer/z/arithmetic/
logarithm.rs
