Class DoubleKaratsubaConvolutionStrategy

All Implemented Interfaces:
Serializable, ConvolutionStrategy

public class DoubleKaratsubaConvolutionStrategy extends DoubleMediumConvolutionStrategy
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 Details

    • 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 Details

    • DoubleKaratsubaConvolutionStrategy

      public DoubleKaratsubaConvolutionStrategy(int radix)
      Creates a convolution strategy using the specified radix.
      Parameters:
      radix - The radix that will be used.
  • Method Details