org.apfloat.internal
Class DoubleSixStepFNTStrategy

java.lang.Object
  extended byorg.apfloat.internal.DoubleElementaryModMath
      extended byorg.apfloat.internal.DoubleModMath
          extended byorg.apfloat.internal.DoubleTableFNTStrategy
              extended byorg.apfloat.internal.DoubleParallelFNTStrategy
                  extended byorg.apfloat.internal.DoubleSixStepFNTStrategy
All Implemented Interfaces:
DoubleModConstants, NTTStrategy

public class DoubleSixStepFNTStrategy
extends DoubleParallelFNTStrategy
implements NTTStrategy, DoubleModConstants

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, of course. Also scrambling the data can be omitted.

This algorithm is parallelized so that the row transforms are done in parallel using multiple threads, if the number of processors is greater than one in ApfloatContext.getNumberOfProcessors().

If the data block to be transformed is larger than the memory treshold setting in the current ApfloatContext, this class will synchronize all data access on the shared memory lock retrieved from ApfloatContext.getSharedMemoryLock().

All access to this class must be externally synchronized.

Version:
1.0
Author:
Mikko Tommila

Field Summary
 
Fields inherited from interface org.apfloat.internal.DoubleModConstants
MAX_POWER_OF_TWO_BASE, MAX_POWER_OF_TWO_BITS, MAX_TRANSFORM_LENGTH, MODULUS, PRIMITIVE_ROOT
 
Constructor Summary
DoubleSixStepFNTStrategy()
          Default constructor.
 
Method Summary
 void inverseTransform(DataStorage dataStorage, int modulus, long totalTransformLength)
          Perform an inverse transform on the data.
 void transform(DataStorage dataStorage, int modulus)
          Perform a forward transform on the data.
 
Methods inherited from class org.apfloat.internal.DoubleParallelFNTStrategy
getMemoryLock, multiplyElements, transformRows
 
Methods inherited from class org.apfloat.internal.DoubleTableFNTStrategy
getTransformLength, inverseTableFNT, tableFNT
 
Methods inherited from class org.apfloat.internal.DoubleModMath
createWTable, getForwardNthRoot, getInverseNthRoot, modDivide, modInverse, modPow, negate
 
Methods inherited from class org.apfloat.internal.DoubleElementaryModMath
getModulus, modAdd, modMultiply, modSubtract, setModulus
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface org.apfloat.spi.NTTStrategy
getTransformLength
 

Constructor Detail

DoubleSixStepFNTStrategy

public DoubleSixStepFNTStrategy()
Default constructor.

Method Detail

transform

public void transform(DataStorage dataStorage,
                      int modulus)
               throws ApfloatRuntimeException
Description copied from interface: NTTStrategy
Perform a forward transform on the data.

Multiple moduli can be used, if the convolution algorithm uses the Chinese Remainder Theorem to calculate the final result.

Specified by:
transform in interface NTTStrategy
Overrides:
transform in class DoubleTableFNTStrategy
Throws:
ApfloatRuntimeException

inverseTransform

public void inverseTransform(DataStorage dataStorage,
                             int modulus,
                             long totalTransformLength)
                      throws ApfloatRuntimeException
Description copied from interface: NTTStrategy
Perform an inverse transform on the data.

Multiple moduli can be used, if the convolution algorithm uses the Chinese Remainder Theorem to calculate the final result.

Specified by:
inverseTransform in interface NTTStrategy
Overrides:
inverseTransform in class DoubleTableFNTStrategy
Throws:
ApfloatRuntimeException