func reversePairs32(x uint32) uint32 {
	const m = 1<<32 - 1
	x = x>>2&(m1&m) | x&(m1&m)<<2
	x = x>>4&(m2&m) | x&(m2&m)<<4
	return bits.ReverseBytes32(x)
}
reversePairs32 returns the value of x with its bit pairs in reversed order.
package fourier
import (
	"math"
	"math/bits"
	"math/cmplx"
)
func CoefficientsRadix2(seq []complex128) []complex128 {
	x := seq
	switch len(x) {
	default:
		if bits.OnesCount(uint(len(x))) != 1 {
			panic("fourier: radix-2 fft called with non-power 2 length")
		}
	case 0, 1:
		return x
	case 2:
		x[0], x[1] =
			x[0]+x[1],
			x[0]-x[1]
		return x
	case 4:
		t := x[1] + x[3]
		u := x[2]
		v := negi(x[1] - x[3])
		x[0], x[1], x[2], x[3] =
			x[0]+u+t,
			x[0]-u+v,
			x[0]+u-t,
			x[0]-u-v
		return x
	}
	bitReversePermute(x)
	for k := 0; k < len(x); k += 4 {
		t := x[k+2] + x[k+3]
		u := x[k+1]
		v := negi(x[k+2] - x[k+3])
		x[k], x[k+1], x[k+2], x[k+3] =
			x[k]+u+t,
			x[k]-u+v,
			x[k]+u-t,
			x[k]-u-v
	}
	for m := 4; m < len(x); m *= 2 {
		f := swap(complex(math.Sincos(-math.Pi / float64(m))))
		for k := 0; k < len(x); k += 2 * m {
			w := 1 + 0i
			for j := 0; j < m; j++ {
				i := j + k
				u := w * x[i+m]
				x[i], x[i+m] =
					x[i]+u,
					x[i]-u
				w *= f
			}
		}
	}
	return x
}
func bitReversePermute(x []complex128) {
	if len(x) < 2 || bits.OnesCount(uint(len(x))) != 1 {
		panic("fourier: invalid bitReversePermute call")
	}
	lz := bits.LeadingZeros(uint(len(x) - 1))
	i := 0
	for ; i < len(x)/2; i++ {
		j := int(bits.Reverse(uint(i)) >> lz)
		if i < j {
			x[i], x[j] = x[j], x[i]
		}
	}
	for i++; i < len(x); i += 2 {
		j := int(bits.Reverse(uint(i)) >> lz)
		if i < j {
			x[i], x[j] = x[j], x[i]
		}
	}
}
func SequenceRadix2(coeff []complex128) []complex128 {
	x := coeff
	for i, j := 1, len(x)-1; i < j; i, j = i+1, j-1 {
		x[i], x[j] = x[j], x[i]
	}
	CoefficientsRadix2(x)
	return x
}
func PadRadix2(x []complex128) []complex128 {
	if len(x) == 0 {
		return x
	}
	b := bits.Len(uint(len(x)))
	if len(x) == 1<<(b-1) {
		return x
	}
	p := make([]complex128, 1<<b)
	copy(p, x)
	return p
}
func TrimRadix2(x []complex128) (even, remains []complex128) {
	if len(x) == 0 {
		return x, nil
	}
	n := 1 << (bits.Len(uint(len(x))) - 1)
	return x[:n], x[n:]
}
func CoefficientsRadix4(seq []complex128) []complex128 {
	x := seq
	switch len(x) {
	default:
		if bits.OnesCount(uint(len(x))) != 1 || bits.TrailingZeros(uint(len(x)))&0x1 != 0 {
			panic("fourier: radix-4 fft called with non-power 4 length")
		}
	case 0, 1:
		return x
	case 4:
		t := x[1] + x[3]
		u := x[2]
		v := negi(x[1] - x[3])
		x[0], x[1], x[2], x[3] =
			x[0]+u+t,
			x[0]-u+v,
			x[0]+u-t,
			x[0]-u-v
		return x
	}
	bitPairReversePermute(x)
	for k := 0; k < len(x); k += 4 {
		t := x[k+1] + x[k+3]
		u := x[k+2]
		v := negi(x[k+1] - x[k+3])
		x[k], x[k+1], x[k+2], x[k+3] =
			x[k]+u+t,
			x[k]-u+v,
			x[k]+u-t,
			x[k]-u-v
	}
	for m := 4; m < len(x); m *= 4 {
		f := swap(complex(math.Sincos((-math.Pi / 2) / float64(m))))
		for k := 0; k < len(x); k += m * 4 {
			w := 1 + 0i
			w2 := w
			w3 := w2
			for j := 0; j < m; j++ {
				i := j + k
				t := x[i+m]*w + x[i+3*m]*w3
				u := x[i+2*m] * w2
				v := negi(x[i+m]*w - x[i+3*m]*w3)
				x[i], x[i+m], x[i+2*m], x[i+3*m] =
					x[i]+u+t,
					x[i]-u+v,
					x[i]+u-t,
					x[i]-u-v
				wt := f
				w *= wt
				wt *= f
				w2 *= wt
				wt *= f
				w3 *= wt
			}
		}
	}
	return x
}
func bitPairReversePermute(x []complex128) {
	if len(x) < 4 || bits.OnesCount(uint(len(x))) != 1 || bits.TrailingZeros(uint(len(x)))&0x1 != 0 {
		panic("fourier: invalid bitPairReversePermute call")
	}
	lz := bits.LeadingZeros(uint(len(x) - 1))
	i := 0
	for ; i < 3*len(x)/4; i++ {
		j := int(reversePairs(uint(i)) >> lz)
		if i < j {
			x[i], x[j] = x[j], x[i]
		}
	}
	for i++; i < len(x); i += 2 {
		j := int(reversePairs(uint(i)) >> lz)
		if i < j {
			x[i], x[j] = x[j], x[i]
		}
	}
}
func SequenceRadix4(coeff []complex128) []complex128 {
	x := coeff
	for i, j := 1, len(x)-1; i < j; i, j = i+1, j-1 {
		x[i], x[j] = x[j], x[i]
	}
	CoefficientsRadix4(x)
	return x
}
func PadRadix4(x []complex128) []complex128 {
	if len(x) == 0 {
		return x
	}
	b := bits.Len(uint(len(x)))
	if len(x) == 1<<(b-1) && b&0x1 == 1 {
		return x
	}
	p := make([]complex128, 1<<((b+1)&^0x1))
	copy(p, x)
	return p
}
func TrimRadix4(x []complex128) (even, remains []complex128) {
	if len(x) == 0 {
		return x, nil
	}
	n := 1 << ((bits.Len(uint(len(x))) - 1) &^ 0x1)
	return x[:n], x[n:]
}
func reversePairs(x uint) uint {
	if bits.UintSize == 32 {
		return uint(reversePairs32(uint32(x)))
	}
	return uint(reversePairs64(uint64(x)))
}
const (
	m1 = 0x3333333333333333
	m2 = 0x0f0f0f0f0f0f0f0f
)