|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apfloat.internal.FloatElementaryModMath
org.apfloat.internal.FloatModMath
org.apfloat.internal.FloatTableFNTStrategy
org.apfloat.internal.FloatParallelFNTStrategy
org.apfloat.internal.FloatTwoPassFNTStrategy
public class FloatTwoPassFNTStrategy
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:
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.
DataStorage.getTransposedArray(int,int,int,int)
Constructor Summary | |
---|---|
FloatTwoPassFNTStrategy()
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.FloatParallelFNTStrategy |
---|
getSharedMemoryLockKey, lock, multiplyElements, transformRows, unlock |
Methods inherited from class org.apfloat.internal.FloatTableFNTStrategy |
---|
getTransformLength, inverseTableFNT, tableFNT |
Methods inherited from class org.apfloat.internal.FloatModMath |
---|
createWTable, getForwardNthRoot, getInverseNthRoot, modDivide, modInverse, modPow, negate |
Methods inherited from class org.apfloat.internal.FloatElementaryModMath |
---|
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 |
---|
public FloatTwoPassFNTStrategy()
Method Detail |
---|
public void transform(DataStorage dataStorage, int modulus) throws ApfloatRuntimeException
NTTStrategy
Multiple moduli can be used, if the convolution algorithm uses the Chinese Remainder Theorem to calculate the final result.
transform
in interface NTTStrategy
transform
in class FloatTableFNTStrategy
dataStorage
- The data to be transformed.modulus
- Number of modulus to use (in case the transform supports multiple moduli).
ApfloatRuntimeException
public void inverseTransform(DataStorage dataStorage, int modulus, long totalTransformLength) throws ApfloatRuntimeException
NTTStrategy
Multiple moduli can be used, if the convolution algorithm uses the Chinese Remainder Theorem to calculate the final result.
inverseTransform
in interface NTTStrategy
inverseTransform
in class FloatTableFNTStrategy
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.
ApfloatRuntimeException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |