func TestRoundTripPolyValues(t *testing.T) {
	Size := 100000
	if testing.Short() {
		Size = 50
	}
	n := make(nat, Size)
	for p := range n {
		n[p] = Word(rand.Int63())
	}
	k, m := fftSize(n, nil)
	pol := polyFromNat(n, k, m)
	f := valueSize(k, m, 1)
	values := pol.Transform(f)
	pol2 := values.InvTransform()
	pol2.m = m
	t.Logf("k=%d, m=%d", k, m)
	n2 := pol2.Int()
	if cmpnat(t, n, n2) != 0 {
		t.Errorf("different n and n2")
	}
}
Tests Fourier transform and its reciprocal.
package bigfft
import (
	"fmt"
	. "math/big"
	"math/rand"
	"testing"
)
func cmpnat(t *testing.T, x, y nat) int {
	var a, b Int
	a.SetBits(x)
	b.SetBits(y)
	c := a.Cmp(&b)
	if c != 0 {
		t.Logf("a.len=%d, b.len=%d", a.BitLen(), b.BitLen())
		for i := 0; i < len(x) || i < len(y); i++ {
			var u, v Word
			if i < len(x) {
				u = x[i]
			}
			if i < len(y) {
				v = y[i]
			}
			if diff := u ^ v; diff != 0 {
				t.Logf("diff at word %d: %x", i, diff)
			}
		}
	}
	return c
}
func TestRoundTripIntPoly(t *testing.T) {
	N := 4
	step := 500
	if testing.Short() {
		N = 2
	}
	for size := 300; size < 50000; size += step {
		n := make(nat, size)
		for i := 0; i < N; i++ {
			for p := range n {
				n[p] = Word(rand.Int63())
			}
			k, m := fftSize(n, nil)
			pol := polyFromNat(n, k, m)
			n2 := pol.Int()
			if cmpnat(t, n, n2) != 0 {
				t.Errorf("different n and n2, size=%d, iter=%d", size, i)
			}
		}
	}
}
func TestFourierSizes(t *testing.T) {
	sizes := []int{
		2e3, 3e3, 5e3, 7e3, 10e3, 14e3,
		2e4, 3e4, 5e4, 7e4, 10e4, 14e4,
		2e5, 3e5, 5e5, 7e5, 10e5, 14e5,
		2e6, 3e6, 5e6, 7e6, 10e6, 14e6,
		2e7, 3e7, 5e7, 7e7, 10e7, 14e7,
		2e8, 3e8, 5e8, 7e8, 10e8, 14e8,
	}
	for _, s := range sizes {
		k, m := fftSize(make(nat, s/_W), make(nat, s/_W))
		v := valueSize(k, m, 2)
		t.Logf("bits=%d => FFT size %d, chunk size = %d, value size = %d",
			s, 1<<k, m, v)
		needed := 2*m*_W + int(k)
		got := v * _W
		t.Logf("inefficiency: value/chunk_product=%.2f, fftsize/inputsize=%.2f",
			float64(got)/float64(needed), float64(v<<k)/float64(2*s/_W))
		if v > 3*m {
			t.Errorf("FFT word size %d >> input word size %d", v, m)
		}
	}
}
func testFourier(t *testing.T, N int, k uint) {
	src := make([]fermat, 1<<k)
	for i := range src {
		src[i] = make(fermat, N+1)
		for p := 0; p < N; p++ {
			src[i][p] = Word(rnd.Int63())
		}
	}
	cmpFourier(t, N, k, src, false)
	cmpFourier(t, N, k, src, true)
	for i := range src {
		for p := 0; p < N; p++ {
			src[i][p] = ^Word(0)
		}
	}
	cmpFourier(t, N, k, src, false)
	cmpFourier(t, N, k, src, true)
}
func cmpFourier(t *testing.T, N int, k uint, src []fermat, inverse bool) {
	t.Logf("testFourier(t, %d, %d, inverse=%v)", N, k, inverse)
	ωshift := (4 * N * _W) >> k
	if inverse {
		ωshift = -ωshift
	}
	dst1 := make([]fermat, 1<<k)
	dst2 := make([]fermat, 1<<k)
	for i := range src {
		dst1[i] = make(fermat, N+1)
		dst2[i] = make(fermat, N+1)
	}
	tmp := make(fermat, N+1)
	tmp2 := make(fermat, N+1)
	for i := range src {
		for j := range dst1 {
			tmp.ShiftHalf(src[i], i*j*ωshift, tmp2)
			dst1[j].Add(dst1[j], tmp)
		}
	}
	fourier(dst2, src, inverse, N, k)
	for i := range src {
		if cmpnat(t, nat(dst1[i]), nat(dst2[i])) != 0 {
			var x, y Int
			x.SetBits(dst1[i])
			y.SetBits(dst2[i])
			t.Errorf("difference in dst[%d]: %x %x", i, &x, &y)
		}
	}
}
func TestFourier(t *testing.T) {
	testFourier(t, 1, 2)
	testFourier(t, 1, 3)
	testFourier(t, 1, 4)
	testFourier(t, 2, 2)
	testFourier(t, 2, 3)
	testFourier(t, 2, 4)
	testFourier(t, 2, 8)
	testFourier(t, 4, 4)
	testFourier(t, 4, 5)
	testFourier(t, 4, 6)
	testFourier(t, 4, 8)
	if _W == 64 {
		testFourier(t, 1, 8)
		testFourier(t, 3, 8)
		testFourier(t, 5, 8)
		testFourier(t, 7, 8)
		testFourier(t, 9, 8)
		testFourier(t, 11, 8)
	}
}