Modifier and Type	Class and Description
pack-priv static class	FftMultiplier.ComplexVector
pack-priv static class	FftMultiplier.MutableComplex

Modifier and Type	Field and Description
public static final double	COS_0_25
private static final int	FFT_THRESHOLD The threshold value for using floating point FFT multiplication.
private static final int	MAX_MAG_LENGTH This constant limits `mag.length` of BigIntegers to the supported range.
private static volatile FftMultiplier.ComplexVector[]	ROOTS2_CACHE Sets of complex roots of unity.
private static volatile FftMultiplier.ComplexVector[]	ROOTS3_CACHE Sets of complex roots of unity.
private static final int	ROOTS3_CACHE_SIZE for FFTs of length up to 3*2^19
private static final int	ROOTS_CACHE2_SIZE for FFTs of length up to 2^19
public static final double	SIN_0_25
private static final int	TOOM_COOK_THRESHOLD The threshold value for using 3-way Toom-Cook multiplication.

Access	Constructor and Description
pack-priv	FftMultiplier()

Method Summary

Modifier and Type	Method and Description
pack-priv static int	Returns: the maximum number of bits bitsPerFftPoint(int length of this number in bits bitLen) Returns the maximum number of bits that one double precision number can fit without causing the multiplication to be incorrect.
private static FftMultiplier.ComplexVector	calculateRootsOfUnity(int n) Returns n-th complex roots of unity for the angles 0..pi/2, suitable for a transform of length n.
private static void	fft(FftMultiplier.ComplexVector input and output, must be a power of two in size a, FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length), log2(a.length)-2, log2(a.length)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2*roots.length))`, i.e., they must cover the first quadrant. roots) Performs an FFT of length 2^n on the vector `a`.
private static void	fft3(FftMultiplier.ComplexVector inputs / outputs for the first FFT coefficient a0, FftMultiplier.ComplexVector inputs / outputs for the second FFT coefficient a1, FftMultiplier.ComplexVector inputs / outputs for the third FFT coefficient a2, int 1 for a forward FFT, -1 for an inverse FFT sign, double 1 for a forward FFT, 1/3 for an inverse FFT scale) Performs FFTs or IFFTs of size 3 on the vector `(a0[i], a1[i], a2[i])` for each `i`.
private static void	fftMixedRadix(FftMultiplier.ComplexVector input and output, must be 32^n in size for some n>=2 a, FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length/3), log2(a.length/3)-2, log2(a.length/3)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2roots.length))`, i.e., they must cover the first quadrant. roots2, FftMultiplier.ComplexVector must be the same length as `a` and contain roots of unity such that `roots[k] = e^(piki/(2roots3.length))`, i.e., they need to cover the first quadrant. roots3) Performs an FFT of length 32^n on the vector `a`.
pack-priv static BigInteger	fromFftVector(FftMultiplier.ComplexVector fftVec, int signum, int bitsPerFftPoint)
private static FftMultiplier.ComplexVector[]	getRootsOfUnity2(int for a transform of length 2^logN logN) Returns sets of complex roots of unity.
private static FftMultiplier.ComplexVector	getRootsOfUnity3(int for a transform of length 3*2^logN logN) Returns sets of complex roots of unity.
private static void	ifft(FftMultiplier.ComplexVector input and output, must be a power of two in size a, FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length), log2(a.length)-2, log2(a.length)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2*roots.length))`, i.e., they must cover the first quadrant. roots) Performs an inverse FFT of length 2^n on the vector `a`.
private static void	ifftMixedRadix(FftMultiplier.ComplexVector input and output, must be 32^n in size for some n>=2 a, FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length/3), log2(a.length/3)-2, log2(a.length/3)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2roots.length))`, i.e., they must cover the first quadrant. roots2, FftMultiplier.ComplexVector must be the same length as `a` and contain roots of unity such that `roots[k] = e^(piki/(2roots3.length))`, i.e., they need to cover the first quadrant. roots3) Performs an inverse FFT of length 32^n on the vector `a`.
pack-priv static BigInteger	Returns: `this * val` multiply(BigInteger value a a, BigInteger value b b) Returns a BigInteger whose value is `(a * b)`.
pack-priv static BigInteger	Returns: a*b multiplyFft(BigInteger value a a, BigInteger value b b) Multiplies two BigIntegers using a floating-point FFT.
pack-priv static BigInteger	Returns: `this<sup>2</sup>` square(BigInteger a) Returns a BigInteger whose value is `(this<sup>2</sup>)`.
pack-priv static BigInteger	squareFft(BigInteger a)
pack-priv static FftMultiplier.ComplexVector	toFftVector(byte[] mag, int fftLen, int bitsPerFftPoint) Converts this BigInteger into an array of complex numbers suitable for an FFT.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

COS_0_25	back to summary
public static final double COS_0_25

FFT_THRESHOLD	back to summary
private static final int FFT_THRESHOLD The threshold value for using floating point FFT multiplication. If the number of bits in each mag array is greater than the Toom-Cook threshold, and the number of bits in at least one of the mag arrays is greater than this threshold, then FFT multiplication will be used.

MAX_MAG_LENGTH	back to summary
private static final int MAX_MAG_LENGTH This constant limits `mag.length` of BigIntegers to the supported range.

ROOTS2_CACHE	back to summary
private static volatile FftMultiplier.ComplexVector[] ROOTS2_CACHE Sets of complex roots of unity. The set at index k contains 2^k elements representing all (2^(k+2))-th roots between 0 and pi/2. Used for FFT multiplication.

ROOTS3_CACHE	back to summary
private static volatile FftMultiplier.ComplexVector[] ROOTS3_CACHE Sets of complex roots of unity. The set at index k contains 32^k elements representing all (32^(k+2))-th roots between 0 and pi/2. Used for FFT multiplication.

ROOTS3_CACHE_SIZE	back to summary
private static final int ROOTS3_CACHE_SIZE for FFTs of length up to 3*2^19

ROOTS_CACHE2_SIZE	back to summary
private static final int ROOTS_CACHE2_SIZE for FFTs of length up to 2^19

SIN_0_25	back to summary
public static final double SIN_0_25

TOOM_COOK_THRESHOLD	back to summary
private static final int TOOM_COOK_THRESHOLD The threshold value for using 3-way Toom-Cook multiplication.

Constructor Detail

FftMultiplier	back to summary
pack-priv FftMultiplier()

Method Detail

bitsPerFftPoint	back to summary
pack-priv static int bitsPerFftPoint(int bitLen) Returns the maximum number of bits that one double precision number can fit without causing the multiplication to be incorrect. Parameters bitLen:int length of this number in bits Returns:int the maximum number of bits

bitsPerFftPoint

back to summary

pack-priv static int bitsPerFftPoint(int bitLen)

Returns the maximum number of bits that one double precision number can fit without causing the multiplication to be incorrect.

Parameters

bitLen:int: length of this number in bits

Returns:int

the maximum number of bits

calculateRootsOfUnity	back to summary
private static FftMultiplier.ComplexVector calculateRootsOfUnity(int n) Returns n-th complex roots of unity for the angles 0..pi/2, suitable for a transform of length n. They are used as twiddle factors and as weights for the right-angle transform. n must be 1 or an even number.

fft back to summary

fft	back to summary
private static void fft(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots) Performs an FFT of length 2^n on the vector `a`. This is a decimation-in-frequency implementation. Parameters a:FftMultiplier.ComplexVector input and output, must be a power of two in size roots:FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length), log2(a.length)-2, log2(a.length)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2*roots.length))`, i.e., they must cover the first quadrant.

private static void fft(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots)

Performs an FFT of length 2^n on the vector a. This is a decimation-in-frequency implementation.

Parameters

a:FftMultiplier.ComplexVector: input and output, must be a power of two in size
roots:FftMultiplier.ComplexVector[]: an array that contains one set of roots at indices log2(a.length), log2(a.length)-2, log2(a.length)-4, ... Each roots[s] must contain 2^s roots of unity such that roots[s][k] = e^(pi*k*i/(2*roots.length)), i.e., they must cover the first quadrant.

fft3 back to summary

fft3	back to summary
private static void fft3(FftMultiplier.ComplexVector a0, FftMultiplier.ComplexVector a1, FftMultiplier.ComplexVector a2, int sign, double scale) Performs FFTs or IFFTs of size 3 on the vector `(a0[i], a1[i], a2[i])` for each `i`. The output is placed back into `a0, a1, and a2`. Parameters a0:FftMultiplier.ComplexVector inputs / outputs for the first FFT coefficient a1:FftMultiplier.ComplexVector inputs / outputs for the second FFT coefficient a2:FftMultiplier.ComplexVector inputs / outputs for the third FFT coefficient sign:int 1 for a forward FFT, -1 for an inverse FFT scale:double 1 for a forward FFT, 1/3 for an inverse FFT

private static void fft3(FftMultiplier.ComplexVector a0, FftMultiplier.ComplexVector a1, FftMultiplier.ComplexVector a2, int sign, double scale)

Performs FFTs or IFFTs of size 3 on the vector (a0[i], a1[i], a2[i]) for each i. The output is placed back into a0, a1, and a2.

Parameters

a0:FftMultiplier.ComplexVector: inputs / outputs for the first FFT coefficient
a1:FftMultiplier.ComplexVector: inputs / outputs for the second FFT coefficient
a2:FftMultiplier.ComplexVector: inputs / outputs for the third FFT coefficient
sign:int: 1 for a forward FFT, -1 for an inverse FFT
scale:double: 1 for a forward FFT, 1/3 for an inverse FFT

fftMixedRadix back to summary

fftMixedRadix	back to summary
private static void fftMixedRadix(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots2, FftMultiplier.ComplexVector roots3) Performs an FFT of length 32^n on the vector `a`. Uses the 4-step algorithm to decompose the 32^n FFT into 2^n FFTs of length 3 and 3 FFTs of length 2^n. See https://www.nas.nasa.gov/assets/pdf/techreports/1989/rnr-89-004.pdf Parameters a:FftMultiplier.ComplexVector input and output, must be 32^n in size for some n>=2 roots2:FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length/3), log2(a.length/3)-2, log2(a.length/3)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2roots.length))`, i.e., they must cover the first quadrant. roots3:FftMultiplier.ComplexVector must be the same length as `a` and contain roots of unity such that `roots[k] = e^(piki/(2*roots3.length))`, i.e., they need to cover the first quadrant.

private static void fftMixedRadix(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots2, FftMultiplier.ComplexVector roots3)

Performs an FFT of length 3*2^n on the vector a. Uses the 4-step algorithm to decompose the 3*2^n FFT into 2^n FFTs of length 3 and 3 FFTs of length 2^n. See https://www.nas.nasa.gov/assets/pdf/techreports/1989/rnr-89-004.pdf

Parameters

a:FftMultiplier.ComplexVector: input and output, must be 3*2^n in size for some n>=2
roots2:FftMultiplier.ComplexVector[]: an array that contains one set of roots at indices log2(a.length/3), log2(a.length/3)-2, log2(a.length/3)-4, ... Each roots[s] must contain 2^s roots of unity such that roots[s][k] = e^(pi*k*i/(2*roots.length)), i.e., they must cover the first quadrant.
roots3:FftMultiplier.ComplexVector: must be the same length as a and contain roots of unity such that roots[k] = e^(pi*k*i/(2*roots3.length)), i.e., they need to cover the first quadrant.

fromFftVector	back to summary
pack-priv static BigInteger fromFftVector(FftMultiplier.ComplexVector fftVec, int signum, int bitsPerFftPoint)

getRootsOfUnity2	back to summary
private static FftMultiplier.ComplexVector[] getRootsOfUnity2(int logN) Returns sets of complex roots of unity. For k=logN, logN-2, logN-4, ..., the return value contains all k-th roots between 0 and pi/2. Parameters logN:int for a transform of length 2^logN

getRootsOfUnity2

back to summary

private static FftMultiplier.ComplexVector[] getRootsOfUnity2(int logN)

Returns sets of complex roots of unity. For k=logN, logN-2, logN-4, ..., the return value contains all k-th roots between 0 and pi/2.

Parameters

logN:int: for a transform of length 2^logN

getRootsOfUnity3	back to summary
private static FftMultiplier.ComplexVector getRootsOfUnity3(int logN) Returns sets of complex roots of unity. For k=logN, logN-2, logN-4, ..., the return value contains all k-th roots between 0 and pi/2. Parameters logN:int for a transform of length 3*2^logN

getRootsOfUnity3

back to summary

private static FftMultiplier.ComplexVector getRootsOfUnity3(int logN)

Returns sets of complex roots of unity. For k=logN, logN-2, logN-4, ..., the return value contains all k-th roots between 0 and pi/2.

Parameters

logN:int: for a transform of length 3*2^logN

ifft back to summary

ifft	back to summary
private static void ifft(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots) Performs an inverse FFT of length 2^n on the vector `a`. This is a decimation-in-time implementation. Parameters a:FftMultiplier.ComplexVector input and output, must be a power of two in size roots:FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length), log2(a.length)-2, log2(a.length)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2*roots.length))`, i.e., they must cover the first quadrant.

private static void ifft(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots)

Performs an inverse FFT of length 2^n on the vector a. This is a decimation-in-time implementation.

Parameters

a:FftMultiplier.ComplexVector: input and output, must be a power of two in size
roots:FftMultiplier.ComplexVector[]: an array that contains one set of roots at indices log2(a.length), log2(a.length)-2, log2(a.length)-4, ... Each roots[s] must contain 2^s roots of unity such that roots[s][k] = e^(pi*k*i/(2*roots.length)), i.e., they must cover the first quadrant.

ifftMixedRadix back to summary

ifftMixedRadix	back to summary
private static void ifftMixedRadix(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots2, FftMultiplier.ComplexVector roots3) Performs an inverse FFT of length 32^n on the vector `a`. Uses the 4-step algorithm to decompose the 32^n FFT into 2^n FFTs of length 3 and 3 FFTs of length 2^n. See https://www.nas.nasa.gov/assets/pdf/techreports/1989/rnr-89-004.pdf Parameters a:FftMultiplier.ComplexVector input and output, must be 32^n in size for some n>=2 roots2:FftMultiplier.ComplexVector[] an array that contains one set of roots at indices log2(a.length/3), log2(a.length/3)-2, log2(a.length/3)-4, ... Each roots[s] must contain 2^s roots of unity such that `roots[s][k] = e^(piki/(2roots.length))`, i.e., they must cover the first quadrant. roots3:FftMultiplier.ComplexVector must be the same length as `a` and contain roots of unity such that `roots[k] = e^(piki/(2*roots3.length))`, i.e., they need to cover the first quadrant.

private static void ifftMixedRadix(FftMultiplier.ComplexVector a, FftMultiplier.ComplexVector[] roots2, FftMultiplier.ComplexVector roots3)

Performs an inverse FFT of length 3*2^n on the vector a. Uses the 4-step algorithm to decompose the 3*2^n FFT into 2^n FFTs of length 3 and 3 FFTs of length 2^n. See https://www.nas.nasa.gov/assets/pdf/techreports/1989/rnr-89-004.pdf

Parameters

a:FftMultiplier.ComplexVector: input and output, must be 3*2^n in size for some n>=2
roots2:FftMultiplier.ComplexVector[]: an array that contains one set of roots at indices log2(a.length/3), log2(a.length/3)-2, log2(a.length/3)-4, ... Each roots[s] must contain 2^s roots of unity such that roots[s][k] = e^(pi*k*i/(2*roots.length)), i.e., they must cover the first quadrant.
roots3:FftMultiplier.ComplexVector: must be the same length as a and contain roots of unity such that roots[k] = e^(pi*k*i/(2*roots3.length)), i.e., they need to cover the first quadrant.

multiply back to summary

multiply	back to summary
pack-priv static BigInteger multiply(BigInteger a, BigInteger b) Returns a BigInteger whose value is `(a * b)`. Implementation Note An implementation may offer better algorithmic performance when `a == b`. Parameters a:BigInteger value a b:BigInteger value b Returns:BigInteger `this * val`

pack-priv static BigInteger multiply(BigInteger a, BigInteger b)

Returns a BigInteger whose value is (a * b).

Implementation Note

An implementation may offer better algorithmic performance when a == b.

Parameters

a:BigInteger: value a
b:BigInteger: value b

Returns:BigInteger

this * val

multiplyFft	back to summary
pack-priv static BigInteger multiplyFft(BigInteger a, BigInteger b) Multiplies two BigIntegers using a floating-point FFT. Floating-point math is inaccurate; to ensure the output of the FFT and IFFT rounds to the correct result for every input, the provably safe FFT error bounds from "Rapid Multiplication Modulo The Sum And Difference of Highly Composite Numbers" by Colin Percival, pg. 392 (fft.pdf) are used, the vector is "balanced" before the FFT, and accurate twiddle factors are used. This implementation incorporates several features compared to the standard FFT algorithm (Cooley Tukey FFT algorithm): It uses a variant called right-angle convolution which weights the vector before the transform. The benefit of the right-angle convolution is that when multiplying two numbers of length n, an FFT of length n suffices whereas a regular FFT needs length 2n. This is because the right-angle convolution places half of the result in the real part and the other half in the imaginary part. See: Discrete Weighted Transforms And Large-Integer Arithmetic by Richard Crandall and Barry Fagin. FFTs of length 32^n are supported in addition to 2^n. Radix-4 butterflies; see https://www.nxp.com/docs/en/application-note/AN3666.pdf Bernstein's conjugate twiddle trick for a small speed gain at the expense of (further) reordering the output of the FFT which is not a problem because it is reordered back in the IFFT. Roots of unity are cached FFT vectors are stored as arrays of primitive doubles (two array elements are needed for representing one complex number). Storing them as arrays of primitive doubles instead of as MutableComplex objects is memory efficient, but in some cases below ~10^6 decimal digits, it hurts speed because it requires additional copying. Ideally this would be implemented using value types when they become available. Parameters a:BigInteger value a b:BigInteger value b Returns:BigInteger ab

multiplyFft

back to summary

pack-priv static BigInteger multiplyFft(BigInteger a, BigInteger b)

Multiplies two BigIntegers using a floating-point FFT.

Floating-point math is inaccurate; to ensure the output of the FFT and IFFT rounds to the correct result for every input, the provably safe FFT error bounds from "Rapid Multiplication Modulo The Sum And Difference of Highly Composite Numbers" by Colin Percival, pg. 392 (fft.pdf) are used, the vector is "balanced" before the FFT, and accurate twiddle factors are used.

This implementation incorporates several features compared to the standard FFT algorithm (Cooley Tukey FFT algorithm):

It uses a variant called right-angle convolution which weights the vector before the transform. The benefit of the right-angle convolution is that when multiplying two numbers of length n, an FFT of length n suffices whereas a regular FFT needs length 2n. This is because the right-angle convolution places half of the result in the real part and the other half in the imaginary part. See: Discrete Weighted Transforms And Large-Integer Arithmetic by Richard Crandall and Barry Fagin.
FFTs of length 3*2^n are supported in addition to 2^n.
Radix-4 butterflies; see https://www.nxp.com/docs/en/application-note/AN3666.pdf
Bernstein's conjugate twiddle trick for a small speed gain at the expense of (further) reordering the output of the FFT which is not a problem because it is reordered back in the IFFT.
Roots of unity are cached

FFT vectors are stored as arrays of primitive doubles (two array elements are needed for representing one complex number). Storing them as arrays of primitive doubles instead of as MutableComplex objects is memory efficient, but in some cases below ~10^6 decimal digits, it hurts speed because it requires additional copying. Ideally this would be implemented using value types when they become available.

Parameters

a:BigInteger: value a
b:BigInteger: value b

Returns:BigInteger

a*b

square back to summary

square	back to summary
pack-priv static BigInteger square(BigInteger a) Returns a BigInteger whose value is `(this<sup>2</sup>)`. Returns:BigInteger `this<sup>2</sup>`

pack-priv static BigInteger square(BigInteger a)

Returns a BigInteger whose value is (this<sup>2</sup>).

Returns:BigInteger: this<sup>2</sup>

squareFft	back to summary
pack-priv static BigInteger squareFft(BigInteger a)

toFftVector	back to summary
pack-priv static FftMultiplier.ComplexVector toFftVector(byte[] mag, int fftLen, int bitsPerFftPoint) Converts this BigInteger into an array of complex numbers suitable for an FFT. Populates the real parts and sets the imaginary parts to zero.

ch.randelshofer.fastdoubleparser back to summary

pack-priv final Class FftMultiplier.ComplexVector

Class Inheritance

extends Object

java.lang.Object
ch.randelshofer.fastdoubleparser.FftMultiplier.ComplexVector

Field Summary

Modifier and Type	Field and Description
private final double[]	a This arrays contains complex numbers.
private static final int	COMPLEX_SIZE_SHIFT A complex number in an FFT double[] vector occupies 2^1 array elements.
private static final int	IMAG
private final int	length The number of complex numbers stored in this vector.
private final int	offset Offset to the real part of a complex number.
private static final int	REAL

Constructor Summary

Access	Constructor and Description
pack-priv	ComplexVector(int length)
pack-priv	ComplexVector(FftMultiplier.ComplexVector the other vector c, int start index of the view from, int end index of the view to) Creates a view on another vector.

Method Summary

Modifier and Type	Method and Description
pack-priv void	add(int idxa, FftMultiplier.MutableComplex c)
pack-priv void	addInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)
pack-priv void	addTimesIInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)
pack-priv void	applyInverseWeights(FftMultiplier.ComplexVector weights) Multiplies the elements of an FFT vector by 1/weight.
pack-priv void	applyWeights(FftMultiplier.ComplexVector weights) Multiplies the elements of an FFT vector by weights.
pack-priv void	copyInto(int idxa, FftMultiplier.MutableComplex destination)
pack-priv double	imag(int idxa)
pack-priv void	imag(int idxa, double value)
private int	imagIdx(int idxa)
pack-priv void	multiply(int idxa, FftMultiplier.MutableComplex c) Multiplies `a` by `c`.
pack-priv void	multiplyByIAnd(int idxa, FftMultiplier.MutableComplex c) Multiplies `a` by `c` and by `i`.
pack-priv void	multiplyConjugate(int idxa, FftMultiplier.MutableComplex c) Multiplies `a` by the conjugate of `c`.
pack-priv void	multiplyConjugateInto(int idxa, FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)
pack-priv void	multiplyConjugateTimesI(int idxa, FftMultiplier.MutableComplex c) Multiplies `(a[i].real,a[i+1].imaginary)` by the conjugate of `c` and by `i`.
pack-priv void	multiplyInto(int idxa, FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)
pack-priv void	multiplyPointwise(FftMultiplier.ComplexVector cvec)
pack-priv double	part(int idxa, int part)
pack-priv double	real(int idxa)
pack-priv void	real(int idxa, double value)
private int	realIdx(int idxa)
pack-priv void	set(int idxa, double real, double imag)
pack-priv void	squarePointwise() The result is placed in the argument
pack-priv void	subtractInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)
pack-priv void	subtractTimesIInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)
pack-priv void	timesTwoToThe(int idxa, int n)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

a	back to summary
private final double[] a This arrays contains complex numbers. A complex number occupies 2 consecutive array elements: the real part and then the imaginary part.

back to summary

private final double[] a

This arrays contains complex numbers.

A complex number occupies 2 consecutive array elements: the real part and then the imaginary part.

COMPLEX_SIZE_SHIFT	back to summary
private static final int COMPLEX_SIZE_SHIFT A complex number in an FFT double[] vector occupies 2^1 array elements.

IMAG	back to summary
private static final int IMAG

length	back to summary
private final int length The number of complex numbers stored in this vector.

offset	back to summary
private final int offset Offset to the real part of a complex number.

REAL	back to summary
private static final int REAL

Constructor Detail

ComplexVector	back to summary
pack-priv ComplexVector(int length)

ComplexVector	back to summary
pack-priv ComplexVector(FftMultiplier.ComplexVector c, int from, int to) Creates a view on another vector. Parameters c:FftMultiplier.ComplexVector the other vector from:int start index of the view to:int end index of the view

ComplexVector

back to summary

pack-priv ComplexVector(FftMultiplier.ComplexVector c, int from, int to)

Creates a view on another vector.

Parameters

c:FftMultiplier.ComplexVector: the other vector
from:int: start index of the view
to:int: end index of the view

Method Detail

add	back to summary
pack-priv void add(int idxa, FftMultiplier.MutableComplex c)

addInto	back to summary
pack-priv void addInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)

addTimesIInto	back to summary
pack-priv void addTimesIInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)

applyInverseWeights	back to summary
pack-priv void applyInverseWeights(FftMultiplier.ComplexVector weights) Multiplies the elements of an FFT vector by 1/weight. Used for the right-angle convolution.

applyWeights	back to summary
pack-priv void applyWeights(FftMultiplier.ComplexVector weights) Multiplies the elements of an FFT vector by weights. Doing this makes a regular FFT convolution a right-angle convolution.

copyInto	back to summary
pack-priv void copyInto(int idxa, FftMultiplier.MutableComplex destination)

imag	back to summary
pack-priv double imag(int idxa)

imag	back to summary
pack-priv void imag(int idxa, double value)

imagIdx	back to summary
private int imagIdx(int idxa)

multiply	back to summary
pack-priv void multiply(int idxa, FftMultiplier.MutableComplex c) Multiplies `a` by `c`. Stores the result in a[idx] and a[idx+1].

multiplyByIAnd	back to summary
pack-priv void multiplyByIAnd(int idxa, FftMultiplier.MutableComplex c) Multiplies `a` by `c` and by `i`. Stores the result in a[idx] and a[idx+1].

multiplyConjugate	back to summary
pack-priv void multiplyConjugate(int idxa, FftMultiplier.MutableComplex c) Multiplies `a` by the conjugate of `c`. Stores the result in a[i] and a[i+1].

multiplyConjugateInto	back to summary
pack-priv void multiplyConjugateInto(int idxa, FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)

multiplyConjugateTimesI	back to summary
pack-priv void multiplyConjugateTimesI(int idxa, FftMultiplier.MutableComplex c) Multiplies `(a[i].real,a[i+1].imaginary)` by the conjugate of `c` and by `i`. Stores the result in a[i] and a[i+1].

multiplyInto	back to summary
pack-priv void multiplyInto(int idxa, FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)

multiplyPointwise	back to summary
pack-priv void multiplyPointwise(FftMultiplier.ComplexVector cvec)

part	back to summary
pack-priv double part(int idxa, int part)

real	back to summary
pack-priv double real(int idxa)

real	back to summary
pack-priv void real(int idxa, double value)

realIdx	back to summary
private int realIdx(int idxa)

set	back to summary
pack-priv void set(int idxa, double real, double imag)

squarePointwise	back to summary
pack-priv void squarePointwise() The result is placed in the argument

subtractInto	back to summary
pack-priv void subtractInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)

subtractTimesIInto	back to summary
pack-priv void subtractTimesIInto(int idxa, FftMultiplier.ComplexVector c, int idxc, FftMultiplier.MutableComplex destination)

timesTwoToThe	back to summary
pack-priv void timesTwoToThe(int idxa, int n)

ch.randelshofer.fastdoubleparser back to summary

pack-priv final Class FftMultiplier.MutableComplex

Class Inheritance

extends Object

java.lang.Object
ch.randelshofer.fastdoubleparser.FftMultiplier.MutableComplex

Field Summary

Modifier and Type	Field and Description
pack-priv double	imag
pack-priv double	real

Constructor Summary

Access	Constructor and Description
pack-priv	MutableComplex()

Method Summary

Modifier and Type	Method and Description
pack-priv void	add(FftMultiplier.MutableComplex c)
pack-priv void	add(FftMultiplier.ComplexVector c, int idxc)
pack-priv void	addInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination) Adds c to this number and stores the result in destination.
pack-priv void	addTimesI(FftMultiplier.MutableComplex c) Adds c*i to this number.
pack-priv void	addTimesI(FftMultiplier.ComplexVector c, int idxc)
pack-priv void	addTimesIInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination) Adds c*i to this number and stores the result in destination.
pack-priv void	copyInto(FftMultiplier.ComplexVector c, int idxc)
pack-priv void	multiply(FftMultiplier.MutableComplex c)
pack-priv void	multiplyConjugate(FftMultiplier.MutableComplex c) multiplies this number by the conjugate of c.
pack-priv void	set(FftMultiplier.ComplexVector c, int idxc)
pack-priv void	squareInto(FftMultiplier.MutableComplex destination)
pack-priv void	subtract(FftMultiplier.MutableComplex c)
pack-priv void	subtract(FftMultiplier.ComplexVector c, int idxc)
pack-priv void	subtractInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)
pack-priv void	subtractInto(FftMultiplier.MutableComplex c, FftMultiplier.ComplexVector destination, int idxd)
pack-priv void	subtractTimesI(FftMultiplier.MutableComplex c)
pack-priv void	subtractTimesI(FftMultiplier.ComplexVector c, int idxc)
pack-priv void	subtractTimesIInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

imag	back to summary
pack-priv double imag

real	back to summary
pack-priv double real

Constructor Detail

MutableComplex	back to summary
pack-priv MutableComplex()

Method Detail

add	back to summary
pack-priv void add(FftMultiplier.MutableComplex c)

add	back to summary
pack-priv void add(FftMultiplier.ComplexVector c, int idxc)

addInto	back to summary
pack-priv void addInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination) Adds c to this number and stores the result in destination. Leaves this number unmodified.

addTimesI	back to summary
pack-priv void addTimesI(FftMultiplier.MutableComplex c) Adds c*i to this number.

addTimesI	back to summary
pack-priv void addTimesI(FftMultiplier.ComplexVector c, int idxc)

addTimesIInto	back to summary
pack-priv void addTimesIInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination) Adds c*i to this number and stores the result in destination. Leaves this number unmodified.

copyInto	back to summary
pack-priv void copyInto(FftMultiplier.ComplexVector c, int idxc)

multiply	back to summary
pack-priv void multiply(FftMultiplier.MutableComplex c)

multiplyConjugate	back to summary
pack-priv void multiplyConjugate(FftMultiplier.MutableComplex c) multiplies this number by the conjugate of c.

set	back to summary
pack-priv void set(FftMultiplier.ComplexVector c, int idxc)

squareInto	back to summary
pack-priv void squareInto(FftMultiplier.MutableComplex destination)

subtract	back to summary
pack-priv void subtract(FftMultiplier.MutableComplex c)

subtract	back to summary
pack-priv void subtract(FftMultiplier.ComplexVector c, int idxc)

subtractInto	back to summary
pack-priv void subtractInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)

subtractInto	back to summary
pack-priv void subtractInto(FftMultiplier.MutableComplex c, FftMultiplier.ComplexVector destination, int idxd)

subtractTimesI	back to summary
pack-priv void subtractTimesI(FftMultiplier.MutableComplex c)

subtractTimesI	back to summary
pack-priv void subtractTimesI(FftMultiplier.ComplexVector c, int idxc)

subtractTimesIInto	back to summary
pack-priv void subtractTimesIInto(FftMultiplier.MutableComplex c, FftMultiplier.MutableComplex destination)

pack-priv Class FftMultiplier

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class FftMultiplier.ComplexVector

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class FftMultiplier.MutableComplex

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail