Class LongKaratsubaConvolutionStrategy

  • All Implemented Interfaces:
    Serializable, ConvolutionStrategy

    public class LongKaratsubaConvolutionStrategy
    extends LongMediumConvolutionStrategy
    Convolution strategy using the Karatsuba algorithm. The complexity of the algorithm is O(nlog(3)/log(2)) as the operands are split to two and multiplied using three multiplications (and five additions / subtractions). This splitting is done recursively until some cut-off point where the basic O(n2) algorithm is applied. The Karatsuba algorithm is faster than the basic O(n2) multiplication algorithm for medium size numbers larger than some certain size. For very large numbers, the transform-based convolution algorithms are faster.
    Since:
    1.4
    Version:
    1.4
    Author:
    Mikko Tommila
    See Also:
    Serialized Form
    • Field Detail

      • CUTOFF_POINT

        public static final int CUTOFF_POINT
        Cut-off point for Karatsuba / basic convolution.

        Convolutions where the shorter number is at most this long are calculated using the basic O(n2) algorithm i.e. super.convolute().

        See Also:
        Constant Field Values
    • Constructor Detail

      • LongKaratsubaConvolutionStrategy

        public LongKaratsubaConvolutionStrategy​(int radix)
        Creates a convolution strategy using the specified radix.
        Parameters:
        radix - The radix that will be used.