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