Package org.apfloat.internal
Class AbstractConvolutionBuilder
- java.lang.Object
-
- org.apfloat.internal.AbstractConvolutionBuilder
-
- All Implemented Interfaces:
ConvolutionBuilder
- Direct Known Subclasses:
DoubleConvolutionBuilder
,FloatConvolutionBuilder
,IntConvolutionBuilder
,LongConvolutionBuilder
public abstract class AbstractConvolutionBuilder extends java.lang.Object implements ConvolutionBuilder
Abstract base class for creating convolutions of suitable type for the specified length.Based on a work estimate, depending on the operand sizes and implementation-dependent factors, the O(n2) long multiplication, Karatsuba multiplication and the NTT algorithms are chosen e.g. as follows:
Convolution algorithms size1 size2 Algorithm 16 16 Long 16 256 Long 32 32 Long 32 256 Long 64 64 Karatsuba 64 256 NTT 64 65536 Karatsuba 128 128 NTT 128 65536 NTT 128 4294967296 Karatsuba 256 256 NTT 256 4294967296 Karatsuba 512 512 NTT 512 4294967296 NTT - Since:
- 1.7.0
- Version:
- 1.7.0
-
-
Field Summary
Fields Modifier and Type Field Description private static double
LOG2_3
-
Constructor Summary
Constructors Modifier Constructor Description protected
AbstractConvolutionBuilder()
Subclass constructor.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description ConvolutionStrategy
createConvolution(int radix, long size1, long size2, long resultSize)
Returns a convolution strategy of suitable type for the specified length.protected abstract ConvolutionStrategy
createKaratsubaConvolutionStrategy(int radix)
Create a Karatsuba convolution strategy.protected abstract ConvolutionStrategy
createMediumConvolutionStrategy(int radix)
Create a medium-length convolution strategy where the size of one of the data sets is relatively small (but more than one).protected abstract ConvolutionStrategy
createShortConvolutionStrategy(int radix)
Create a short-length convolution strategy where the size of either data set is one.protected abstract ConvolutionStrategy
createThreeNTTConvolutionStrategy(int radix, NTTStrategy nttStrategy)
Create a 3-NTT convolution strategy.protected abstract float
getKaratsubaCostFactor()
Get the Karatsuba convolution cost factor.protected abstract int
getKaratsubaCutoffPoint()
Get the Karatsuba convolution cutoff point.protected abstract float
getNTTCostFactor()
Get the NTT convolution cost factor.
-
-
-
Method Detail
-
createConvolution
public ConvolutionStrategy createConvolution(int radix, long size1, long size2, long resultSize)
Description copied from interface:ConvolutionBuilder
Returns a convolution strategy of suitable type for the specified length.- Specified by:
createConvolution
in interfaceConvolutionBuilder
- Parameters:
radix
- The radix that will be used.size1
- Length of first data set.size2
- Length of second data set.resultSize
- Minimum number of elements needed in the result data.- Returns:
- A suitable object for performing the convolution.
-
getKaratsubaCutoffPoint
protected abstract int getKaratsubaCutoffPoint()
Get the Karatsuba convolution cutoff point. When either operand is shorter than this then the medium-length convolution strategy should be used instead.- Returns:
- The Karatsuba convolution cutoff point.
- Since:
- 1.7.0
-
getKaratsubaCostFactor
protected abstract float getKaratsubaCostFactor()
Get the Karatsuba convolution cost factor. It is used in determining the most efficient convolution strategy for the given data lengths.- Returns:
- The Karatsuba convolution cost factor.
- Since:
- 1.7.0
-
getNTTCostFactor
protected abstract float getNTTCostFactor()
Get the NTT convolution cost factor. It is used in determining the most efficient convolution strategy for the given data lengths.- Returns:
- The NTT convolution cost factor.
- Since:
- 1.7.0
-
createShortConvolutionStrategy
protected abstract ConvolutionStrategy createShortConvolutionStrategy(int radix)
Create a short-length convolution strategy where the size of either data set is one.- Parameters:
radix
- The radix that will be used.- Returns:
- A new short-length convolution strategy.
- Since:
- 1.7.0
-
createMediumConvolutionStrategy
protected abstract ConvolutionStrategy createMediumConvolutionStrategy(int radix)
Create a medium-length convolution strategy where the size of one of the data sets is relatively small (but more than one).- Parameters:
radix
- The radix that will be used.- Returns:
- A new medium-length convolution strategy.
- Since:
- 1.7.0
-
createKaratsubaConvolutionStrategy
protected abstract ConvolutionStrategy createKaratsubaConvolutionStrategy(int radix)
Create a Karatsuba convolution strategy.- Parameters:
radix
- The radix that will be used.- Returns:
- A new Karatsuba convolution strategy.
- Since:
- 1.7.0
-
createThreeNTTConvolutionStrategy
protected abstract ConvolutionStrategy createThreeNTTConvolutionStrategy(int radix, NTTStrategy nttStrategy)
Create a 3-NTT convolution strategy.- Parameters:
radix
- The radix that will be used.nttStrategy
- The underlying NTT strategy.- Returns:
- A new 3-NTT convolution strategy.
- Since:
- 1.7.0
-
-