org.apfloat.internal
Class DoubleTableFNTStrategy

java.lang.Object
  extended by org.apfloat.internal.DoubleElementaryModMath
      extended by org.apfloat.internal.DoubleModMath
          extended by org.apfloat.internal.DoubleTableFNTStrategy
All Implemented Interfaces:
NTTStrategy
Direct Known Subclasses:
DoubleParallelFNTStrategy

public class DoubleTableFNTStrategy
extends DoubleModMath
implements NTTStrategy

Fast Number Theoretic Transform that uses lookup tables for powers of n:th root of unity and permutation indexes.

All access to this class must be externally synchronized.

Version:
1.1
Author:
Mikko Tommila

Constructor Summary
DoubleTableFNTStrategy()
          Default constructor.
 
Method Summary
 long getTransformLength(long size)
          Return the supported transform length for the specified data size.
protected  void inverseTableFNT(ArrayAccess arrayAccess, double[] wTable, int[] permutationTable)
          Inverse (Cooley-Tukey) fast Number Theoretic Transform.
 void inverseTransform(DataStorage dataStorage, int modulus, long totalTransformLength)
          Perform an inverse transform on the data.
protected  void tableFNT(ArrayAccess arrayAccess, double[] wTable, int[] permutationTable)
          Forward (Sande-Tukey) fast Number Theoretic Transform.
 void transform(DataStorage dataStorage, int modulus)
          Perform a forward transform on the data.
 
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
 

Constructor Detail

DoubleTableFNTStrategy

public DoubleTableFNTStrategy()
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
Parameters:
dataStorage - The data to be transformed.
modulus - Number of modulus to use (in case the transform supports multiple moduli).
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
Parameters:
dataStorage - The data to be transformed.
modulus - Number of modulus to use (in case the transform supports multiple moduli).
totalTransformLength - Total transform length; the final result elements are divided by this value.
Throws:
ApfloatRuntimeException

getTransformLength

public long getTransformLength(long size)
Description copied from interface: NTTStrategy
Return the supported transform length for the specified data size.

Specified by:
getTransformLength in interface NTTStrategy
Parameters:
size - Length of the data to be transformed.
Returns:
Length of the transform needed by this transform.

tableFNT

protected void tableFNT(ArrayAccess arrayAccess,
                        double[] wTable,
                        int[] permutationTable)
                 throws ApfloatRuntimeException
Forward (Sande-Tukey) fast Number Theoretic Transform. Data length must be a power of two.

Parameters:
arrayAccess - The data array to transform.
wTable - Table of powers of n:th root of unity w modulo the current modulus.
permutationTable - Table of permutation indexes, or null if the data should not be permuted.
Throws:
ApfloatRuntimeException

inverseTableFNT

protected void inverseTableFNT(ArrayAccess arrayAccess,
                               double[] wTable,
                               int[] permutationTable)
                        throws ApfloatRuntimeException
Inverse (Cooley-Tukey) fast Number Theoretic Transform. Data length must be a power of two.

Parameters:
arrayAccess - The data array to transform.
wTable - Table of powers of n:th root of unity w modulo the current modulus.
permutationTable - Table of permutation indexes, or null if the data should not be permuted.
Throws:
ApfloatRuntimeException