Fast Walsh Hadamard Transform (高速ウォルシュアダマール変換) (math/fft/fast-walsh-hadamard-transform.hpp)

• View this file on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "math/fft/fast-walsh-hadamard-transform.hpp"

Required by

• Bitwise Xor Convolution (Bitwise-XOR畳み込み) (math/fft/bitwise-xor-convolution.hpp)

Verified with

• test/verify/yosupo-bitwise-xor-convolution.test.cpp

Code

/**
 * @brief Fast Walsh Hadamard Transform (高速ウォルシュアダマール変換)
 */
template< typename T >
void fast_walsh_hadamard_transform(vector< T > &f, bool inv = false) {
  const int n = (int) f.size();
  assert((n & (n - 1)) == 0);
  for(int i = 1; i < n; i <<= 1) {
    for(int j = 0; j < n; j += i << 1) {
      for(int k = 0; k < i; k++) {
        T s = f[j + k], t = f[j + k + i];
        f[j + k] = s + t;
        f[j + k + i] = s - t;
      }
    }
  }
  if(inv) {
    T inv_n = T(1) / n;
    for(auto &x : f) x *= inv_n;
  }
}

#line 1 "math/fft/fast-walsh-hadamard-transform.hpp"
/**
 * @brief Fast Walsh Hadamard Transform (高速ウォルシュアダマール変換)
 */
template< typename T >
void fast_walsh_hadamard_transform(vector< T > &f, bool inv = false) {
  const int n = (int) f.size();
  assert((n & (n - 1)) == 0);
  for(int i = 1; i < n; i <<= 1) {
    for(int j = 0; j < n; j += i << 1) {
      for(int k = 0; k < i; k++) {
        T s = f[j + k], t = f[j + k + i];
        f[j + k] = s + t;
        f[j + k + i] = s - t;
      }
    }
  }
  if(inv) {
    T inv_n = T(1) / n;
    for(auto &x : f) x *= inv_n;
  }
}

Back to top page