View Javadoc
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 }