src/math/convolution/fast-walsh-hadamard-transform.hpp

• View this file on GitHub
• Last update: 2023-06-24 21:59:36+09:00
• Include: #include "src/math/convolution/fast-walsh-hadamard-transform.hpp"

Depends on

• src/cpp-template/header/size-alias.hpp

Required by

• src/math/convolution/bitwise-and-convolution.hpp
• src/math/convolution/bitwise-xor-convolution.hpp

Verified with

• test/library-checker/bitwise_and_convolution.test.cpp
• test/library-checker/bitwise_xor_convolution.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"

#include <cassert>
#include <vector>

namespace luz {

  // length of f must be 2^k
  template < typename T, typename F >
  void fast_walsh_hadamard_transform(std::vector< T > &f, F op) {
    const usize n = f.size();
    assert((n & (n - 1)) == 0);

    usize i = 1;
    while (i < n) {
      usize j = 0;

      while (j < n) {
        for (usize k = 0; k < i; k++) {
          op(f[j + k], f[j + k + i]);
        }

        j += i << 1;
      }

      i <<= 1;
    }
  }

} // namespace luz

#line 2 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 4 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#include <cassert>
#include <vector>

namespace luz {

  // length of f must be 2^k
  template < typename T, typename F >
  void fast_walsh_hadamard_transform(std::vector< T > &f, F op) {
    const usize n = f.size();
    assert((n & (n - 1)) == 0);

    usize i = 1;
    while (i < n) {
      usize j = 0;

      while (j < n) {
        for (usize k = 0; k < i; k++) {
          op(f[j + k], f[j + k + i]);
        }

        j += i << 1;
      }

      i <<= 1;
    }
  }

} // namespace luz

Back to top page