1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.complex;
23
24 import java.io.Serializable;
25
26 import org.hipparchus.exception.LocalizedCoreFormats;
27 import org.hipparchus.exception.MathIllegalArgumentException;
28 import org.hipparchus.exception.MathIllegalStateException;
29 import org.hipparchus.util.FastMath;
30 import org.hipparchus.util.SinCos;
31
32 /**
33 * A helper class for the computation and caching of the {@code n}-th roots
34 * of unity.
35 */
36 public class RootsOfUnity implements Serializable {
37
38 /** Serializable version id. */
39 private static final long serialVersionUID = 20120201L;
40
41 /** Number of roots of unity. */
42 private int omegaCount;
43
44 /** Real part of the roots. */
45 private double[] omegaReal;
46
47 /**
48 * Imaginary part of the {@code n}-th roots of unity, for positive values
49 * of {@code n}. In this array, the roots are stored in counter-clockwise
50 * order.
51 */
52 private double[] omegaImaginaryCounterClockwise;
53
54 /**
55 * Imaginary part of the {@code n}-th roots of unity, for negative values
56 * of {@code n}. In this array, the roots are stored in clockwise order.
57 */
58 private double[] omegaImaginaryClockwise;
59
60 /**
61 * {@code true} if {@link #computeRoots(int)} was called with a positive
62 * value of its argument {@code n}. In this case, counter-clockwise ordering
63 * of the roots of unity should be used.
64 */
65 private boolean isCounterClockWise;
66
67 /**
68 * Build an engine for computing the {@code n}-th roots of unity.
69 */
70 public RootsOfUnity() {
71 omegaCount = 0;
72 omegaReal = null;
73 omegaImaginaryCounterClockwise = null;
74 omegaImaginaryClockwise = null;
75 isCounterClockWise = true;
76 }
77
78 /**
79 * Returns {@code true} if {@link #computeRoots(int)} was called with a
80 * positive value of its argument {@code n}. If {@code true}, then
81 * counter-clockwise ordering of the roots of unity should be used.
82 *
83 * @return {@code true} if the roots of unity are stored in counter-clockwise order
84 * @throws MathIllegalStateException if no roots of unity have been computed yet
85 */
86 public boolean isCounterClockWise()
87 throws MathIllegalStateException {
88 synchronized (this) {
89 if (omegaCount == 0) {
90 throw new MathIllegalStateException(
91 LocalizedCoreFormats.ROOTS_OF_UNITY_NOT_COMPUTED_YET);
92 }
93 return isCounterClockWise;
94 }
95 }
96
97 /**
98 * Computes the {@code n}-th roots of unity.
99 * <p>
100 * The roots are stored in {@code omega[]}, such that {@code omega[k] = w ^ k},
101 * where {@code k = 0, ..., n - 1}, {@code w = exp(2 * pi * i / n)} and
102 * {@code i = sqrt(-1)}.
103 * <p>
104 * Note that {@code n} can be positive of negative
105 * <ul>
106 * <li>{@code abs(n)} is always the number of roots of unity.</li>
107 * <li>If {@code n > 0}, then the roots are stored in counter-clockwise order.</li>
108 * <li>If {@code n < 0}, then the roots are stored in clockwise order.</li>
109 * </ul>
110 *
111 * @param n the (signed) number of roots of unity to be computed
112 * @throws MathIllegalArgumentException if {@code n = 0}
113 */
114 public void computeRoots(int n) throws MathIllegalArgumentException {
115
116 if (n == 0) {
117 throw new MathIllegalArgumentException(
118 LocalizedCoreFormats.CANNOT_COMPUTE_0TH_ROOT_OF_UNITY);
119 }
120
121 synchronized (this) {
122 isCounterClockWise = n > 0;
123
124 // avoid repetitive calculations
125 final int absN = FastMath.abs(n);
126
127 if (absN == omegaCount) {
128 return;
129 }
130
131 // calculate everything from scratch
132 final double t = 2.0 * FastMath.PI / absN;
133 final SinCos sc = FastMath.sinCos(t);
134 omegaReal = new double[absN];
135 omegaImaginaryCounterClockwise = new double[absN];
136 omegaImaginaryClockwise = new double[absN];
137 omegaReal[0] = 1.0;
138 omegaImaginaryCounterClockwise[0] = 0.0;
139 omegaImaginaryClockwise[0] = 0.0;
140 for (int i = 1; i < absN; i++) {
141 omegaReal[i] = omegaReal[i - 1] * sc.cos() -
142 omegaImaginaryCounterClockwise[i - 1] * sc.sin();
143 omegaImaginaryCounterClockwise[i] = omegaReal[i - 1] * sc.sin() +
144 omegaImaginaryCounterClockwise[i - 1] * sc.cos();
145 omegaImaginaryClockwise[i] = -omegaImaginaryCounterClockwise[i];
146 }
147 omegaCount = absN;
148 }
149 }
150
151 /**
152 * Get the real part of the {@code k}-th {@code n}-th root of unity.
153 *
154 * @param k index of the {@code n}-th root of unity
155 * @return real part of the {@code k}-th {@code n}-th root of unity
156 * @throws MathIllegalStateException if no roots of unity have been computed yet
157 * @throws MathIllegalArgumentException if {@code k} is out of range
158 */
159 public double getReal(int k)
160 throws MathIllegalArgumentException, MathIllegalStateException {
161
162 synchronized (this) {
163 if (omegaCount == 0) {
164 throw new MathIllegalStateException(
165 LocalizedCoreFormats.ROOTS_OF_UNITY_NOT_COMPUTED_YET);
166 }
167 if ((k < 0) || (k >= omegaCount)) {
168 throw new MathIllegalArgumentException(
169 LocalizedCoreFormats.OUT_OF_RANGE_ROOT_OF_UNITY_INDEX,
170 Integer.valueOf(k),
171 Integer.valueOf(0),
172 Integer.valueOf(omegaCount - 1));
173 }
174
175 return omegaReal[k];
176 }
177 }
178
179 /**
180 * Get the imaginary part of the {@code k}-th {@code n}-th root of unity.
181 *
182 * @param k index of the {@code n}-th root of unity
183 * @return imaginary part of the {@code k}-th {@code n}-th root of unity
184 * @throws MathIllegalStateException if no roots of unity have been computed yet
185 * @throws MathIllegalArgumentException if {@code k} is out of range
186 */
187 public double getImaginary(int k)
188 throws MathIllegalArgumentException, MathIllegalStateException {
189
190 synchronized (this) {
191 if (omegaCount == 0) {
192 throw new MathIllegalStateException(
193 LocalizedCoreFormats.ROOTS_OF_UNITY_NOT_COMPUTED_YET);
194 }
195 if ((k < 0) || (k >= omegaCount)) {
196 throw new MathIllegalArgumentException(
197 LocalizedCoreFormats.OUT_OF_RANGE_ROOT_OF_UNITY_INDEX,
198 Integer.valueOf(k),
199 Integer.valueOf(0),
200 Integer.valueOf(omegaCount - 1));
201 }
202
203 return isCounterClockWise ? omegaImaginaryCounterClockwise[k] :
204 omegaImaginaryClockwise[k];
205 }
206 }
207
208 /**
209 * Returns the number of roots of unity currently stored.
210 * <p>
211 * If {@link #computeRoots(int)} was called with {@code n}, then this method
212 * returns {@code abs(n)}. If no roots of unity have been computed yet, this
213 * method returns 0.
214 *
215 * @return the number of roots of unity currently stored
216 */
217 public int getNumberOfRoots() {
218 synchronized (this) {
219 return omegaCount;
220 }
221 }
222 }