org.apfloat.internal
Class DoubleTwoPassFNTStrategy

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.DoubleTwoPassFNTStrategy
All Implemented Interfaces:
DoubleModConstants, NTTStrategy

public class DoubleTwoPassFNTStrategy
extends DoubleParallelFNTStrategy
implements NTTStrategy, DoubleModConstants

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, of course.

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().

This transform uses the maximum amount of memory available as retrieved from ApfloatContext.getMaxMemoryBlockSize(). All access on memory is synchronized on the shared memory lock retrieved from ApfloatContext.getSharedMemoryLock().

All access to this class must be externally synchronized.

Version:
1.0
Author:
Mikko Tommila
See Also:
DataStorage.getTransposedArray(int,int,int,int)

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
DoubleTwoPassFNTStrategy()
          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

DoubleTwoPassFNTStrategy

public DoubleTwoPassFNTStrategy()
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