// -*- C++ -*- // automatically generated by autodoc // ========== HEADER FILE src/haar/fib-haar.h: ========== inline void fibonacci_haar(double *a, ulong f0, ulong f1); // In-place Fibonacci-Haar transform of a[0,...,f0-1]. // f0 must be a Fibonacci number, f1 the next smaller Fibonacci number. inline void fibonacci_haar_nn(double *a, ulong f0, ulong f1); // In-place Fibonacci-Haar transform of a[0,...,f0-1]. // Non-normalized version. // f0 must be a Fibonacci number, f1 the next smaller Fibonacci number. // ========== HEADER FILE src/haar/haar.h: ========== void haar(Type *f, ulong ldn, Type *ws=nullptr); // Transform wrt. to Haar base // // The basis functions are: // 0: [+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +] // 1: [+ + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - -] // 2: [+ + + + + + + + - - - - - - - - ] // 3: [ + + + + + + + + - - - - - - - -] // 4: [+ + + + - - - - ] // 5: [ + + + + - - - - ] // 6: [ + + + + - - - - ] // 7: [ + + + + - - - -] // 8: [+ + - - ] // 9: [ + + - - ] // 10: [ + + - - ] // 11: [ + + - - ] // 12: [ + + - - ] // 13: [ + + - - ] // 14: [ + + - - ] // 15: [ + + - -] // 16: [+ - ] // 17: [ + - ] // 18: [ + - ] // 19: [ + - ] // 20: [ + - ] // 21: [ + - ] // 22: [ + - ] // 23: [ + - ] // 24: [ + - ] // 25: [ + - ] // 26: [ + - ] // 27: [ + - ] // 28: [ + - ] // 29: [ + - ] // 30: [ + - ] // 31: [ + -] // void inverse_haar(Type *f, ulong ldn, Type *ws=nullptr); // Inverse transform wrt. to Haar base void haar_inplace(Type *f, ulong ldn); // Transform wrt. to haar base. // In-place operation. // The sequence // haar_inplace(); haar_permute(); // is equivalent to // haar() // // The basis (is the Haar basis, reordered): // 0: [+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +] // 1: [+ - ] // 2: [+ + - - ] // 3: [ + - ] // 4: [+ + + + - - - - ] // 5: [ + - ] // 6: [ + + - - ] // 7: [ + - ] // 8: [+ + + + + + + + - - - - - - - - ] // 9: [ + - ] // 10: [ + + - - ] // 11: [ + - ] // 12: [ + + + + - - - - ] // 13: [ + - ] // 14: [ + + - - ] // 15: [ + - ] // 16: [+ + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - -] // 17: [ + - ] // 18: [ + + - - ] // 19: [ + - ] // 20: [ + + + + - - - - ] // 21: [ + - ] // 22: [ + + - - ] // 23: [ + - ] // 24: [ + + + + + + + + - - - - - - - -] // 25: [ + - ] // 26: [ + + - - ] // 27: [ + - ] // 28: [ + + + + - - - -] // 29: [ + - ] // 30: [ + + - -] // 31: [ + -] // void inverse_haar_inplace(Type *f, ulong ldn); // Inverse transform wrt. to Haar base. // In-place operation. // The sequence // inverse_haar_permute(); inverse_haar_inplace(); // is equivalent to // inverse_haar() // ========== HEADER FILE src/haar/haarnn.h: ========== void haar_nn(Type *f, ulong ldn, Type *ws=nullptr); // Transform wrt. to non-normalized Haar base void inverse_haar_nn(Type *f, ulong ldn, Type *ws=nullptr); void haar_inplace_nn(Type *f, ulong ldn); // Transform wrt. to non-normalized Haar base, // In-place operation. // The sequence // haar_inplace_nn(); haar_permute(); // is equivalent to // haar_nn() void inverse_haar_inplace_nn(Type *f, ulong ldn); // Inverse transform wrt. to Haar base // In-place operation. // The sequence // inverse_haar_permute(); inverse_haar_inplace(); // is equivalent to // inverse_haar() // ========== HEADER FILE src/haar/haarrevnn.h: ========== void haar_rev_nn(Type *f, ulong ldn); // Transform with basis: abs() // 0: [ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + ] 1/32 // 1: [ + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - ] 1/32 // 2: [ + - + - + - + - + - + - + - + - ] 1/16 // 3: [ + - + - + - + - + - + - + - + - ] 1/16 // 4: [ + - + - + - + - ] 1/8 // 5: [ + - + - + - + - ] 1/8 // 6: [ + - + - + - + - ] 1/8 // 7: [ + - + - + - + - ] 1/8 // 8: [ + - + - ] 1/4 // 9: [ + - + - ] 1/4 // 10: [ + - + - ] 1/4 // 11: [ + - + - ] 1/4 // 12: [ + - + - ] 1/4 // 13: [ + - + - ] 1/4 // 14: [ + - + - ] 1/4 // 15: [ + - + - ] 1/4 // 16: [ + - ] 1/2 // 17: [ + - ] 1/2 // 18: [ + - ] 1/2 // 19: [ + - ] 1/2 // 20: [ + - ] 1/2 // 21: [ + - ] 1/2 // 22: [ + - ] 1/2 // 23: [ + - ] 1/2 // 24: [ + - ] 1/2 // 25: [ + - ] 1/2 // 26: [ + - ] 1/2 // 27: [ + - ] 1/2 // 28: [ + - ] 1/2 // 29: [ + - ] 1/2 // 30: [ + - ] 1/2 // 31: [ + - ] 1/2 // // in-place algorithm // no normalization void inverse_haar_rev_nn(Type *f, ulong ldn); // ========== HEADER FILE src/haar/mers-haar.h: ========== inline void mersenne_haar(double *a, ulong f0); // In-place Mersenne-Haar transform of a[0,...,f0-1]. // f0 must be a Mersenne number. inline void mersenne_haar_nn(double *a, ulong f0); // In-place Mersenne-Haar transform of a[0,...,f0-1]. // Non-normalized version. // f0 must be a Mersenne number. // ========== HEADER FILE src/haar/prefix-transform.h: ========== void prefix_transform(Type *f, ulong ldn); // Prefix transform: let F[] be the transform of f[], then // F[k] = sum( j \in P(k), f[j] ) where P(k) is the set of prefixes of k. // // Transform with basis: // // 0: [ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + ] // 1: [ + + + + + + + + + + + + + + + + ] // 2: [ + + + + + + + + ] // 3: [ + + + + + + + + ] // 4: [ + + + + ] // 5: [ + + + + ] // 6: [ + + + + ] // 7: [ + + + + ] // 8: [ + + ] // 9: [ + + ] // 10: [ + + ] // 11: [ + + ] // 12: [ + + ] // 13: [ + + ] // 14: [ + + ] // 15: [ + + ] // 16: [ + ] // 17: [ + ] // 18: [ + ] // 19: [ + ] // 20: [ + ] // 21: [ + ] // 22: [ + ] // 23: [ + ] // 24: [ + ] // 25: [ + ] // 26: [ + ] // 27: [ + ] // 28: [ + ] // 29: [ + ] // 30: [ + ] // 31: [ + ] // void inverse_prefix_transform(Type *f, ulong ldn); // Inverse of prefix_transform(). // Transform with basis: // // 0: [ + - - - - - ] // 1: [ + - - - - ] // 2: [ + - - - ] // 3: [ + - - - ] // 4: [ + - - ] // 5: [ + - - ] // 6: [ + - - ] // 7: [ + - - ] // 8: [ + - ] // 9: [ + - ] // 10: [ + - ] // 11: [ + - ] // 12: [ + - ] // 13: [ + - ] // 14: [ + - ] // 15: [ + - ] // 16: [ + ] // 17: [ + ] // 18: [ + ] // 19: [ + ] // 20: [ + ] // 21: [ + ] // 22: [ + ] // 23: [ + ] // 24: [ + ] // 25: [ + ] // 26: [ + ] // 27: [ + ] // 28: [ + ] // 29: [ + ] // 30: [ + ] // 31: [ + ] // inline void slow_prefix_convolution(const Type *f, const Type *g, ulong ldn, Type *h); // Compute the prefix convolution h[] of f[] and g[]: // h[k] = sum(j \in P(k), f[k]*g[j]+f[j]*g[k]) - f[k]*g[k] // where P(k) is the set of prefixes of k. // Result written to h[]. // Complexity is O(n*log(n)) inline void slow_prefix_convolution(const Type *f, Type *g, ulong ldn); // Result written to g[]. inline void prefix_convolution(Type * restrict f, Type * restrict g, ulong ldn); // Compute the prefix convolution h[] of f[] and g[]: // h[k] = sum(j \in P(k), f[k]*g[j]+f[j]*g[k]) - f[k]*g[k] // where P(k) is the set of prefixes of k. // Result written to g[]. // Complexity is O(n) // Semi-symbolic scheme where (A,B,...,F) denotes (10,11,...,15): // [0 1 2 3 4 5 6 7 8 9 A B C D E F] // [1 1 3 5 7 9 B D F] // [2 2 6 A E ] // [3 3 3 7 B F] // [4 4 C ] // [5 5 5 D ] // [6 6 6 E ] // [7 7 7 7 F] // [8 8 ] // [9 9 9 ] // [A A A ] // [B B B B ] // [C C C ] // [D D D D ] // [E E E E ] // [F F F F F] // ========== HEADER FILE src/haar/transposedhaarnn.h: ========== void transposed_haar_nn(Type *f, ulong ldn, Type *ws=nullptr); // Transform wrt. to transposed non-normalized Haar base. // This is the inverse_haar() routine without normalization. void inverse_transposed_haar_nn(Type *f, ulong ldn, Type *ws=nullptr); void transposed_haar_inplace_nn(Type *f, ulong ldn); // Transform wrt. to transposed non-normalized Haar base. // In-place operation. // The sequence // inverse_haar_permute(); transposed_haar_inplace_nn(); // is equivalent to // transposed_haar_nn() void inverse_transposed_haar_inplace_nn(Type *f, ulong ldn); // ========== HEADER FILE src/haar/transposedhaarrevnn.h: ========== void transposed_haar_rev_nn(Type *f, ulong ldn); // Transform with basis (transposed basis of haar_rev_nn()): // 0: [ + + + + + + ] // 1: [ + - + + + + ] // 2: [ + + - + + + ] // 3: [ + - - + + + ] // 4: [ + + + - + + ] // 5: [ + - + - + + ] // 6: [ + + - - + + ] // 7: [ + - - - + + ] // 8: [ + + + + - + ] // 9: [ + - + + - + ] // 10: [ + + - + - + ] // 11: [ + - - + - + ] // 12: [ + + + - - + ] // 13: [ + - + - - + ] // 14: [ + + - - - + ] // 15: [ + - - - - + ] // 16: [ + + + + + - ] // 17: [ + - + + + - ] // 18: [ + + - + + - ] // 19: [ + - - + + - ] // 20: [ + + + - + - ] // 21: [ + - + - + - ] // 22: [ + + - - + - ] // 23: [ + - - - + - ] // 24: [ + + + + - - ] // 25: [ + - + + - - ] // 26: [ + + - + - - ] // 27: [ + - - + - - ] // 28: [ + + + - - - ] // 29: [ + - + - - - ] // 30: [ + + - - - - ] // 31: [ + - - - - - ] // // in-place algorithm // no normalization void inverse_transposed_haar_rev_nn(Type *f, ulong ldn);