RootsOfUnity.java

  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.  *      http://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. package org.apache.commons.math3.complex;

  19. import java.io.Serializable;

  21. import org.apache.commons.math3.exception.MathIllegalArgumentException;
  22. import org.apache.commons.math3.exception.MathIllegalStateException;
  23. import org.apache.commons.math3.exception.OutOfRangeException;
  24. import org.apache.commons.math3.exception.ZeroException;
  25. import org.apache.commons.math3.exception.util.LocalizedFormats;
  26. import org.apache.commons.math3.util.FastMath;

  28. /**
  29.  * A helper class for the computation and caching of the {@code n}-th roots of
  30.  * unity.
  31.  *
  32.  * @since 3.0
  33.  */
  34. public class RootsOfUnity implements Serializable {

  36.     /** Serializable version id. */
  37.     private static final long serialVersionUID = 20120201L;

  39.     /** Number of roots of unity. */
  40.     private int omegaCount;

  42.     /** Real part of the roots. */
  43.     private double[] omegaReal;

  45.     /**
  46.      * Imaginary part of the {@code n}-th roots of unity, for positive values
  47.      * of {@code n}. In this array, the roots are stored in counter-clockwise
  48.      * order.
  49.      */
  50.     private double[] omegaImaginaryCounterClockwise;

  52.     /**
  53.      * Imaginary part of the {@code n}-th roots of unity, for negative values
  54.      * of {@code n}. In this array, the roots are stored in clockwise order.
  55.      */
  56.     private double[] omegaImaginaryClockwise;

  58.     /**
  59.      * {@code true} if {@link #computeRoots(int)} was called with a positive
  60.      * value of its argument {@code n}. In this case, counter-clockwise ordering
  61.      * of the roots of unity should be used.
  62.      */
  63.     private boolean isCounterClockWise;

  65.     /**
  66.      * Build an engine for computing the {@code n}-th roots of unity.
  67.      */
  68.     public RootsOfUnity() {

  70.         omegaCount = 0;
  71.         omegaReal = null;
  72.         omegaImaginaryCounterClockwise = null;
  73.         omegaImaginaryClockwise = null;
  74.         isCounterClockWise = true;
  75.     }

  77.     /**
  78.      * Returns {@code true} if {@link #computeRoots(int)} was called with a
  79.      * positive value of its argument {@code n}. If {@code true}, then
  80.      * counter-clockwise ordering of the roots of unity should be used.
  81.      *
  82.      * @return {@code true} if the roots of unity are stored in
  83.      * counter-clockwise order
  84.      * @throws MathIllegalStateException if no roots of unity have been computed
  85.      * yet
  86.      */
  87.     public synchronized boolean isCounterClockWise()
  88.             throws MathIllegalStateException {

  90.         if (omegaCount == 0) {
  91.             throw new MathIllegalStateException(
  92.                     LocalizedFormats.ROOTS_OF_UNITY_NOT_COMPUTED_YET);
  93.         }
  94.         return isCounterClockWise;
  95.     }

  97.     /**
  98.      * <p>
  99.      * Computes the {@code n}-th roots of unity. The roots are stored in
  100.      * {@code omega[]}, such that {@code omega[k] = w ^ k}, where
  101.      * {@code k = 0, ..., n - 1}, {@code w = exp(2 * pi * i / n)} and
  102.      * {@code i = sqrt(-1)}.
  103.      * </p>
  104.      * <p>
  105.      * Note that {@code n} can be positive of negative
  106.      * </p>
  107.      * <ul>
  108.      * <li>{@code abs(n)} is always the number of roots of unity.</li>
  109.      * <li>If {@code n > 0}, then the roots are stored in counter-clockwise order.</li>
  110.      * <li>If {@code n < 0}, then the roots are stored in clockwise order.</p>
  111.      * </ul>
  112.      *
  113.      * @param n the (signed) number of roots of unity to be computed
  114.      * @throws ZeroException if {@code n = 0}
  115.      */
  116.     public synchronized void computeRoots(int n) throws ZeroException {

  118.         if (n == 0) {
  119.             throw new ZeroException(
  120.                     LocalizedFormats.CANNOT_COMPUTE_0TH_ROOT_OF_UNITY);
  121.         }

  123.         isCounterClockWise = n > 0;

  125.         // avoid repetitive calculations
  126.         final int absN = FastMath.abs(n);

  128.         if (absN == omegaCount) {
  129.             return;
  130.         }

  132.         // calculate everything from scratch
  133.         final double t = 2.0 * FastMath.PI / absN;
  134.         final double cosT = FastMath.cos(t);
  135.         final double sinT = FastMath.sin(t);
  136.         omegaReal = new double[absN];
  137.         omegaImaginaryCounterClockwise = new double[absN];
  138.         omegaImaginaryClockwise = new double[absN];
  139.         omegaReal[0] = 1.0;
  140.         omegaImaginaryCounterClockwise[0] = 0.0;
  141.         omegaImaginaryClockwise[0] = 0.0;
  142.         for (int i = 1; i < absN; i++) {
  143.             omegaReal[i] = omegaReal[i - 1] * cosT -
  144.                     omegaImaginaryCounterClockwise[i - 1] * sinT;
  145.             omegaImaginaryCounterClockwise[i] = omegaReal[i - 1] * sinT +
  146.                     omegaImaginaryCounterClockwise[i - 1] * cosT;
  147.             omegaImaginaryClockwise[i] = -omegaImaginaryCounterClockwise[i];
  148.         }
  149.         omegaCount = absN;
  150.     }

  152.     /**
  153.      * Get the real part of the {@code k}-th {@code n}-th root of unity.
  154.      *
  155.      * @param k index of the {@code n}-th root of unity
  156.      * @return real part of the {@code k}-th {@code n}-th root of unity
  157.      * @throws MathIllegalStateException if no roots of unity have been
  158.      * computed yet
  159.      * @throws MathIllegalArgumentException if {@code k} is out of range
  160.      */
  161.     public synchronized double getReal(int k)
  162.             throws MathIllegalStateException, MathIllegalArgumentException {

  164.         if (omegaCount == 0) {
  165.             throw new MathIllegalStateException(
  166.                     LocalizedFormats.ROOTS_OF_UNITY_NOT_COMPUTED_YET);
  167.         }
  168.         if ((k < 0) || (k >= omegaCount)) {
  169.             throw new OutOfRangeException(
  170.                     LocalizedFormats.OUT_OF_RANGE_ROOT_OF_UNITY_INDEX,
  171.                     Integer.valueOf(k),
  172.                     Integer.valueOf(0),
  173.                     Integer.valueOf(omegaCount - 1));
  174.         }

  176.         return omegaReal[k];
  177.     }

  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
  185.      * computed yet
  186.      * @throws OutOfRangeException if {@code k} is out of range
  187.      */
  188.     public synchronized double getImaginary(int k)
  189.             throws MathIllegalStateException, OutOfRangeException {

  191.         if (omegaCount == 0) {
  192.             throw new MathIllegalStateException(
  193.                     LocalizedFormats.ROOTS_OF_UNITY_NOT_COMPUTED_YET);
  194.         }
  195.         if ((k < 0) || (k >= omegaCount)) {
  196.             throw new OutOfRangeException(
  197.                     LocalizedFormats.OUT_OF_RANGE_ROOT_OF_UNITY_INDEX,
  198.                     Integer.valueOf(k),
  199.                     Integer.valueOf(0),
  200.                     Integer.valueOf(omegaCount - 1));
  201.         }

  203.         return isCounterClockWise ? omegaImaginaryCounterClockwise[k] :
  204.             omegaImaginaryClockwise[k];
  205.     }

  207.     /**
  208.      * Returns the number of roots of unity currently stored. If
  209.      * {@link #computeRoots(int)} was called with {@code n}, then this method
  210.      * returns {@code abs(n)}. If no roots of unity have been computed yet, this
  211.      * method returns 0.
  212.      *
  213.      * @return the number of roots of unity currently stored
  214.      */
  215.     public synchronized int getNumberOfRoots() {
  216.         return omegaCount;
  217.     }
  218. }
Created with JaCoCo 0.7.2.201409121644