org.apfloat.internal

Class FloatSixStepFNTStrategy

java.lang.Object

org.apfloat.internal.FloatElementaryModMath

org.apfloat.internal.FloatModMath

org.apfloat.internal.FloatTableFNTStrategy

org.apfloat.internal.FloatParallelFNTStrategy

org.apfloat.internal.FloatSixStepFNTStrategy

All Implemented Interfaces:

ParallelNTTStrategy, NTTStrategy

public class FloatSixStepFNTStrategy
extends FloatParallelFNTStrategy

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 n₁ x n₂ 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 w^{i 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 shared 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.5.1

Author:

Mikko Tommila

Field Summary

Fields inherited from class org.apfloat.internal.FloatParallelFNTStrategy

parallelRunner

Constructor Summary

Constructors

Constructor and Description
FloatSixStepFNTStrategy() Default constructor.

Method Summary

Methods

Modifier and Type	Method and Description
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

multiplyElements, setParallelRunner, transformRows

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

FloatSixStepFNTStrategy

public FloatSixStepFNTStrategy()

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 FloatTableFNTStrategy

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

Overrides:

inverseTransform in class FloatTableFNTStrategy

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