factorion_lib/
calculation_tasks.rs

1//! This module handles the calculation of pending calculation tasks
2
3use factorion_math::rug::ops::AddFrom;
4#[cfg(any(feature = "serde", test))]
5use serde::{Deserialize, Serialize};
6
7use crate::calculation_results::Number;
8
9use crate::Consts;
10use crate::{
11    calculation_results::{Calculation, CalculationResult},
12    math,
13};
14
15use crate::rug::{Float, ops::Pow};
16
17pub mod recommended {
18    use factorion_math::rug::Complete;
19    use factorion_math::rug::integer::IntegerExt64;
20
21    use crate::rug::Integer;
22    // Limit for exact calculation, set to limit calculation time
23    pub static UPPER_CALCULATION_LIMIT: fn() -> Integer = || 1_000_000.into();
24    // Limit for approximation, set to ensure enough accuracy (5 decimals)
25    pub static UPPER_APPROXIMATION_LIMIT: fn() -> Integer =
26        || Integer::u64_pow_u64(10, 300).complete();
27    // Limit for exact subfactorial calculation, set to limit calculation time
28    pub static UPPER_SUBFACTORIAL_LIMIT: fn() -> Integer = || 100_000.into();
29    // Limit for exact termial calculation, set to limit calculation time (absurdly high)
30    pub static UPPER_TERMIAL_LIMIT: fn() -> Integer = || Integer::u64_pow_u64(10, 10000).complete();
31    // Limit for approximation, set to ensure enough accuracy (5 decimals)
32    // Based on max float. (bits)
33    pub static UPPER_TERMIAL_APPROXIMATION_LIMIT: u32 = 1073741822;
34}
35
36/// Representation of the calculation to be done
37#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
38#[cfg_attr(any(feature = "serde", test), derive(Serialize, Deserialize))]
39pub struct CalculationJob {
40    pub base: CalculationBase,
41    /// Type of the calculation
42    pub level: i32,
43    /// Number of negations encountered
44    pub negative: u32,
45}
46/// The basis of a calculation, whether [Number] or [CalculationJob].
47#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
48#[cfg_attr(any(feature = "serde", test), derive(Serialize, Deserialize))]
49pub enum CalculationBase {
50    Num(Number),
51    Calc(Box<CalculationJob>),
52}
53
54impl CalculationJob {
55    /// Execute the calculation. \
56    /// If include_steps is enabled, will return all intermediate results.
57    pub fn execute(self, include_steps: bool, consts: &Consts) -> Vec<Option<Calculation>> {
58        let CalculationJob {
59            mut base,
60            mut level,
61            mut negative,
62        } = self;
63        let size = {
64            let mut n = 1;
65            let mut b = &base;
66            while let CalculationBase::Calc(inner) = b {
67                n += 1;
68                b = &inner.base;
69            }
70            n
71        };
72        // TODO: Maybe ignore include steps if size is too big (we can't respond properly anyway)
73        let mut steps = Vec::with_capacity(size);
74        let mut calcs = loop {
75            match base {
76                CalculationBase::Num(num) => {
77                    break vec![
78                        Self::calculate_appropriate_factorial(num.clone(), level, negative, consts)
79                            .map(|res| Calculation {
80                                value: num,
81                                steps: vec![(level, negative % 2 == 1)],
82                                result: res,
83                            }),
84                    ];
85                }
86                CalculationBase::Calc(calc) => {
87                    steps.push((level, negative));
88                    CalculationJob {
89                        base,
90                        level,
91                        negative,
92                    } = *calc;
93                }
94            }
95        };
96        for (i, (level, negative)) in steps.into_iter().rev().enumerate() {
97            let calc = if include_steps && i < 30 {
98                calcs.last().cloned()
99            } else {
100                calcs.pop()
101            };
102            match calc {
103                Some(Some(Calculation {
104                    result: res,
105                    mut steps,
106                    value: number,
107                })) => {
108                    let factorial = Self::calculate_appropriate_factorial(
109                        res, level, negative, consts,
110                    )
111                    .map(|res| {
112                        steps.push((level, negative % 2 == 1));
113                        Calculation {
114                            value: number,
115                            steps,
116                            result: res,
117                        }
118                    });
119                    calcs.push(factorial);
120                }
121                _ => return calcs,
122            };
123        }
124        calcs
125    }
126    fn calculate_appropriate_factorial(
127        num: Number,
128        level: i32,
129        negative: u32,
130        consts: &Consts,
131    ) -> Option<CalculationResult> {
132        let prec = consts.float_precision;
133        let calc_num = match num {
134            CalculationResult::Approximate(base, exponent) => {
135                let res = base.as_float() * Float::with_val(prec, 10).pow(&exponent);
136                if Float::is_finite(&(res.clone() * math::APPROX_FACT_SAFE_UPPER_BOUND_FACTOR)) {
137                    res.to_integer().unwrap()
138                } else {
139                    return Some(if base.as_float() < &0.0 {
140                        CalculationResult::ComplexInfinity
141                    } else if level < 0 {
142                        let termial = math::approximate_approx_termial(
143                            (Float::from(base), exponent),
144                            -level as u32,
145                        );
146                        CalculationResult::Approximate(termial.0.into(), termial.1)
147                    } else {
148                        let mut exponent = exponent;
149                        exponent.add_from(math::length(&exponent, prec));
150                        CalculationResult::ApproximateDigitsTower(false, false, 1.into(), exponent)
151                    });
152                }
153            }
154            CalculationResult::ApproximateDigits(was_neg, digits) => {
155                return Some(if digits.is_negative() {
156                    CalculationResult::Float(Float::new(prec).into())
157                } else if was_neg {
158                    CalculationResult::ComplexInfinity
159                } else if level < 0 {
160                    CalculationResult::ApproximateDigits(false, (digits - 1) * 2 + 1)
161                } else {
162                    let mut digits = digits;
163                    digits.add_from(math::length(&digits, prec));
164                    CalculationResult::ApproximateDigitsTower(false, false, 1.into(), digits)
165                });
166            }
167            CalculationResult::ApproximateDigitsTower(was_neg, neg, depth, exponent) => {
168                return Some(if neg {
169                    CalculationResult::Float(Float::new(prec).into())
170                } else if was_neg {
171                    CalculationResult::ComplexInfinity
172                } else if level < 0 {
173                    CalculationResult::ApproximateDigitsTower(false, false, depth, exponent)
174                } else {
175                    CalculationResult::ApproximateDigitsTower(false, false, depth + 1, exponent)
176                });
177            }
178            CalculationResult::ComplexInfinity => return Some(CalculationResult::ComplexInfinity),
179            Number::Float(num) => match level {
180                ..-1 => {
181                    // We don't support multitermials of decimals
182                    return None;
183                }
184                -1 => {
185                    let res: Float = math::fractional_termial(num.as_float().clone())
186                        * if negative % 2 != 0 { -1 } else { 1 };
187                    if res.is_finite() {
188                        return Some(CalculationResult::Float(res.into()));
189                    } else {
190                        num.as_float().to_integer()?
191                    }
192                }
193                0 => {
194                    // We don't support subfactorials of deciamals
195                    return None;
196                }
197                1 => {
198                    let res: Float = math::fractional_factorial(num.as_float().clone())
199                        * if negative % 2 != 0 { -1 } else { 1 };
200                    if res.is_finite() {
201                        return Some(CalculationResult::Float(res.into()));
202                    } else {
203                        num.as_float().to_integer()?
204                    }
205                }
206                2.. => {
207                    let res: Float =
208                        math::fractional_multifactorial(num.as_float().clone(), level as u32)
209                            * if negative % 2 != 0 { -1 } else { 1 };
210                    if res.is_finite() {
211                        return Some(CalculationResult::Float(res.into()));
212                    } else {
213                        num.as_float().to_integer()?
214                    }
215                }
216            },
217            Number::Exact(num) => num,
218        };
219        if level > 0 {
220            Some(if calc_num < 0 && level == 1 {
221                CalculationResult::ComplexInfinity
222            } else if calc_num < 0 {
223                let factor = math::negative_multifacorial_factor(calc_num.clone(), level);
224                match (factor, -level - 1 > calc_num) {
225                    (Some(factor), true) => {
226                        let mut res = Self::calculate_appropriate_factorial(
227                            Number::Exact(-calc_num.clone() - level),
228                            level,
229                            negative,
230                            consts,
231                        )?;
232                        res = match res {
233                            CalculationResult::Exact(n) => {
234                                let n = Float::with_val(prec, n);
235                                CalculationResult::Float((factor / n).into())
236                            }
237                            CalculationResult::Approximate(b, e) => {
238                                let (b, e) =
239                                    math::adjust_approximate((factor / Float::from(b), -e));
240                                CalculationResult::Approximate(b.into(), e)
241                            }
242                            CalculationResult::ApproximateDigits(wn, n) => {
243                                CalculationResult::ApproximateDigits(wn, -n)
244                            }
245                            CalculationResult::ApproximateDigitsTower(
246                                wn,
247                                negative,
248                                depth,
249                                base,
250                            ) => CalculationResult::ApproximateDigitsTower(
251                                wn, !negative, depth, base,
252                            ),
253                            CalculationResult::ComplexInfinity => {
254                                CalculationResult::Exact(0.into())
255                            }
256                            CalculationResult::Float(f) => {
257                                CalculationResult::Float((factor / Float::from(f)).into())
258                            }
259                        };
260
261                        res
262                    }
263                    (factor, _) => factor
264                        .map(CalculationResult::Exact)
265                        .unwrap_or(CalculationResult::ComplexInfinity),
266                }
267                // Check if we can approximate the number of digits
268            } else if calc_num > consts.upper_approximation_limit {
269                let factorial =
270                    math::approximate_multifactorial_digits(calc_num.clone(), level as u32, prec);
271                CalculationResult::ApproximateDigits(negative % 2 != 0, factorial)
272            // Check if the number is within a reasonable range to compute
273            } else if calc_num > consts.upper_calculation_limit {
274                let factorial = if level == 0 {
275                    math::approximate_factorial(calc_num.clone(), prec)
276                } else {
277                    math::approximate_multifactorial(calc_num.clone(), level as u32, prec)
278                };
279                CalculationResult::Approximate(
280                    ((factorial.0 * if negative % 2 != 0 { -1 } else { 1 }) as Float).into(),
281                    factorial.1,
282                )
283            } else {
284                let calc_num = calc_num.to_u64().expect("Failed to convert BigInt to u64");
285                let factorial = math::factorial(calc_num, level as u32)
286                    * if negative % 2 != 0 { -1 } else { 1 };
287                CalculationResult::Exact(factorial)
288            })
289        } else if level == 0 {
290            Some(if calc_num < 0 {
291                CalculationResult::ComplexInfinity
292            } else if calc_num > consts.upper_approximation_limit {
293                let factorial = math::approximate_multifactorial_digits(calc_num.clone(), 1, prec);
294                CalculationResult::ApproximateDigits(negative % 2 != 0, factorial)
295            } else if calc_num > consts.upper_subfactorial_limit {
296                let factorial = math::approximate_subfactorial(calc_num.clone(), prec);
297                CalculationResult::Approximate(
298                    ((factorial.0 * if negative % 2 != 0 { -1 } else { 1 }) as Float).into(),
299                    factorial.1,
300                )
301            } else {
302                let calc_num = calc_num.to_u64().expect("Failed to convert BigInt to u64");
303                let factorial =
304                    math::subfactorial(calc_num) * if negative % 2 != 0 { -1 } else { 1 };
305                CalculationResult::Exact(factorial)
306            })
307        } else if level < 0 {
308            Some(
309                if calc_num.significant_bits() > consts.upper_termial_approximation_limit {
310                    let termial = math::approximate_termial_digits(calc_num, -level as u32, prec);
311                    CalculationResult::ApproximateDigits(negative % 2 != 0, termial)
312                } else if calc_num > consts.upper_termial_limit {
313                    let termial = math::approximate_termial(calc_num, -level as u32, prec);
314                    CalculationResult::Approximate(
315                        ((termial.0 * if negative % 2 != 0 { -1 } else { 1 }) as Float).into(),
316                        termial.1,
317                    )
318                } else {
319                    let termial = if level < -1 {
320                        math::multitermial(calc_num, -level as u32)
321                    } else {
322                        math::termial(calc_num)
323                    };
324                    let termial = termial * if negative % 2 != 0 { -1 } else { 1 };
325                    CalculationResult::Exact(termial)
326                },
327            )
328        } else {
329            unreachable!()
330        }
331    }
332}
333
334#[cfg(test)]
335mod tests {
336    use super::*;
337    use factorion_math::recommended::FLOAT_PRECISION;
338
339    #[test]
340    fn test_unsupported_calcs() {
341        let consts = Consts::default();
342        // Subfactorial
343        let job = CalculationJob {
344            base: CalculationBase::Num(Number::Float(Float::with_val(FLOAT_PRECISION, 1.5).into())),
345            level: 0,
346            negative: 0,
347        };
348        assert_eq!(job.execute(false, &consts), vec![None]);
349        // Multitermial
350        let job = CalculationJob {
351            base: CalculationBase::Num(Number::Float(Float::with_val(FLOAT_PRECISION, 1.5).into())),
352            level: -2,
353            negative: 0,
354        };
355        assert_eq!(job.execute(false, &consts), vec![None]);
356        let job = CalculationJob {
357            base: CalculationBase::Num(Number::Float(Float::with_val(FLOAT_PRECISION, 1.5).into())),
358            level: -51,
359            negative: 0,
360        };
361        assert_eq!(job.execute(false, &consts), vec![None]);
362    }
363}
factorion_lib/calculation_tasks.rs

factorion_lib/
calculation_tasks.rs
