malachite_nz/integer/arithmetic/
falling_factorial.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// Uses code adopted from the FLINT Library.
4//
5//      Copyright © 2011 Fredrik Johansson
6//
7// This file is part of Malachite.
8
9use crate::integer::Integer;
10use malachite_base::num::arithmetic::traits::{FallingFactorial, RisingFactorial};
11use malachite_base::num::basic::traits::One;
12
13impl FallingFactorial for Integer {
14    type Output = Self;
15
16    /// Computes the falling factorial of an [`Integer`]: the product of the `n` consecutive numbers
17    /// counting down from `self`, or 1 when `n` is 0. The [`Integer`] is taken by value.
18    ///
19    /// $$
20    /// f(x, n) = x^{\underline{n}} = x (x - 1) \cdots (x - n + 1).
21    /// $$
22    ///
23    /// The falling factorial is the rising factorial of $x - n + 1$, which is how it is computed.
24    /// When the factors span 0, the result is 0, and when they are all negative, its sign is that
25    /// of $(-1)^n$.
26    ///
27    /// # Worst-case complexity
28    /// $T(m) = O(m (\log m)^2 \log\log m)$
29    ///
30    /// $M(m) = O(m \log m)$
31    ///
32    /// where $T$ is time, $M$ is additional memory, and $m$ is the number of significant bits of
33    /// the result.
34    ///
35    /// # Examples
36    /// ```
37    /// use malachite_base::num::arithmetic::traits::FallingFactorial;
38    /// use malachite_nz::integer::Integer;
39    ///
40    /// assert_eq!(Integer::from(6).falling_factorial(4), 360);
41    /// // The factors span 0.
42    /// assert_eq!(Integer::from(3).falling_factorial(5), 0);
43    /// // The factors are all negative: (-2)(-3)(-4) = -24.
44    /// assert_eq!(Integer::from(-2).falling_factorial(3), -24);
45    /// assert_eq!(Integer::from(-10).falling_factorial(0), 1);
46    /// ```
47    ///
48    /// FLINT has no `fmpz` falling factorial; this is `gr_falling_ui` from `gr_special/bin.c`,
49    /// FLINT 3.6.0, in the ring of integers, which also reduces to the rising factorial.
50    fn falling_factorial(mut self, n: u64) -> Self {
51        if n == 0 {
52            Self::ONE
53        } else {
54            self -= Self::from(n - 1);
55            self.rising_factorial(n)
56        }
57    }
58}
59
60impl FallingFactorial for &Integer {
61    type Output = Integer;
62
63    /// Computes the falling factorial of an [`Integer`]: the product of the `n` consecutive numbers
64    /// counting down from `self`, or 1 when `n` is 0. The [`Integer`] is taken by reference.
65    ///
66    /// $$
67    /// f(x, n) = x^{\underline{n}} = x (x - 1) \cdots (x - n + 1).
68    /// $$
69    ///
70    /// The falling factorial is the rising factorial of $x - n + 1$, which is how it is computed.
71    /// When the factors span 0, the result is 0, and when they are all negative, its sign is that
72    /// of $(-1)^n$.
73    ///
74    /// # Worst-case complexity
75    /// $T(m) = O(m (\log m)^2 \log\log m)$
76    ///
77    /// $M(m) = O(m \log m)$
78    ///
79    /// where $T$ is time, $M$ is additional memory, and $m$ is the number of significant bits of
80    /// the result.
81    ///
82    /// # Examples
83    /// ```
84    /// use malachite_base::num::arithmetic::traits::FallingFactorial;
85    /// use malachite_nz::integer::Integer;
86    ///
87    /// assert_eq!((&Integer::from(6)).falling_factorial(4), 360);
88    /// // The factors span 0.
89    /// assert_eq!((&Integer::from(3)).falling_factorial(5), 0);
90    /// // The factors are all negative: (-2)(-3)(-4) = -24.
91    /// assert_eq!((&Integer::from(-2)).falling_factorial(3), -24);
92    /// assert_eq!((&Integer::from(-10)).falling_factorial(0), 1);
93    /// ```
94    ///
95    /// FLINT has no `fmpz` falling factorial; this is `gr_falling_ui` from `gr_special/bin.c`,
96    /// FLINT 3.6.0, in the ring of integers, which also reduces to the rising factorial.
97    fn falling_factorial(self, n: u64) -> Integer {
98        if n == 0 {
99            Integer::ONE
100        } else {
101            (self - Integer::from(n - 1)).rising_factorial(n)
102        }
103    }
104}
malachite_nz/integer/arithmetic/falling_factorial.rs

malachite_nz/integer/arithmetic/
falling_factorial.rs
