public abstract class AbstractConvolutionBuilder extends Object implements ConvolutionBuilder
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:
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 |
Modifier | Constructor and Description |
---|---|
protected |
AbstractConvolutionBuilder()
Subclass constructor.
|
Modifier and Type | Method and 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.
|
protected AbstractConvolutionBuilder()
public ConvolutionStrategy createConvolution(int radix, long size1, long size2, long resultSize)
ConvolutionBuilder
createConvolution
in interface ConvolutionBuilder
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.protected abstract int getKaratsubaCutoffPoint()
protected abstract float getKaratsubaCostFactor()
protected abstract float getNTTCostFactor()
protected abstract ConvolutionStrategy createShortConvolutionStrategy(int radix)
radix
- The radix that will be used.protected abstract ConvolutionStrategy createMediumConvolutionStrategy(int radix)
radix
- The radix that will be used.protected abstract ConvolutionStrategy createKaratsubaConvolutionStrategy(int radix)
radix
- The radix that will be used.protected abstract ConvolutionStrategy createThreeNTTConvolutionStrategy(int radix, NTTStrategy nttStrategy)
radix
- The radix that will be used.nttStrategy
- The underlying NTT strategy.Copyright © 2017. All rights reserved.