package bigfft

Import Path
	github.com/remyoudompheng/bigfft (on go.dev)

Dependency Relation
	imports 2 packages, and imported by one package

Involved Source Files

	      arith_decl.go
	      fermat.go
	   #d fft.go
		Package bigfft implements multiplication of big.Int using FFT.

		The implementation is based on the Schönhage-Strassen method
		using integer FFT modulo 2^n+1.

	      scan.go
	      arith_amd64.s
Package-Level Type Names (total 5, none are exported)

	/* sort exporteds by: alphabet | popularity */
	/* 5 unexporteds ... *//* 5 unexporteds: */
	 type fermat nat ([]T)
		A fermat of length w+1 represents a number modulo 2^(w*_W) + 1. The last
		word is zero or one. A number has at most two representatives satisfying the
		0-1 last word constraint.

		Methods (total 7, in which 6 are exported)
			( T) Add(x, y fermat) fermat
				Add computes addition mod 2^n+1.

			( T) Mul(x, y fermat) fermat
			( T) Shift(x fermat, k int)
				Shift computes (x << k) mod (2^n+1).

			( T) ShiftHalf(x fermat, k int, tmp fermat)
				ShiftHalf shifts x by k/2 bits the left. Shifting by 1/2 bit
				is multiplication by sqrt(2) mod 2^n+1 which is 2^(3n/4) - 2^(n/4).
				A temporary buffer must be provided in tmp.

			( T) String() string
			( T) Sub(x, y fermat) fermat
				Sub computes substraction mod 2^n+1.

			/* one unexported ... *//* one unexported: */
			( T) norm()
		Implements (at least 4, in which 1 are exported)
			 T : fmt.Stringer
			/* 3+ unexporteds ... *//* 3+ unexporteds: */
			 T : context.stringer
			 T : os/signal.stringer
			 T : runtime.stringer
		As Inputs Of (at least 3, none are exported)
			/* 3+ unexporteds ... *//* 3+ unexporteds: */
			func basicMul(z, x, y fermat)
			func fourier(dst []fermat, src []fermat, backward bool, n int, k uint)
			func fourier(dst []fermat, src []fermat, backward bool, n int, k uint)

	 type nat ([]T)

		Methods (only one, which is exported)
			( T) String() string
		Implements (at least 4, in which 1 are exported)
			 T : fmt.Stringer
			/* 3+ unexporteds ... *//* 3+ unexporteds: */
			 T : context.stringer
			 T : os/signal.stringer
			 T : runtime.stringer
		As Outputs Of (at least 2, neither is exported)
			/* 2+ unexporteds ... *//* 2+ unexporteds: */
			func fftmul(x, y nat) nat
			func trim(n nat) nat
		As Inputs Of (at least 4, none are exported)
			/* 4+ unexporteds ... *//* 4+ unexporteds: */
			func fftmul(x, y nat) nat
			func fftSize(x, y nat) (k uint, m int)
			func polyFromNat(x nat, k uint, m int) poly
			func trim(n nat) nat

	 type polValues (struct)
		A polValues represents the value of a poly at the powers of a
		K-th root of unity θ=2^(l/2) in Z/(b^n+1)Z, where b^n = 2^(K/4*l).

		Fields (total 3, none are exported)
			/* 3 unexporteds ... *//* 3 unexporteds: */
			k uint
				// k is such that K = 1<<k.

			n int
				// the length of coefficients, n*_W a multiple of K/4.

			values []fermat
				// a slice of K (n+1)-word values

		Methods (total 3, all are exported)
			(*T) InvNTransform() poly
				InvTransform reconstructs a polynomial from its values at
				roots of x^K+1. The m field of the returned polynomial
				is unspecified.

			(*T) InvTransform() poly
				InvTransform reconstructs p (modulo X^K - 1) from its
				values at θ^i for i = 0..K-1.

			(*T) Mul(q *polValues) (r polValues)
				Mul returns the pointwise product of p and q.


	 type poly (struct)
		poly represents an integer via a polynomial in Z[x]/(x^K+1)
		where K is the FFT length and b^m is the computation basis 1<<(m*_W).
		If P = a[0] + a[1] x + ... a[n] x^(K-1), the associated natural number
		is P(b^m).

		Fields (total 3, none are exported)
			/* 3 unexporteds ... *//* 3 unexporteds: */
			a []nat
				// a slice of at most K m-word coefficients.

			k uint
				// k is such that K = 1<<k.

			m int
				// the m such that P(b^m) is the original number.

		Methods (total 4, all are exported)
			(*T) Int() nat
				Int evaluates back a poly to its integer value.

			(*T) Mul(q *poly) poly
				Mul multiplies p and q modulo X^K-1, where K = 1<<p.k.
				The product is done via a Fourier transform.

			(*T) NTransform(n int) polValues
				NTransform evaluates p at θω^i for i = 0...K-1, where
				θ is a (2K)-th primitive root of unity in Z/(b^n+1)Z
				and ω = θ².

			(*T) Transform(n int) polValues
				Transform evaluates p at θ^i for i = 0...K-1, where
				θ is a K-th primitive root of unity in Z/(b^n+1)Z.

		As Outputs Of (at least one unexported)
			/* at least one unexported ... *//* at least one unexported: */
			func polyFromNat(x nat, k uint, m int) poly

	 type scanner (struct)

		Fields (only one, which is unexported)
			/* one unexported ... *//* one unexported: */
			powers []*big.Int
				powers[i] is 10^(2^i * quadraticScanThreshold).

		Methods (total 3, none are exported)
			/* 3 unexporteds ... *//* 3 unexporteds: */
			(*T) chunkSize(size int) (int, *big.Int)
			(*T) power(k uint) *big.Int
			(*T) scan(z *big.Int, str string)


Package-Level Functions (total 17, in which 2 are exported)

	 func FromDecimalString(s string) *big.Int
		FromDecimalString converts the base 10 string
		representation of a natural (non-negative) number
		into a *big.Int.
		Its asymptotic complexity is less than quadratic.

	 func Mul(x, y *big.Int) *big.Int
		Mul computes the product x*y and returns z.
		It can be used instead of the Mul method of
		*big.Int from math/big package.

	/* 15 unexporteds ... *//* 15 unexporteds: */
	 func addMulVVW(z, x []Word, y Word) (c Word)
	 func addVV(z, x, y []Word) (c Word)
		implemented in arith_$GOARCH.s

	 func addVW(z, x []Word, y Word) (c Word)
	 func basicMul(z, x, y fermat)
		copied from math/big

		basicMul multiplies x and y and leaves the result in z.
		The (non-normalized) result is placed in z[0 : len(x) + len(y)].

	 func fftmul(x, y nat) nat
	 func fftSize(x, y nat) (k uint, m int)
		returns the FFT length k, m the number of words per chunk
		such that m << k is larger than the number of words
		in x*y.

	 func fourier(dst []fermat, src []fermat, backward bool, n int, k uint)
		fourier performs an unnormalized Fourier transform
		of src, a length 1<<k vector of numbers modulo b^n+1
		where b = 1<<_W.

	 func mulAddVWW(z, x []Word, y, r Word) (c Word)
	 func mulFFT(x, y *big.Int) *big.Int
	 func polyFromNat(x nat, k uint, m int) poly
		polyFromNat slices the number x into a polynomial
		with 1<<k coefficients made of m words.

	 func shlVU(z, x []Word, s uint) (c Word)
	 func subVV(z, x, y []Word) (c Word)
	 func subVW(z, x []Word, y Word) (c Word)
	 func trim(n nat) nat
	 func valueSize(k uint, m int, extra uint) int
		valueSize returns the length (in words) to use for polynomial
		coefficients, to compute a correct product of polynomials P*Q
		where deg(P*Q) < K (== 1<<k) and where coefficients of P and Q are
		less than b^m (== 1 << (m*_W)).
		The chosen length (in bits) must be a multiple of 1 << (k-extra).


Package-Level Variables (total 2, neither is exported)

	/* 2 unexporteds ... *//* 2 unexporteds: */
	  var fftSizeThreshold [16]int64
		fftSizeThreshold[i] is the maximal size (in bits) where we should use
		fft size i.

	  var fftThreshold int
		fftThreshold is the size (in words) above which FFT is used over
		Karatsuba from math/big.

		TestCalibrate seems to indicate a threshold of 60kbits on 32-bit
		arches and 110kbits on 64-bit arches.


Package-Level Constants (total 2, neither is exported)

	/* 2 unexporteds ... *//* 2 unexporteds: */
	const _W int = 64
	const quadraticScanThreshold = 1232
		quadraticScanThreshold is the number of digits
		below which big.Int.SetString is more efficient
		than subquadratic algorithms.
		1232 digits fit in 4096 bits.

The pages are generated with Golds v0.3.6. (GOOS=darwin GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.