Package org.apfloat.internal
Class StepCarryCRTStrategy
- java.lang.Object
-
- org.apfloat.internal.StepCarryCRTStrategy
-
- All Implemented Interfaces:
Parallelizable
,CarryCRTStrategy
public class StepCarryCRTStrategy extends java.lang.Object implements CarryCRTStrategy, Parallelizable
Class for performing the final step of a three-modulus Number Theoretic Transform based convolution. Works with blocks of data.The algorithm is parallelized for multiprocessor computers, if the data fits in memory.
The parallelization works so that the carry-CRT is done in blocks in parallel. As a final step, a second pass is done through the data set to propagate the carries from one block to the next.
All access to this class must be externally synchronized.
- Since:
- 1.7.0
- Version:
- 1.9.0
- See Also:
CarryCRTStepStrategy
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
StepCarryCRTStrategy.CarryCRTRunnable<T>
-
Field Summary
Fields Modifier and Type Field Description private int
radix
-
Constructor Summary
Constructors Constructor Description StepCarryCRTStrategy(int radix)
Creates a carry-CRT object using the specified radix.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description DataStorage
carryCRT(DataStorage resultMod0, DataStorage resultMod1, DataStorage resultMod2, long resultSize)
Calculate the final result of a three-NTT convolution.protected <T> ParallelRunnable
createCarryCRTParallelRunnable(java.lang.Class<T> elementArrayType, DataStorage resultMod0, DataStorage resultMod1, DataStorage resultMod2, DataStorage dataStorage, long size, long resultSize)
Create a ParallelRunnable object for doing the carry-CRT in parallel.private <T> DataStorage
doCarryCRT(java.lang.Class<T> elementArrayType, DataStorage resultMod0, DataStorage resultMod1, DataStorage resultMod2, long resultSize)
-
-
-
Method Detail
-
carryCRT
public DataStorage carryCRT(DataStorage resultMod0, DataStorage resultMod1, DataStorage resultMod2, long resultSize) throws ApfloatRuntimeException
Calculate the final result of a three-NTT convolution.Performs a Chinese Remainder Theorem (CRT) on each element of the three result data sets to get the result of each element modulo the product of the three moduli. Then it calculates the carries to get the final result.
Note that the return value's initial word may be zero or non-zero, depending on how large the result is.
Assumes that
MODULUS[0] > MODULUS[1] > MODULUS[2]
.- Specified by:
carryCRT
in interfaceCarryCRTStrategy
- Parameters:
resultMod0
- The result moduloMODULUS[0]
.resultMod1
- The result moduloMODULUS[1]
.resultMod2
- The result moduloMODULUS[2]
.resultSize
- The number of elements needed in the final result.- Returns:
- The final result with the CRT performed and the carries calculated.
- Throws:
ApfloatRuntimeException
-
doCarryCRT
private <T> DataStorage doCarryCRT(java.lang.Class<T> elementArrayType, DataStorage resultMod0, DataStorage resultMod1, DataStorage resultMod2, long resultSize) throws ApfloatRuntimeException
- Throws:
ApfloatRuntimeException
-
createCarryCRTParallelRunnable
protected <T> ParallelRunnable createCarryCRTParallelRunnable(java.lang.Class<T> elementArrayType, DataStorage resultMod0, DataStorage resultMod1, DataStorage resultMod2, DataStorage dataStorage, long size, long resultSize)
Create a ParallelRunnable object for doing the carry-CRT in parallel.- Type Parameters:
T
- The element array type used.- Parameters:
elementArrayType
- The element array type used.resultMod0
- The result moduloMODULUS[0]
.resultMod1
- The result moduloMODULUS[1]
.resultMod2
- The result moduloMODULUS[2]
.dataStorage
- The destination data storage of the computation.size
- The number of elements in the whole data set.resultSize
- The number of elements needed in the final result.- Returns:
- An suitable object for performing the carry-CRT in parallel.
-
-