factorion_lib/
calculation_tasks.rs

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

factorion_lib/
calculation_tasks.rs
