# Class LongKaratsubaConvolutionStrategy

java.lang.Object
org.apfloat.internal.LongBaseMath
org.apfloat.internal.LongMediumConvolutionStrategy
org.apfloat.internal.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 Summary

  Fields
  Modifier and Type
  Field
  Description
  `static final int`
  `CUTOFF_POINT`
  Cut-off point for Karatsuba / basic convolution.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `LongKaratsubaConvolutionStrategy(int radix)`
  Creates a convolution strategy using the specified radix.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `DataStorage`
  `convolute(DataStorage x, DataStorage y, long resultSize)`
  Convolutes the two sets of data.

  ### Methods inherited from class LongBaseMath

  `baseAdd, baseDivide, baseMultiplyAdd, baseSubtract`

  ### Methods inherited from class Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## 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

  - ### LongKaratsubaConvolutionStrategy

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

- ## Method Details

  - ### convolute

    public DataStorage convolute(DataStorage x, DataStorage y, long resultSize) throws ApfloatRuntimeException
    Description copied from interface: `ConvolutionStrategy`
    Convolutes the two sets of data.
    Specified by:
      `convolute` in interface `ConvolutionStrategy`
    Overrides:
      `convolute` in class `LongMediumConvolutionStrategy`
    Parameters:
      `x` - First data set.
      `y` - Second data set.
      `resultSize` - Number of elements needed in the result data.
    Returns:
      The convolved data.
    Throws:
      `ApfloatRuntimeException`