org.apfloat.internal
Class LongKaratsubaConvolutionStrategy

java.lang.Object
  extended by org.apfloat.internal.LongBaseMath
      extended by org.apfloat.internal.LongMediumConvolutionStrategy
          extended by 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
static int CUTOFF_POINT
          Cut-off point for Karatsuba / basic convolution.
 
Constructor Summary
LongKaratsubaConvolutionStrategy(int radix)
          Creates a convolution strategy using the specified radix.
 
Method Summary
 DataStorage convolute(DataStorage x, DataStorage y, long resultSize)
          Convolutes the two sets of data.
 
Methods inherited from class org.apfloat.internal.LongBaseMath
baseAdd, baseDivide, baseMultiplyAdd, baseSubtract
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

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.
Method Detail

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