Class LongKaratsubaConvolutionStrategy

  • All Implemented Interfaces:
    java.io.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
    See Also:
    Serialized Form