malachite_nz/gaussian_integer/arithmetic/pow.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// Uses code adopted from the FLINT Library.
4//
5// Copyright © 2022 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::gaussian_integer::GaussianInteger;
14use core::mem::take;
15use malachite_base::num::arithmetic::traits::{MulIPow, Pow, PowAssign, Square, SquareAssign};
16use malachite_base::num::basic::traits::One;
17use malachite_base::num::logic::traits::{BitAccess, SignificantBits};
18
19// A port of `fmpzi_pow_ui`: a purely real or purely imaginary base is a real power times a unit,
20// and anything else is binary exponentiation, which squares once per bit of the exponent and
21// multiplies by the base once per set bit. The by-value and by-reference helpers differ only in
22// what they consume; the general case needs the base throughout, so both borrow it there.
23
24// The base has two nonzero parts and `exp` is at least 3. Starting from the square rather than from
25// a copy of the base saves a clone.
26fn pow_general(x: &GaussianInteger, exp: u64) -> GaussianInteger {
27 let bits = exp.significant_bits();
28 let mut power = x.square();
29 if exp.get_bit(bits - 2) {
30 power *= x;
31 }
32 for i in (0..bits - 2).rev() {
33 power.square_assign();
34 if exp.get_bit(i) {
35 power *= x;
36 }
37 }
38 power
39}
40
41fn pow_val(x: GaussianInteger, exp: u64) -> GaussianInteger {
42 match exp {
43 0 => GaussianInteger::ONE,
44 1 => x,
45 2 => x.square(),
46 _ if x.imaginary == 0u32 => GaussianInteger::from(x.real.pow(exp)),
47 // (bi)^n = b^n i^n
48 _ if x.real == 0u32 => GaussianInteger::from(x.imaginary.pow(exp)).mul_i_pow(exp),
49 _ => pow_general(&x, exp),
50 }
51}
52
53fn pow_ref(x: &GaussianInteger, exp: u64) -> GaussianInteger {
54 match exp {
55 0 => GaussianInteger::ONE,
56 1 => x.clone(),
57 2 => x.square(),
58 _ if x.imaginary == 0u32 => GaussianInteger::from((&x.real).pow(exp)),
59 // (bi)^n = b^n i^n
60 _ if x.real == 0u32 => GaussianInteger::from((&x.imaginary).pow(exp)).mul_i_pow(exp),
61 _ => pow_general(x, exp),
62 }
63}
64
65impl Pow<u64> for GaussianInteger {
66 type Output = Self;
67
68 /// Raises a [`GaussianInteger`] to a power, taking the [`GaussianInteger`] by value.
69 ///
70 /// $f(x, n) = x^n$.
71 ///
72 /// # Worst-case complexity
73 /// $T(n, m) = O(nm \log (nm) \log\log (nm))$
74 ///
75 /// $M(n, m) = O(nm \log (nm))$
76 ///
77 /// where $T$ is time, $M$ is additional memory, $n$ is the maximum number of significant bits
78 /// of the real and imaginary parts of `self`, and $m$ is `exp`.
79 ///
80 /// # Examples
81 /// ```
82 /// use malachite_base::num::arithmetic::traits::Pow;
83 /// use malachite_nz::gaussian_integer::GaussianInteger;
84 /// use std::str::FromStr;
85 ///
86 /// assert_eq!(
87 /// GaussianInteger::from_str("2+i").unwrap().pow(5).to_string(),
88 /// "-38+41i"
89 /// );
90 /// assert_eq!(
91 /// GaussianInteger::from_str("1+i")
92 /// .unwrap()
93 /// .pow(10)
94 /// .to_string(),
95 /// "32i"
96 /// );
97 /// assert_eq!(
98 /// GaussianInteger::from_str("-7+24i")
99 /// .unwrap()
100 /// .pow(4)
101 /// .to_string(),
102 /// "164833+354144i"
103 /// );
104 /// ```
105 #[inline]
106 fn pow(self, exp: u64) -> Self {
107 pow_val(self, exp)
108 }
109}
110
111impl Pow<u64> for &GaussianInteger {
112 type Output = GaussianInteger;
113
114 /// Raises a [`GaussianInteger`] to a power, taking the [`GaussianInteger`] by reference.
115 ///
116 /// $f(x, n) = x^n$.
117 ///
118 /// # Worst-case complexity
119 /// $T(n, m) = O(nm \log (nm) \log\log (nm))$
120 ///
121 /// $M(n, m) = O(nm \log (nm))$
122 ///
123 /// where $T$ is time, $M$ is additional memory, $n$ is the maximum number of significant bits
124 /// of the real and imaginary parts of `self`, and $m$ is `exp`.
125 ///
126 /// # Examples
127 /// ```
128 /// use malachite_base::num::arithmetic::traits::Pow;
129 /// use malachite_nz::gaussian_integer::GaussianInteger;
130 /// use std::str::FromStr;
131 ///
132 /// assert_eq!(
133 /// (&GaussianInteger::from_str("2+i").unwrap())
134 /// .pow(5)
135 /// .to_string(),
136 /// "-38+41i"
137 /// );
138 /// assert_eq!(
139 /// (&GaussianInteger::from_str("1+i").unwrap())
140 /// .pow(10)
141 /// .to_string(),
142 /// "32i"
143 /// );
144 /// assert_eq!(
145 /// (&GaussianInteger::from_str("-7+24i").unwrap())
146 /// .pow(4)
147 /// .to_string(),
148 /// "164833+354144i"
149 /// );
150 /// ```
151 #[inline]
152 fn pow(self, exp: u64) -> GaussianInteger {
153 pow_ref(self, exp)
154 }
155}
156
157impl PowAssign<u64> for GaussianInteger {
158 /// Raises a [`GaussianInteger`] to a power in place.
159 ///
160 /// $x \gets x^n$.
161 ///
162 /// # Worst-case complexity
163 /// $T(n, m) = O(nm \log (nm) \log\log (nm))$
164 ///
165 /// $M(n, m) = O(nm \log (nm))$
166 ///
167 /// where $T$ is time, $M$ is additional memory, $n$ is the maximum number of significant bits
168 /// of the real and imaginary parts of `self`, and $m$ is `exp`.
169 ///
170 /// # Examples
171 /// ```
172 /// use malachite_base::num::arithmetic::traits::PowAssign;
173 /// use malachite_nz::gaussian_integer::GaussianInteger;
174 /// use std::str::FromStr;
175 ///
176 /// let mut x = GaussianInteger::from_str("2+i").unwrap();
177 /// x.pow_assign(5);
178 /// assert_eq!(x.to_string(), "-38+41i");
179 ///
180 /// let mut x = GaussianInteger::from_str("1+i").unwrap();
181 /// x.pow_assign(10);
182 /// assert_eq!(x.to_string(), "32i");
183 /// ```
184 #[inline]
185 fn pow_assign(&mut self, exp: u64) {
186 *self = pow_val(take(self), exp);
187 }
188}