Package org.apfloat.internal

Class AbstractConvolutionBuilder

java.lang.Object

org.apfloat.internal.AbstractConvolutionBuilder

All Implemented Interfaces:

ConvolutionBuilder

Direct Known Subclasses:

DoubleConvolutionBuilder, FloatConvolutionBuilder, IntConvolutionBuilder, LongConvolutionBuilder

public abstract class AbstractConvolutionBuilder
extends Object
implements ConvolutionBuilder

Abstract base class for creating convolutions of suitable type for the specified length.

Based on a work estimate, depending on the operand sizes and implementation-dependent factors, the O(n²) long multiplication, Karatsuba multiplication and the NTT algorithms are chosen e.g. as follows:

Convolution algorithms

size1	size2	Algorithm
16	16	Long
16	256	Long
32	32	Long
32	256	Long
64	64	Karatsuba
64	256	NTT
64	65536	Karatsuba
128	128	NTT
128	65536	NTT
128	4294967296	Karatsuba
256	256	NTT
256	4294967296	Karatsuba
512	512	NTT
512	4294967296	NTT

Since:

1.7.0

Version:

1.7.0

Author:

Mikko Tommila

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractConvolutionBuilder()	Subclass constructor.

Method Summary

Modifier and Type	Method	Description
ConvolutionStrategy	createConvolution(int radix, long size1, long size2, long resultSize)	Returns a convolution strategy of suitable type for the specified length.
protected abstract ConvolutionStrategy	createKaratsubaConvolutionStrategy(int radix)	Create a Karatsuba convolution strategy.
protected abstract ConvolutionStrategy	createMediumConvolutionStrategy(int radix)	Create a medium-length convolution strategy where the size of one of the data sets is relatively small (but more than one).
protected abstract ConvolutionStrategy	createShortConvolutionStrategy(int radix)	Create a short-length convolution strategy where the size of either data set is one.
protected abstract ConvolutionStrategy	createThreeNTTConvolutionStrategy(int radix, NTTStrategy nttStrategy)	Create a 3-NTT convolution strategy.
protected abstract float	getKaratsubaCostFactor()	Get the Karatsuba convolution cost factor.
protected abstract int	getKaratsubaCutoffPoint()	Get the Karatsuba convolution cutoff point.
protected abstract float	getNTTCostFactor()	Get the NTT convolution cost factor.

Methods inherited from class java.lang.Object

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

Constructor Details

AbstractConvolutionBuilder

protected AbstractConvolutionBuilder()

Subclass constructor.

Method Details

createConvolution

public ConvolutionStrategy createConvolution(int radix,
 long size1,
 long size2,
 long resultSize)

Description copied from interface: ConvolutionBuilder

Returns a convolution strategy of suitable type for the specified length.

Specified by:

createConvolution in interface ConvolutionBuilder

Parameters:

radix - The radix that will be used.

size1 - Length of first data set.

size2 - Length of second data set.

resultSize - Minimum number of elements needed in the result data.

Returns:

A suitable object for performing the convolution.

getKaratsubaCutoffPoint

protected abstract int getKaratsubaCutoffPoint()

Get the Karatsuba convolution cutoff point. When either operand is shorter than this then the medium-length convolution strategy should be used instead.

Returns:

The Karatsuba convolution cutoff point.

Since:

1.7.0

getKaratsubaCostFactor

protected abstract float getKaratsubaCostFactor()

Get the Karatsuba convolution cost factor. It is used in determining the most efficient convolution strategy for the given data lengths.

Returns:

The Karatsuba convolution cost factor.

Since:

1.7.0

getNTTCostFactor

protected abstract float getNTTCostFactor()

Get the NTT convolution cost factor. It is used in determining the most efficient convolution strategy for the given data lengths.

Returns:

The NTT convolution cost factor.

Since:

1.7.0

createShortConvolutionStrategy

protected abstract ConvolutionStrategy createShortConvolutionStrategy(int radix)

Create a short-length convolution strategy where the size of either data set is one.

Parameters:

radix - The radix that will be used.

Returns:

A new short-length convolution strategy.

Since:

1.7.0

createMediumConvolutionStrategy

protected abstract ConvolutionStrategy createMediumConvolutionStrategy(int radix)

Create a medium-length convolution strategy where the size of one of the data sets is relatively small (but more than one).

Parameters:

radix - The radix that will be used.

Returns:

A new medium-length convolution strategy.

Since:

1.7.0

createKaratsubaConvolutionStrategy

protected abstract ConvolutionStrategy createKaratsubaConvolutionStrategy(int radix)

Create a Karatsuba convolution strategy.

Parameters:

radix - The radix that will be used.

Returns:

A new Karatsuba convolution strategy.

Since:

1.7.0

createThreeNTTConvolutionStrategy

protected abstract ConvolutionStrategy createThreeNTTConvolutionStrategy(int radix,
 NTTStrategy nttStrategy)

Create a 3-NTT convolution strategy.

Parameters:

radix - The radix that will be used.

nttStrategy - The underlying NTT strategy.

Returns:

A new 3-NTT convolution strategy.

Since:

1.7.0