# Class TwoPassFNTStrategy

java.lang.Object
org.apfloat.internal.AbstractStepFNTStrategy
org.apfloat.internal.TwoPassFNTStrategy

All Implemented Interfaces:
  `DecorableNTTStrategy, Parallelizable, NTTStrategy`

Direct Known Subclasses:
  `ColumnTwoPassFNTStrategy, IntAparapiTwoPassFNTStrategy, LongAparapiTwoPassFNTStrategy`

public class TwoPassFNTStrategy extends AbstractStepFNTStrategy implements DecorableNTTStrategy
Fast Number Theoretic Transform that uses a "two-pass" algorithm to calculate a very long transform on data that resides on a mass storage device. The storage medium should preferably be a solid state disk for good performance; on normal hard disks performance is usually inadequate.

The "two-pass" algorithm only needs to do two passes through the data set. In comparison, a basic FFT algorithm of length 2n needs to do n passes through the data set. Although the algorithm is fairly optimal in terms of amount of data transferred between the mass storage and main memory, the mass storage access is not linear but done in small incontinuous pieces, so due to disk seek times the performance can be quite lousy.

When the data to be transformed is considered to be an n1 x n2 matrix of data, instead of a linear array, the two passes go as follows:

1. Do n2 transforms of length n1 by transforming the matrix columns. Do this by fetching n1 x b blocks in memory so that the blocks are as large as possible but fit in main memory.
2. Then do n1 transforms of length n2 by transforming the matrix rows. Do this also by fetching b x n2 blocks in memory so that the blocks just fit in the available memory.

The algorithm requires reading blocks of b elements from the mass storage device. The smaller the amount of memory compared to the transform length is, the smaller is b also. Reading very short blocks of data from hard disks can be prohibitively slow.

When reading the column data to be transformed, the data can be transposed to rows by reading the b-length blocks to proper locations in memory and then transposing the b x b blocks.

In a convolution algorithm the data elements can remain in any order after the transform, as long as the inverse transform can transform it back. The convolution's element-by-element multiplication is not sensitive to the order in which the elements are.

All access to this class must be externally synchronized.

Since:
  1.7.0
Version:
  1.15.0
Author:
  Mikko Tommila
See Also:
  - `DataStorage.getTransposedArray(int,int,int,int)`

- ## Field Summary

  ### Fields inherited from class AbstractStepFNTStrategy

  `stepStrategy`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `TwoPassFNTStrategy()`
  Default constructor.
  `TwoPassFNTStrategy(NTTStepStrategy stepStrategy)`
  Constructor with step strategy.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `protected ArrayAccess`
  `getColumns(DataStorage dataStorage, int startColumn, int columns, int rows)`
  Get a block of column data.
  `protected ArrayAccess`
  `getRows(DataStorage dataStorage, int startRow, int rows, int columns)`
  Get a block of row data.
  `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 startRow, int startColumn, int rows, int columns, long length, long totalTransformLength, boolean isInverse, int modulus)`
  Multiply each matrix element `(i, j)` by `wi * j / totalTransformLength`.
  `protected void`
  `transform(DataStorage dataStorage, int n1, int n2, long length, int modulus)`
  Transform the data in steps.
  `protected void`
  `transformColumns(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)`
  Transform the columns of the data matrix.
  `protected void`
  `transformRows(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)`
  Transform the rows of the data matrix.

  ### Methods inherited from class AbstractStepFNTStrategy

  `getTransformLength, inverseTransform, transform`

  ### Methods inherited from class Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

  ### Methods inherited from interface DecorableNTTStrategy

  `postTransform, preTransform`

- ## Constructor Details

  - ### TwoPassFNTStrategy

    public TwoPassFNTStrategy()
    Default constructor.

  - ### TwoPassFNTStrategy

    public TwoPassFNTStrategy(NTTStepStrategy stepStrategy)
    Constructor with step strategy.
    Parameters:
      `stepStrategy` - The step strategy to use.

- ## 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`

  - ### getColumns

    protected ArrayAccess getColumns(DataStorage dataStorage, int startColumn, int columns, int rows)
    Get a block of column data. The data may be transposed, depending on the implementation.
    Parameters:
      `dataStorage` - The data storage.
      `startColumn` - The starting column where data is read.
      `columns` - The number of columns of data to read.
      `rows` - The number of rows of data to read. This should be equivalent to n1, number of rows in the matrix.
    Returns:
      Access to an array of size `columns` x `rows` containing the data.

  - ### getRows

    protected ArrayAccess getRows(DataStorage dataStorage, int startRow, int rows, int columns)
    Get a block of row data. The data may be transposed, depending on the implementation.
    Parameters:
      `dataStorage` - The data storage.
      `startRow` - The starting row where data is read.
      `rows` - The number of rows of data to read.
      `columns` - The number of columns of data to read. This should be equivalent to n2, number of columns in the matrix.
    Returns:
      Access to an array of size `columns` x `rows` containing the data.

  - ### multiplyElements

    protected void multiplyElements(ArrayAccess arrayAccess, int startRow, int startColumn, int rows, int columns, long length, long totalTransformLength, boolean isInverse, int modulus)
    Multiply each matrix element `(i, j)` by `wi * j / totalTransformLength`. The matrix size is n1 x n2.
    Parameters:
      `arrayAccess` - The memory array to multiply.
      `startRow` - Which row in the whole matrix the starting row in the `arrayAccess` is.
      `startColumn` - Which column in the whole matrix the starting column in the `arrayAccess` is.
      `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.

  - ### transformColumns

    protected void transformColumns(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)
    Transform the columns of the data matrix. The data may be in transposed format, depending on the implementation.

    By default the column 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 to columns and to transform.
      `length` - Length of one transform (one column).
      `count` - Number of columns.
      `isInverse` - `true` if an inverse transform is performed, `false` if a forward transform is performed.
      `modulus` - Index of the modulus.

  - ### transformRows

    protected void transformRows(ArrayAccess arrayAccess, int length, int count, boolean isInverse, int modulus)
    Transform the rows of the data matrix. The data may be in transposed format, depending on the implementation.

    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.