Class SixStepFNTStrategy

java.lang.Object
org.apfloat.internal.AbstractStepFNTStrategy
org.apfloat.internal.SixStepFNTStrategy
All Implemented Interfaces:
Parallelizable, NTTStrategy
Direct Known Subclasses:
ColumnSixStepFNTStrategy

public class SixStepFNTStrategy extends AbstractStepFNTStrategy
Fast Number Theoretic Transform that uses a "six-step" algorithm to calculate a long transform more efficiently on cache-based memory architectures.

When the data to be transformed is considered to be an n1 x n2 matrix of data, instead of a linear array, the six steps are as follows:

  1. Transpose the matrix.
  2. Transform the rows.
  3. Transpose the matrix.
  4. Multiply each matrix element by wi j (where w is the n:th root of unity).
  5. Transform the rows.
  6. Transpose the matrix.

In a convolution algorithm the last transposition step can be omitted to increase performance, as well as the first transposition step in the inverse transform. The convolution's element-by-element multiplication is not sensitive to the order in which the elements are. Also scrambling the data can be omitted.

All access to this class must be externally synchronized.

Since:
1.7.0
Version:
1.9.0
Author:
Mikko Tommila
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected MatrixStrategy
    The matrix strategy.

    Fields inherited from class org.apfloat.internal.AbstractStepFNTStrategy

    stepStrategy
  • Constructor Summary

    Constructors
    Constructor
    Description
    Default constructor.
  • Method Summary

    Modifier and Type
    Method
    Description
    protected void
    inverseTransform​(DataStorage dataStorage, int n1, int n2, long length, long totalTransformLength, int modulus)
    Inverse transform the data in steps.
    protected void
    multiplyElements​(ArrayAccess arrayAccess, int rows, int columns, long length, long totalTransformLength, boolean isInverse, int modulus)
    Multiply each matrix element by a power of the n:th root of unity.
    protected void
    postTransform​(ArrayAccess arrayAccess)
    Finish processing the data after the (inverse) transform.
    protected void
    preTransform​(ArrayAccess arrayAccess)
    Prepare the data for the (inverse) transform.
    protected void
    transform​(DataStorage dataStorage, int n1, int n2, long length, int modulus)
    Transform the data in steps.
    protected void
    transformFirst​(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)
    The first transform of the rows (or columns) of the data matrix.
    protected void
    transformSecond​(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)
    The second transform of the rows (or columns) of the data matrix.
    protected void
    transposeFinal​(ArrayAccess arrayAccess, int n1, int n2, boolean isInverse)
    The final transpose of the forward transform, or the initial transpose of the inverse transform.
    protected void
    transposeInitial​(ArrayAccess arrayAccess, int n1, int n2, boolean isInverse)
    The initial transpose of the forward transform, or the final transpose of the inverse transform, to transpose the columns of the matrix to be rows.
    protected void
    transposeMiddle​(ArrayAccess arrayAccess, int n1, int n2, boolean isInverse)
    The second transpose of either the forward or inverse transform.

    Methods inherited from class org.apfloat.internal.AbstractStepFNTStrategy

    getTransformLength, inverseTransform, transform

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • matrixStrategy

      protected MatrixStrategy matrixStrategy
      The matrix strategy.
  • Constructor Details

    • SixStepFNTStrategy

      public SixStepFNTStrategy()
      Default constructor.
  • Method Details

    • transform

      protected void transform(DataStorage dataStorage, int n1, int n2, long length, int modulus) throws ApfloatRuntimeException
      Description copied from class: AbstractStepFNTStrategy
      Transform the data in steps.
      Specified by:
      transform in class AbstractStepFNTStrategy
      Parameters:
      dataStorage - The data.
      n1 - Height of the data matrix.
      n2 - Width of the data matrix.
      length - Length of the data.
      modulus - Which modulus to use.
      Throws:
      ApfloatRuntimeException
    • inverseTransform

      protected void inverseTransform(DataStorage dataStorage, int n1, int n2, long length, long totalTransformLength, int modulus) throws ApfloatRuntimeException
      Description copied from class: AbstractStepFNTStrategy
      Inverse transform the data in steps.
      Specified by:
      inverseTransform in class AbstractStepFNTStrategy
      Parameters:
      dataStorage - The data.
      n1 - Height of the data matrix.
      n2 - Width of the data matrix.
      length - Length of the data.
      totalTransformLength - Total transform length.
      modulus - Which modulus to use.
      Throws:
      ApfloatRuntimeException
    • preTransform

      protected void preTransform(ArrayAccess arrayAccess)
      Prepare the data for the (inverse) transform.
      Parameters:
      arrayAccess - The data to prepare.
    • transposeInitial

      protected void transposeInitial(ArrayAccess arrayAccess, int n1, int n2, boolean isInverse)
      The initial transpose of the forward transform, or the final transpose of the inverse transform, to transpose the columns of the matrix to be rows. This step is needed in the six-step algorithm but is omitted in the four-step algorithm.
      Parameters:
      arrayAccess - Accessor to the matrix data. This data will be transposed.
      n1 - Number of rows in the matrix.
      n2 - Number of columns in the matrix.
      isInverse - true if an inverse transform is performed, false if a forward transform is performed.
    • transposeMiddle

      protected void transposeMiddle(ArrayAccess arrayAccess, int n1, int n2, boolean isInverse)
      The second transpose of either the forward or inverse transform. Normally this step is always required as the four-step algorithm only transforms columns of the matrix and the six-step algorithm transforms only rows.
      Parameters:
      arrayAccess - Accessor to the matrix data. This data will be transposed.
      n1 - Number of rows in the matrix.
      n2 - Number of columns in the matrix.
      isInverse - true if an inverse transform is performed, false if a forward transform is performed.
    • transposeFinal

      protected void transposeFinal(ArrayAccess arrayAccess, int n1, int n2, boolean isInverse)
      The final transpose of the forward transform, or the initial transpose of the inverse transform. By default this method does nothing as the step is always unnecessary when the data is only needed for convolution.
      Parameters:
      arrayAccess - Accessor to the matrix data.
      n1 - Number of rows in the matrix.
      n2 - Number of columns in the matrix.
      isInverse - true if an inverse transform is performed, false if a forward transform is performed.
    • transformFirst

      protected void transformFirst(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)
      The first transform of the rows (or columns) of the data matrix. In the default implementation the rows are transformed because in the forward transform the matrix is transposed first. In the inverse transform the matrix is initially in transposed form as it was left like that by the forward transform.

      By default the row transforms permute the data, leaving it in the correct order so the element-by-element multiplication is simpler.

      Parameters:
      arrayAccess - The memory array to split and transform.
      length - Length of one transform (one row physically, by default).
      count - Number of transforms.
      isInverse - true if an inverse transform is performed, false if a forward transform is performed.
      modulus - Index of the modulus.
    • transformSecond

      protected void transformSecond(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)
      The second transform of the rows (or columns) of the data matrix. In the default implementation the rows are transformed because in the forward transform the matrix is transposed first. In the inverse transform the matrix is initially in transposed form as it was left like that by the forward transform.

      By default the row transforms do not permute the data, leaving it in scrambled order, as this does not matter when the data is only used for convolution.

      Parameters:
      arrayAccess - The memory array to split to rows and to transform.
      length - Length of one transform (one row).
      count - Number of rows.
      isInverse - true if an inverse transform is performed, false if a forward transform is performed.
      modulus - Index of the modulus.
    • multiplyElements

      protected void multiplyElements(ArrayAccess arrayAccess, int rows, int columns, long length, long totalTransformLength, boolean isInverse, int modulus)
      Multiply each matrix element by a power of the n:th root of unity.
      Parameters:
      arrayAccess - The memory array to multiply.
      rows - The number of rows in the arrayAccess to multiply.
      columns - The number of columns in the matrix (= n2).
      length - The length of data in the matrix being transformed.
      totalTransformLength - The total transform length, for the scaling factor. Used only for the inverse case.
      isInverse - If the multiplication is done for the inverse transform or not.
      modulus - Index of the modulus.
    • postTransform

      protected void postTransform(ArrayAccess arrayAccess)
      Finish processing the data after the (inverse) transform.
      Parameters:
      arrayAccess - The data to finish.