Package org.apfloat.internal

Class IntKaratsubaConvolutionStrategy

java.lang.Object

org.apfloat.internal.IntBaseMath

org.apfloat.internal.IntMediumConvolutionStrategy

org.apfloat.internal.IntKaratsubaConvolutionStrategy

All Implemented Interfaces:

java.io.Serializable, ConvolutionStrategy

public class IntKaratsubaConvolutionStrategy
extends IntMediumConvolutionStrategy

Convolution strategy using the Karatsuba algorithm. The complexity of the algorithm is O(n^{log(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(n²) algorithm is applied. The Karatsuba algorithm is faster than the basic O(n²) 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
IntKaratsubaConvolutionStrategy(int radix)	Creates a convolution strategy using the specified radix.

Method Summary

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.IntBaseMath

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(n²) algorithm i.e. super.convolute().

See Also:

Constant Field Values

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

Constructor Detail

IntKaratsubaConvolutionStrategy

public IntKaratsubaConvolutionStrategy(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 IntMediumConvolutionStrategy

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)