malachite_nz/integer/arithmetic/
rising_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//
9// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
10// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
11// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
12
13use crate::integer::Integer;
14use crate::natural::Natural;
15use malachite_base::num::arithmetic::traits::{Parity, RisingFactorial};
16use malachite_base::num::basic::traits::{One, Zero};
17
18// This is fmpz_rfac_ui from fmpz/rfac.c, FLINT 3.6.0. A negative base either spans zero, giving
19// zero, or contributes an all-negative factor sequence: its magnitude is the rising factorial of
20// the negated top factor, and its sign is the parity of the number of factors.
21fn rising_factorial_helper(x: &Integer, n: u64) -> Integer {
22    if n == 0 {
23        Integer::ONE
24    } else if n == 1 {
25        x.clone()
26    } else if *x == 0u32 {
27        Integer::ZERO
28    } else if *x < 0u32 {
29        let abs = x.unsigned_abs_ref();
30        if *abs < n {
31            Integer::ZERO
32        } else {
33            let magnitude = (abs - Natural::from(n - 1)).rising_factorial(n);
34            Integer::from_sign_and_abs(n.even(), magnitude)
35        }
36    } else {
37        Integer::from(x.unsigned_abs_ref().rising_factorial(n))
38    }
39}
40
41impl RisingFactorial for Integer {
42    type Output = Self;
43
44    /// Computes the rising factorial of an [`Integer`]: the product of the `n` consecutive numbers
45    /// starting at `self`, or 1 when `n` is 0. The [`Integer`] is taken by value.
46    ///
47    /// A negative base whose factor sequence reaches or crosses zero gives exactly zero; otherwise
48    /// all factors are negative, and the sign of the product is determined by the parity of `n`.
49    ///
50    /// $$
51    /// f(x, n) = x^{(n)} = x (x + 1) \cdots (x + n - 1).
52    /// $$
53    ///
54    /// # Worst-case complexity
55    /// $T(m) = O(m (\log m)^2 \log\log m)$
56    ///
57    /// $M(m) = O(m \log m)$
58    ///
59    /// where $T$ is time, $M$ is additional memory, and $m$ is the number of significant bits of
60    /// the result.
61    ///
62    /// # Examples
63    /// ```
64    /// use malachite_base::num::arithmetic::traits::RisingFactorial;
65    /// use malachite_nz::integer::Integer;
66    ///
67    /// assert_eq!(Integer::from(3).rising_factorial(4), 360);
68    /// assert_eq!(Integer::from(-5).rising_factorial(3), -60);
69    /// assert_eq!(Integer::from(-2).rising_factorial(5), 0);
70    /// ```
71    ///
72    /// This is fmpz_rfac_ui from fmpz/rfac.c, FLINT 3.6.0.
73    #[inline]
74    fn rising_factorial(self, n: u64) -> Self {
75        rising_factorial_helper(&self, n)
76    }
77}
78
79impl RisingFactorial for &Integer {
80    type Output = Integer;
81
82    /// Computes the rising factorial of an [`Integer`]: the product of the `n` consecutive numbers
83    /// starting at `self`, or 1 when `n` is 0. The [`Integer`] is taken by reference.
84    ///
85    /// A negative base whose factor sequence reaches or crosses zero gives exactly zero; otherwise
86    /// all factors are negative, and the sign of the product is determined by the parity of `n`.
87    ///
88    /// $$
89    /// f(x, n) = x^{(n)} = x (x + 1) \cdots (x + n - 1).
90    /// $$
91    ///
92    /// # Worst-case complexity
93    /// $T(m) = O(m (\log m)^2 \log\log m)$
94    ///
95    /// $M(m) = O(m \log m)$
96    ///
97    /// where $T$ is time, $M$ is additional memory, and $m$ is the number of significant bits of
98    /// the result.
99    ///
100    /// # Examples
101    /// ```
102    /// use malachite_base::num::arithmetic::traits::RisingFactorial;
103    /// use malachite_nz::integer::Integer;
104    ///
105    /// assert_eq!((&Integer::from(3)).rising_factorial(4), 360);
106    /// assert_eq!((&Integer::from(-5)).rising_factorial(3), -60);
107    /// assert_eq!((&Integer::from(-2)).rising_factorial(5), 0);
108    /// ```
109    ///
110    /// This is fmpz_rfac_ui from fmpz/rfac.c, FLINT 3.6.0.
111    #[inline]
112    fn rising_factorial(self, n: u64) -> Integer {
113        rising_factorial_helper(self, n)
114    }
115}
malachite_nz/integer/arithmetic/rising_factorial.rs

malachite_nz/integer/arithmetic/
rising_factorial.rs
