org.apfloat.internal
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 |
static int |
CUTOFF_POINT
Cut-off point for Karatsuba / basic convolution. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
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
LongKaratsubaConvolutionStrategy
public LongKaratsubaConvolutionStrategy(int radix)
- Creates a convolution strategy using the specified radix.
- Parameters:
radix
- The radix that will be used.
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