Class AbstractConvolutionBuilder

  • All Implemented Interfaces:
    ConvolutionBuilder
    Direct Known Subclasses:
    DoubleConvolutionBuilder, FloatConvolutionBuilder, IntConvolutionBuilder, LongConvolutionBuilder

    public abstract class AbstractConvolutionBuilder
    extends 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
    size1size2Algorithm
    1616Long
    16256Long
    3232Long
    32256Long
    6464Karatsuba
    64256NTT
    6465536Karatsuba
    128128NTT
    12865536NTT
    1284294967296Karatsuba
    256256NTT
    2564294967296Karatsuba
    512512NTT
    5124294967296NTT
    Since:
    1.7.0
    Version:
    1.7.0
    Author:
    Mikko Tommila
    • Constructor Detail

      • AbstractConvolutionBuilder

        protected AbstractConvolutionBuilder()
        Subclass constructor.
    • 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 interface ConvolutionBuilder
        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