Package org.apfloat.internal
Class LongKaratsubaConvolutionStrategy
- java.lang.Object
-
- org.apfloat.internal.LongBaseMath
-
- org.apfloat.internal.LongMediumConvolutionStrategy
-
- org.apfloat.internal.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
-
-
Field Summary
Fields Modifier and Type Field Description static int
CUTOFF_POINT
Cut-off point for Karatsuba / basic convolution.private static long
serialVersionUID
-
Constructor Summary
Constructors Constructor Description LongKaratsubaConvolutionStrategy(int radix)
Creates a convolution strategy using the specified radix.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private DataStorage
add(DataStorage x1, DataStorage x2)
DataStorage
convolute(DataStorage x, DataStorage y, long resultSize)
Convolutes the two sets of data.private boolean
isZero(DataStorage x, long index)
private void
subtract(DataStorage x1, DataStorage x2)
-
Methods inherited from class org.apfloat.internal.LongBaseMath
baseAdd, baseDivide, baseMultiplyAdd, baseSubtract
-
-
-
-
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
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
-
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 interfaceConvolutionStrategy
- Overrides:
convolute
in classLongMediumConvolutionStrategy
- Parameters:
x
- First data set.y
- Second data set.resultSize
- Number of elements needed in the result data.- Returns:
- The convolved data.
- Throws:
ApfloatRuntimeException
-
add
private DataStorage add(DataStorage x1, DataStorage x2)
-
subtract
private void subtract(DataStorage x1, DataStorage x2)
-
isZero
private boolean isZero(DataStorage x, long index)
-
-